uninformed Search와 비교하여 이론적으로 time complexity가 달라지진 않지만 heuristic function을 잘 주면 실질적으로 빨리 끝나는 장점이 있다.

f(n) = g(n) + h(n)

Tree/Graph search algorithm

image.png

Best-first Search

노드가 f(cost 추정치)에 의해 선택되는 서치

f : estimate of “desirability”) (바람직함의 추정치)

graph search는 dijkstra와 동일하다

fringe에는 바람직함이 증가하는 순서 == f가 작은 순서부터 저장됨

h(n) : n에서 goal까지 cheapest path의 추정치

Greedy best-first search

f(n) = h(n) : 과거는 안보고 미래만 봄

Time Complexity : O(b^m)

Space Complexity : O(b^m)

Completeness : no (DFS랑 똑같네) 유한한 상태 공간 하에서의 graph search에선 yes

Optimality : no

A* search

Idea : 이미 비싼 path는 피하자! g와 h 둘다 봄

best-first search의 한 예

admissible h 사용