Best-first  Search

 

Wikipedia : Best-first Search : Best-first search 는 어떠한 휴리스틱 (Heuristic) 에 따라서 최근의 모든 경로 (path) 들을 순서화하여 깊이우선 탐색 (Depth-first Search) 을 최적화하는 탐색알고리즘이다. 그 휴리스틱은 어떤 경로의 끝이 해 (solution) 에 얼마나 근접한 것인지를 예측하기위한 것이다. 해에 더 가깝다고 판정되는 경로들을 먼저 확장한다. 후보중에서 어떤 경로를 확장하는 것이 가장 좋은가 하는 효율적인 선택은 일반적으로는 우선순위 큐 (priority queue)를 사용하여 구현된다.

Best-first search 알고리즘의 예로서는 Dijkstra's algorithmA* 알고리즘 를 들 수 있다. Best-first 알고리즘들은 조합탐색 (combinatorial search)에서 발견 (pathfinding)을 위해서도 가끔 사용된다.

term :

탐색 (Search)   너비우선 탐색 (Breadth-first Search)   깊이우선 탐색 (Depth-first Search)   반복적 깊이증가 탐색 (Iterative Deepening Depth-first Search)    게임 (Game)

site :

Best First Search

Best First Search : Demo

paper :

재귀적인 최상우선 탐색 (Recursive Best-First Search) : Nils J.Nilsson