반복적 깊이심화 탐색

반복적 깊이심화 탐색

분류	검색 알고리즘
자료 구조	트리 구조, 그래프

반복적 깊이심화 탐색(iterative-deepening search)은 맹목적 탐색 방법 중 하나로 깊이 우선 탐색을 반복적으로 적용하되, 깊이 한계를 조정하여 실행하는 탐색 방법이다. 즉, 깊이 우선 탐색과 너비 우선 탐색을 합쳐서 운용하는 탐색 방법이다.

장점

깊이 우선 탐색의 장점인 메모리 공간 효율, 너비 우선 탐색의 장점인 최단 경로 탐색 보장을 다 가지고 있다.

비효율성

깊이 우선 탐색을 반복하게 되므로 비효율성이 존재하나, 실질적으로 크게 늘지는 않는다.

예를 들어 각 노드가 10개의 지식노드를 가진다고 가정할 때, 너비 우선 탐색 대비 약 11% 정도의 추가 노드가 생성된다.

맹목적 탐색 적용시 우선 고려 대상이다.

같이 보기

• 깊이 우선 탐색
• 너비 우선 탐색