uninformed Search와 비교하여 이론적으로 time complexity가 달라지진 않지만 heuristic function을 잘 주면 실질적으로 빨리 끝나는 장점이 있다.
f(n) = g(n) + h(n)
노드가 f(cost 추정치)에 의해 선택되는 서치
f : estimate of “desirability”) (바람직함의 추정치)
graph search는 dijkstra와 동일하다
fringe에는 바람직함이 증가하는 순서 == f가 작은 순서부터 저장됨
h(n) : n에서 goal까지 cheapest path의 추정치
f(n) = h(n) : 과거는 안보고 미래만 봄
Time Complexity : O(b^m)
Space Complexity : O(b^m)
Completeness : no (DFS랑 똑같네) 유한한 상태 공간 하에서의 graph search에선 yes
Optimality : no
Idea : 이미 비싼 path는 피하자! g와 h 둘다 봄
best-first search의 한 예
admissible h 사용