너비우선탐색 과 깊이우선탐색

http://www.aistudy.com/heuristic/breadth-first_search.htm

breadth -first search 

컴퓨터과학 에서 breadth-first search (BFS) 는 트리 (Tree), 그래프 (Graph) 를 탐색하는 tree search algorithm 이다. 보통 root node에서 출발하여 모든 이웃하는 노드들을 탐색한다. 또한 가장 가까운 노드들 각각에 대해 탐색하지 않은 이웃 노드들을 탐색하여 목표를 찾을 때까지 계속한다.

BFS 는 해 (solution)를 찾아서 조직적으로 트리의 모든 노드들을 검사하는 무정보 탐색 (Uninformed or Blind Search) 이다. 달리 말하면 목표에 대한 고려없이 목표가 발견될 때 까지 전체 트리를 전부 탐색한다 (exhaustively searches). BFS 는 휴리스틱 (Heuristic)  을 사용하지 않는다.

깊이 우선 탐색 

depth first search 

위키백과, 우리 모두의 백과사전.

깊이 우선 탐색

깊이 우선 탐색(depth-first search: DFS)은 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다.

목차

  [숨기기] 

• 1 깊이 제한과 백트래킹
• 2 알고리즘
• 3 장점과 단점
• 4 시간과 저장공간 분석
• 5 같이 보기

깊이 제한과 백트래킹[편집]

탐색 과정이 시작 노드에서 한없이 깊이 진행되는 것을 막기 위해 깊이 제한(depth bound)을 사용한다. 깊이 제한에 도달할 때까지 목표노드가 발견되지 않으면 최근에 첨가된 노드의 부모노드로 되돌아와서, 부모노드에 이전과는 다른 동작자를 적용하여 새로운 자식노드를 생성한다.
여기서 부모노드로 되돌아오는 과정을 백트래킹(backtracking)이라 한다.

http://forum.falinux.com/zbxe/index.php?document_srl=536248&mid=lecture_tip

알고리즘[편집]

  

[깊이우선탐색 알고리즘]