최상 우선 탐색

최상 우선 탐색(best-first search)은 특정 규칙에 따라 선택된 가장 유망한 노드를 확장하여 일반적인 무방향성 그래프를 탐색하는 탐색 알고리즘의 한 종류이다.

주데아 펄은 최상 우선 탐색을 "노드 n의 묘사, 목표의 묘사, 해당 지점까지의 탐색으로 수집된 정보, 그리고 가장 중요하게는 문제 영역에 대한 추가 지식에 따라 달라질 수 있는 휴리스틱 평가 함수 으로 노드 n의 유망성을 추정하는 것"으로 설명했다.Pearl, J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, 1984. p. 48.

일부 저자들은 "최상 우선 탐색"을 특정하게 경로의 끝이 해법(또는 목표)에 얼마나 가까운지 예측하려는 휴리스틱을 사용하는 탐색을 지칭하는 데 사용해왔다. 이는 해법(또는 목표)에 더 가깝다고 판단되는 경로를 먼저 확장하는 방식이다. 이 특정 유형의 탐색을 탐욕적 최상 우선 탐색 또는 순수 휴리스틱 탐색이라고 한다.

확장을 위한 현재 최적 후보의 효율적인 선택은 일반적으로 우선순위 큐를 사용하여 구현된다.

A* 알고리즘은 B*와 마찬가지로 최상 우선 탐색 알고리즘의 한 예이다. 최상 우선 알고리즘은 조합 탐색에서 경로 탐색에 자주 사용된다. A*와 B* 모두 탐욕적 최상 우선 탐색이 아니다. 이들은 목표까지의 예상 거리 외에 시작점으로부터의 거리도 포함하기 때문이다.

탐욕적 최상 우선 탐색

탐욕 알고리즘을 사용하여 부모의 첫 번째 후계자를 확장한다. 후계자가 생성된 후:https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume28/coles07a-html/node11.html#modifiedbestfs Greedy Best-First Search when EHC Fails, Carnegie Mellon

 후계자의 휴리스틱이 부모보다 좋으면 후계자는 큐의 맨 앞에 놓이고(부모는 그 바로 뒤에 다시 삽입됨), 루프가 다시 시작된다.
 그렇지 않으면 후계자는 큐에 삽입된다(휴리스틱 값에 따라 위치가 결정됨). 이 절차는 부모의 남은 후계자(있는 경우)를 평가한다.
다음은 이 알고리즘의 의사코드 예제이다. 여기서 queue는 목표로부터의 휴리스틱 거리를 기반으로 노드를 정렬하는 우선순위 큐를 나타낸다. 이 구현은 방문한 노드를 추적하며, 따라서 무방향 그래프에 사용될 수 있다. 경로를 검색하도록 수정될 수 있다.
 procedure GBS(start, target) is:
   start를 방문으로 표시
   start를 큐에 추가
   while queue is not empty do:
     current_node ← 큐에서 목표까지의 거리가 가장 짧은 정점
     current_node를 큐에서 제거
     foreach current_node의 이웃 n do:
       if n not in visited then:
         if n is target:
           return n
         else:
           n을 방문으로 표시
           n을 큐에 추가
   return failure

 같이 보기 
 빔 탐색
 A* 알고리즘
 데이크스트라 알고리즘

 각주 

 외부 링크 
 위키책: 인공지능: 최상 우선 탐색

분류:검색 알고리즘