깊이우선 탐색이나 너비우선 탐색 등의 blind search method 는 goal 까지 의 경로를 찾는 상당히 소모적인 (exhaustive) 방법이다. 즉 문제에 대한 해를 제공하지만 너무 많은 노드를 확장시키므로 실용적이지 못하다. 많은 문제에 있어 탐색작업을 축소시키기 위해 항상 옳은 해를 제공하지는 못하지만 대부분의 경우에 잘맞는 경험에 의한 규칙 (rules of thumb) 을 이용하는 경우가 많다. 이렇게 그래프로써 표현된 문제에 대한 특별한 정보를 이용하여 탐색 (Search) 작업을 빠르게 진행시키는 방식을 heuristic search method 라고 하며 사용된 정보를 heuristic information 이라 한다.

Heuristic Search 의 역사      

휴리스틱 (Heuristic) 은 새로이 생성된 후계 노드들을 heuristic information 에 따라 정해지는 기준에 의해 순서를 정하거나 ,재조정 하는 것으로서 이렇게 함으로써 탐색은 가장 바람직한 부분을 확장시켜 나가게 될 것이다. 이렇듯 순서를 재조정하기 위해서는 노드의 바람직한 정도를 평가하기 위한 척도가 필요한데 이 척도를 평가함수 (evaluation function) 이라 한다. evaluation function 의 목적은 확장시킬 노드들에게 순위를 매김으로써 어떤 것이 목표노드 까지의 최상의 경로에 있음직한가를 결정하는 것이다. evaluation function은 여러 가지 착상에 근거를 두고 있다. 어떤 노드에 대하여 최상의 경로에 있을 확률을 이용하는 것도 있고, 임의의 노드와 목표 노드들간의 거리 (distance) 나 차이 (difference)를 이용하는 경우도 있다. 게임 (Game) 이나 퍼즐에서는 목표까지의 가능성과 관계된 특성들에 근거를 두는 경우도 있다...........

term :

휴리스틱 탐색 (Heuristic Search)     휴리스틱 (Heuristic)    탐색 (Search)     게임 (Game)    인공지능 (Artificial Intelligence)

site :

AI Topics : Heuristic Search