반복적 깊이심화 탐색

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기
반복적 깊이심화 탐색
분류 검색 알고리즘
자료 구조 트리 구조, 그래프

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

장점[편집]

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

비효율성[편집]

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

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

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

같이 보기[편집]

각주[편집]