휴리스틱 탐색

무정보 탐색의 한계

- 무정보 탐색(깊이/너비 우선 탐색)은 목적지까지 경로를 찾는데 상당히 소모적임 

-> 해는 찾지만 너무 많은 노드를 확장하여 실용적이지 못함

 

 

휴리스틱 탐색 heuristic search, 정보 탐색 infromed search

- 탐색 작업을 축소시키기 위해 대부분 경우에 잘맞는 경험에 의한 규칙(rules of thumb, 주먹구구식)을 이용

- 그래프로 표현된 문제에 특별한 정보(휴리스틱 정보)를 이용하여 탐색을 빠르게 진행하는 방식을 휴리스틱 탐색 모델이라함.

 

무정보 탐색 예시

- 너비 우선 탐색

- 깊이 우선 탐색

- 양방향 탐색

 

휴리스틱 탐색 예시

- 언덕 오르기 hill climbing

- 분기 한정법 branch and bound

- A* 알고리즘

- 최상 우선 탐색 best-first search

 

 

휴리스틱 탐색과 평가 함수

- 새로 생성된 후계 노드들은 휴리스틱 정보에 의한 기준에 따라 순서를 정하거나 재조정하여 탐색을 확장시켜나감

- 평가 함수 evaluation function : 순서를 재조정하기 위해 노드의 바람직한 정도를 평가하기 위한 척도