휴리스틱 탐색

개념

휴리스틱 탐색은 경험이나 문제에 대한 지식을 이용해 더 유망한 상태를 먼저 탐색하는 방법이다. Informed search라고도 한다.

휴리스틱 함수

휴리스틱 함수는 현재 상태가 목표에 얼마나 가까운지 추정하는 평가 함수이다. 값이 작을수록 좋게 설계할 수도 있고, 값이 클수록 좋게 설계할 수도 있다.

예를 들어 8-Puzzle에서는 목표 위치와 다른 타일 수나 맨해튼 거리의 합을 휴리스틱으로 사용할 수 있다. 게임 탐색에서는 내가 이길 수 있는 줄 수와 상대가 이길 수 있는 줄 수의 차이를 평가 함수로 사용할 수 있다.

최단 경로 문제에서 실제 남은 비용을 $h^{\ast }(n)$이라 할 때, 과대평가하지 않는 허용적 휴리스틱은 다음 조건을 만족한다.

$$0\le h(n)\le h^{\ast }(n)$$

장점과 한계

휴리스틱 탐색은 맹목 탐색보다 훨씬 빠르게 답을 찾을 수 있다. 하지만 휴리스틱이 잘못 설계되면 최적해를 보장하지 못하거나 지역 최적에 빠질 수 있다.