Iterative Deepending Search (점차적 깊이 제한 탐색, IDS)는 깊이 우선 탐색(DFS)과 깊이 제한 탐색(DLS)을 결합한 탐색 알고리즘으로, 주로 트리 또는 그래프의 상태 공간을 탐색하고 목표 상태를 찾는데 사용된다.
IDS는 깊이 제한을 점진적으로 늘리면서 깊이 제한 탐색(DLS)를 반복적으로 수행하는 형태로 완전성을 보장하면서 최단 경로를 찾을 수 있다.
특징
- 깊이 제한을 반복적으로 증가
- ISD는 처음에는 매우 작은 깊이 제한(ex. depth limit = 0)으로 시작한다.
- 이 깊이 제한 아래에서는 상태 공간을 한정된 깊이만큼 탐색한다. 그런 다음 깊이 제한을 1씩 증가하며 반복적으로 깊이 제한 탐색(DLS)을 수행한다.
- 완전성(Completeness) 보장
- ISD는 완전성(Completeness)을 보장한다. 즉, 목표 상태가 존재하면 반드시 찾아낸다.
- 이는 깊이 제한을 반복적으로 증가시키면서 모든 가능성을 고려하기 때문이다.
- 평균적 시간 복잡도(Time Complexity)
- ISD의 시간 복잡도(Time Complexity)는 O(b^d 이다.
- b = branch, 각 상태에서 이동 가능한 자식 상태의 개수
- d = depth, 최단 경로의 깊이
- 즉, 목표 상태가 깊이 d 에 있다면 모든 상태를 탐색해야 한다.
- ISD의 시간 복잡도(Time Complexity)는 O(b^d 이다.
- 낮은 공간 복잡도(Space Complexity)
- IDS의 공간 복잡도(Space Complexity)는 O(bd) 이다. 이는 공간 복잡도가 깊이에 비례한다는 것을 의미한다.
- 즉, 깊이가 깊을 수록 더 많은 메모리가 필요하게 된다.
- 최적성(Optimality) 보장
- IDS는 최적성(Optimality)을 보장한다.
- 이는 만약 단계 비용(step cost)이 1이라면 최적 경로를 찾을 수 있다는 것을 의미한다.
Compre to BFS
- 수치적 비교 결과
b = 10, d = 5
N(BFS): 10 + 100 + 1,000 + 10,000 + 100,000 + 999,990 = 1,111,100
N(IDS): 50 + 400 + 3,000 + 20,000 + 100,000 =123,450
- IDS의 경우, b와 d에 따라서 각 깊이에서 확장한 노드 수를 계산한 후 모두 합산한 것이다. 예를 들어, 1번 깊이에서 10개의 노드를 확장하고, 2번 깊이에서 40개의 노드를 확장하고, 3번 깊이에서 300개의 노드를 확장하는 등의 과정을 거쳐 총 123,450개의 노드를 확장했다.
- BFS의 경우, 모든 레벨의 노드를 순차적으로 확장하고, 이로 인해 목표 상태를 먼저 찾을 수 있지만, 레벨마다 노드 수가 급격하게 증가한다.따라서 N(BFS)는 더 높은 값인 1,111,100개의 노드를 확장했다.- 결론적으로 위 예시에서 IDS가 노드 확장 횟수에서 더 효율적으로 동작한 이유는 IDS가 목표가 있는 깊이 d에 도달하면 더 깊은 노드를 확장하지 않는다는 특성 때문이다. 이로 인해 상대적으로 더 적은 노드를 확장하게 되어 노드 확장 횟수가 낮아진다. 반면, BFS는 레벨마다 모든 노드를 확장하므로 노드 확장 횟수가 더 높다.
- 또한, BFS는 목표 테스트를 적용하면 노드를 생성할 때 바로 목표 상태인지 확인할 수 있으며, 이로 인해 목표를 빠르게 찾을 수 있다.
