최상 우선 탐색

개념

최상 우선 탐색은 OPEN 리스트 안의 후보 중 평가 함수 값이 가장 좋은 노드를 먼저 선택하는 휴리스틱 탐색이다. Best First Search라고도 한다.

평가값이 작을수록 좋은 경우 선택 규칙은 다음과 같다.

$$n^{\ast }=\arg \underset{n\in \mathrm{OPEN}}{\min }f(n)$$

언덕등반 탐색과의 차이

언덕등반 탐색은 현재 상태에서 가장 좋은 자식 하나만 선택한다. 반면 최상 우선 탐색은 여러 후보를 OPEN과 CLOSED에 저장해 두고, 전체 후보 중 가장 좋아 보이는 것을 고른다.

장점

언덕등반 탐색보다 유연하다. 당장 선택하지 않은 후보도 나중에 다시 고려할 수 있다.

한계

현재 상태까지 오기 위해 이미 사용한 비용은 고려하지 않고 h(n)만 볼 수 있다. 그래서 실제 경로 비용이 큰데도 목표에 가까워 보인다는 이유로 잘못된 경로를 선택할 수 있다. 이를 개선한 것이 A star 알고리즘이다.