Iterative Deepening Depth-first Search

 

반복적 깊이증가 (iterative deepening) 는 깊이우선 탐색 (Depth-first Search) 처럼 메모리 필요량이 깊이 제한에 비례하면서도 최단 경로로 목표 노드를 찾는 것을 보장하는 방법이다. 반복적 깊이증가 방법에서는 목표 노드가 찾아질 때까지 깊이 제한을 1 씩 증가시키면서 연속적인 깊이우선 탐색을 수행한다. 다음 그림에 반복적 깊이증가 탐색이 진행되는 예를 나타냈다.

 

반복적 깊이증가 탐색 과정

Wikipedia : Iterative deepening depth-first search

반복적으로 깊게 내려가는 검색방식 : Stuart Russell

반복적 깊이증가 (Iterative Deepening) : Nils J.Nilsson