Best-first search 문서 원본 보기

[[분류: 탐색]]

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

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

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

== 종류 ==
# [[Greedy algorithm]]
# [[A* algorithm]]
# [[Beam algorithm]]