Best-first Search
Wikipedia : Best-first Search : Best-first search 는 어떠한 휴리스틱 (Heuristic) 에 따라서 최근의 모든 경로 (path) 들을 순서화하여 깊이우선 탐색 (Depth-first Search) 을 최적화하는 탐색알고리즘이다. 그 휴리스틱은 어떤 경로의 끝이 해 (solution) 에 얼마나 근접한 것인지를 예측하기위한 것이다. 해에 더 가깝다고 판정되는 경로들을 먼저 확장한다. 후보중에서 어떤 경로를 확장하는 것이 가장 좋은가 하는 효율적인 선택은 일반적으로는 우선순위 큐 (priority queue)를 사용하여 구현된다.
Best-first search 알고리즘의 예로서는 Dijkstra's algorithm 과 A* 알고리즘 를 들 수 있다. Best-first 알고리즘들은 조합탐색 (combinatorial search)에서 발견 (pathfinding)을 위해서도 가끔 사용된다.
term :
탐색 (Search) 너비우선 탐색 (Breadth-first Search) 깊이우선 탐색 (Depth-first Search) 반복적 깊이증가 탐색 (Iterative Deepening Depth-first Search) 게임 (Game)
site :
paper :
재귀적인 최상우선 탐색 (Recursive Best-First Search) : Nils J.Nilsson