휴리스틱 탐색

Greedy Best First Search

• Heuristic function의 평가 값이 제일 좋은 Node 부터 탐색한다. 

 

$A^*$ 알고리즘

• $f(n) = g(n) + h(n)$
  • $g(n)$은 현재 노드까지 오는데 사용한 비용
  • $h(n)$은 Heuristic Function의 평가값 
• admissable
  • 휴리스틱 함수가 실제 Cost보다 언제나 작거나 같게 예측을 하는것 
• Admissable한 Heuristic Function을 쓰는 $A^*$알고리즘은 언제나 최선의 솔루션을 구한다.