반복적 깊이심화 탐색
둘러보기로 이동
검색으로 이동
분류 | 검색 알고리즘 |
---|---|
자료 구조 | 트리 구조, 그래프 |
목록 |
---|
관련 주제 |
반복적 깊이심화 탐색(iterative-deepening search)은 맹목적 탐색 방법 중 하나로 깊이 우선 탐색을 반복적으로 적용하되, 깊이 한계를 조정하여 실행하는 탐색 방법이다. 즉, 깊이 우선 탐색과 너비 우선 탐색을 합쳐서 운용하는 탐색 방법이다.
장점
[편집]깊이 우선 탐색의 장점인 메모리 공간 효율, 너비 우선 탐색의 장점인 최단 경로 탐색 보장을 다 가지고 있다.
비효율성
[편집]깊이 우선 탐색을 반복하게 되므로 비효율성이 존재하나, 실질적으로 크게 늘지는 않는다.
예를 들어 각 노드가 10개의 지식노드를 가진다고 가정할 때, 너비 우선 탐색 대비 약 11% 정도의 추가 노드가 생성된다.[1]
맹목적 탐색 적용시 우선 고려 대상이다.
같이 보기
[편집]각주
[편집]- ↑ 이건명. “강의 "인공지능" 中 탐색과 최적화 I”. 《KOCW》.