Informed Search

• state와 cost에 대한 정보가 있음. -> 정보에 따라 변하는 규칙 -> 더 효율적임

• Evaulation Function : $f(n) = g(n) + h(n)$
  $g(n)$ = initial부터 node n까지의 비용(거리)
  $h(n)$ = node n부터 goal까지의 비용(거리) (추정치 Heuristic)

• frontier : Priority Queue
  - $f(n)$이 작은 것이 우선

Greedy Best-first Search

• $f(n) = h(n)$ -> 지금까지의 cost를 고려하지 않고, Goal까지의 cost만 고려

• Evaluation
  • Tree Based
    • Not Complete
    • Not Optimal
    • Time/Space complexity : O(bm)
  • Graph Based
    • Uniform-cost search와 실행이 비슷하다. 우선순위에 쓰이는 함수만 다르다.

A* Search

• $f(n) = g(n) + h(n)$ -> 지금까지의 cost와 Goal까지의 cost를 모두 고려

• Evaluation
  • Tree Based
    - Complete
    - Optimal ($h(n)$이 과대평가 되지 않았다면)
    Prove)

    Goal state이지만 optimal하지 않은 노드 $S$가 frontier에 있다고 하자. 그러면
    $f(S) = g(S) ≥ Optimal Cost　 (∵h(S) = 0)$
    optimal solution path를 진행중인 노드 $n$이 frontier에 있는 상태일 것이다.
    (이 node가 진행하다 보면 Goal state이면서 optimal한 node가 생성될 것이다.)
    이 때, $h(n)$이 실제 cost보다 크지 않으면
    $f(n) = g(n) + h(n) ≤ Optimal Cost$
    따라서, 항상 $f(n)＜g(S)$ 이므로 node $S$는 generate 되지 않는다.

  • Graph Based
    • Not Optimal
  • $h(n)$에 많은 영향을 받는다.

$h = 0$ → uniform cost
$g = 1, h = 0$ → breadth-first
$g = 0$ → greedy best-fisrt![]