Best-first search

개요

노드 중에서 제일 그럴듯한 노드를 먼저 고르는 알고리즘이다. 이때 제일 그럴 듯한 노드를 구하는 방법은 Heuristic Function으로 주어지게 된다.

1. 생성된 노드의 집합에서 제일 적합한 노드를 고른다.
2. 선택된 노드를 확장시켜서 노드의 Successor을 만든다.
3. 생성된 Successor을 다시 생성된 노드의 집합에 넣는다.
4. 다시 1에서 반복.

휴리스틱 함수 F(n)을 사용하여 적합도를 평가하고 F(n)을 어떻게 선택하느냐가 성능에 큰 영향을 미친다.

종류

1. Greedy algorithm
2. A* algorithm
3. Beam search