2. 탐색과 최적화 - 정보 이용 탐색

휴리스틱 탐색이라고도 한다.
휴리스틱 = 신속하게 어림짐작하는 것
예) 최단 경로 문제에서 목적지까지 남은 거리 짐작
 
종류

• 언덕 오르기 방법
• best-first 탐색
• 빔 탐색
• A* 알고리즘

1) 언덕 오르기 방법 (hill climbimg method)

• 현재 노드에서 휴리스틱에 의한 평가값이 가장 좋은 이웃 노드 하나를 확장해 가는 방법
• 국소 최적해(local optimal solution)에 빠질 가능성이 있다
• -> global optimal solution을 구하지 못할 수도 있다.
• -> 이웃 중에서 가장 좋은 걸 찾기 때문

 
2) 최상 우선 탐색 (best-first search)

• 확장 중인 노드들 중, 휴리스틱에 의해 목표 노드까지 남은 거리가 가장 짧은 노드를 우선적으로 탐색

 
3) 빔 탐색 (beam search)

• 휴리스틱에 의한 평가값이 우수한 일정 개수(k)의 확장 가능한 노드만을 
• best-first search로 탐색

 
4) A* (A star) 알고리즘

• 추정한 전체 비용을 최소로 하는 노드를 확장해 가는 방법

: 전체 비용 =  현재 노드까지 투입된 비용 g(n) + 목표 노드까지 남은 비용 h(n)
-> 실제 남은 비용을 정확하게 예측 불가하므로 휴리스틱 함수를 사용한다.

예)