Iterative Deepening A^*

탐색 (Search)    휴리스틱 탐색 (Heuristic Search)   A* 알고리즘   최상우선 탐색 (Best-first Search)

반복적 깊이증가 A* (Iterative Deepenig A*) : Nils J.Nilsson : 무정보 탐색에서  너비우선 탐색 (Breadth-first Search)  의 메모리 요구량은 탐색공간에서 목표 노드의 깊이에 비례하여 지수적으로 증가한다고 하였다. 좋은 휴리스틱 (Heuristic) 이 분기 계수를 감소시키기는 하지만, 휴리스틱 탐색도 같은 단점을 가지고 있다. 무정보 탐색에서 소개한 반복적 깊이증가 탐색 (Iterative Deepening Depth-first Search) 을 이용하면 메모리 요구량이 목표 노드의 깊이에 비례하여 선형적으로 증가하면서 최단 경로를 찾을 수 있다. [Korf 1985] 가 제안한 반복적 깊이증가 A^* (iterative deepening A^*, IDA^*) 방법을 사용하면 휴리스틱 탐색 (Heuristic Search) 에서도 비슷한 효과를 얻을 수 있다. IDA^* 를 병렬 알고리즘으로 구현하면 효율을 더욱 높일 수도 있다.

이 방법은 보통의 반복적 깊이증가 탐색과 비슷한 방식으로 수행된다. 첫 번 탐색에서는 값 한계 (cost cut-off)를 로 설정한다. 은 시작 노드이다. 알다시피, 목표까지의 최적 경로값은 이 값보다 크거나 같다 (만일 이면 같게 된다. 이므로 더 작을 수는 없다). 탐색은 어떤 노드를 확장했을 때 자식 노드의  값이 한계값을 넘으면 되추적 (backtracking) 하면서 깊이우선 형태로 진행한다. 이 깊이우선 탐색 (Depth-first Search) 이 목표 노드를 찾고 끝난다면, 분명히 목표까지의 최단 경로를 찾은 것이다. 만일 그렇지 않으면, 최적 경로의 값은 이 한계값보다 크다고 할 수 있다. 따라서 한계값을 증가시키고 다시 깊이우선 탐색을 시작한다. 최적 경로의 다음으로 가능한 값은 얼마인가? 그 값은 이전의 깊이우선 탐색에서 방문했던 (하지만 확장되지는 않은) 노드들의 값 중 최소값보다 크거나 같을 것이다. 값이 최소인 노드가 최적 경로상에 있을 수 있는 것이다 (이전의 한계값과 같은 값을 갖는 최적 경로가 없다는 것은 이미 알고 있다). 이 의 최소값이 다음 번 깊이우선 탐색에서 한계값으로 사용된다. 직관적으로 IDA^* 가 목표까지의 최단 경로를 찾는 것을 보장한다는 것을 쉽게 알 수 있다.

IDA^* 가 노드의 확장을 반복해야 하지만 (보통의 반복적 깊이증가와 마찬가지로) 메모리 요구량의 감소와 깊이우선 탐색의 구현상의 효율성 (너비우선 탐색에 비하여) 과 관련하여 트레이드오프가 있는 것이다. 그런데 탐색공간에서 모든 노드의 값이 다른 경우에는 어떤 일이 발생하는지 생각해 보자. 반복의 회수가 값이 최적 경로의 값보다 작은 모든 노드의 수와 같게 된다.