반복적 깊이심화 탐색

반복적 깊이심화 탐색

분류	검색 알고리즘
자료 구조	트리, 그래프
최악 시간복잡도	$O(b^d)$, 여기서 $b$는 분기 계수이고 $d$는 가장 얕은 해답의 깊이이다.
공간복잡도	$O(d)$

컴퓨터 과학에서 반복적 깊이심화 탐색(iterative-deepening search) 또는 더 구체적으로 반복적 깊이심화 깊이 우선 탐색(iterative deepening depth-first search) (IDS 또는 IDDFS)은 깊이 우선 탐색의 깊이 제한 버전을 목표를 찾을 때까지 깊이 제한을 늘려가며 반복적으로 실행하는 상태 공간/그래프 탐색 전략이다. IDDFS는 최적이며, 이는 가장 얕은 목표를 찾는다는 의미이다. 깊이 $d+1$에 있는 노드를 방문하기 전에 깊이 $d$까지의 탐색 트리의 모든 노드를 방문하므로, 노드가 처음 방문되는 누적 순서는 너비 우선 탐색과 실질적으로 동일하다. 그러나 IDDFS는 훨씬 적은 메모리를 사용한다.

유향 그래프를 위한 알고리즘

다음 의사코드는 유향 그래프에 대해 재귀적 깊이 제한 DFS(DLS라고 함)를 사용하여 구현된 IDDFS를 보여준다. 이 IDDFS 구현은 이미 방문한 노드를 고려하지 않는다.

함수 IDDFS(root) 는
    깊이 0 부터 ∞ 까지 반복
        found, remaining ← DLS(root, depth)
        만약 found ≠ null 이면
            found 반환
        아니면 만약 not remaining 이면
            null 반환

함수 DLS(node, depth) 는
    만약 depth = 0 이면
        만약 node가 목표 이면
            (node, true) 반환
        아니면
            (null, true) 반환    (찾지 못했지만 자식이 있을 수 있음)

    아니면 만약 depth > 0 이면
        any_remaining ← false
        node의 각 child 에 대해 반복
            found, remaining ← DLS(child, depth−1)
            만약 found ≠ null 이면
                (found, true) 반환
            만약 remaining 이면
                any_remaining ← true    (깊이에서 하나 이상의 노드를 찾았으므로 IDDFS가 더 깊이 탐색하도록 함)
        (null, any_remaining) 반환

목표 노드가 DLS에 의해 발견되면, IDDFS는 더 깊이 탐색하지 않고 이를 반환한다. 그렇지 않고, 해당 깊이 수준에 적어도 하나의 노드가 존재하면, remaining 플래그는 IDDFS가 계속 진행하도록 한다.

2-튜플은 트리 깊이와 목표 멤버십을 사전에 알 수 없는 경우, IDDFS에게 계속 깊이 탐색하거나 중단하라는 신호를 보내는 반환 값으로 유용하다. 다른 해결책으로는 찾지 못했거나 남은 레벨 결과를 나타내기 위해 센티넬 값을 사용하는 방법도 있다.

속성

IDDFS는 깊이 우선 탐색의 공간 효율성을 사용하여 너비 우선 탐색의 완전성(분기 계수가 유한할 때)을 달성한다. 해답이 존재하면 가장 적은 아크를 가진 해답 경로를 찾는다.

반복적 깊이심화는 상태를 여러 번 방문하며, 이는 낭비적으로 보일 수 있다. 그러나 IDDFS가 깊이 $d$까지 탐색 트리를 탐색할 때, 전체 노력의 대부분은 깊이 $d$의 상태를 탐색하는 데 사용된다. 깊이 $d$의 상태 수에 비해 이 깊이 위에 있는 상태를 반복적으로 방문하는 비용은 항상 작다.

게임 트리 탐색에서 IDDFS의 주요 장점은 초기 탐색이 일반적으로 사용되는 킬러 휴리스틱 및 알파-베타 가지치기와 같은 휴리스틱을 개선하는 경향이 있어 최종 깊이 탐색에서 다양한 노드의 점수에 대한 더 정확한 추정치가 나올 수 있고, 더 좋은 순서로 탐색이 완료되므로 탐색이 더 빨리 끝난다는 것이다. 예를 들어, 알파-베타 가지치기는 가장 좋은 수를 먼저 탐색할 때 가장 효율적이다.

두 번째 장점은 알고리즘의 반응성이다. 초기 반복은 $d$에 작은 값을 사용하므로 매우 빠르게 실행된다. 이를 통해 알고리즘은 거의 즉시 결과에 대한 초기 지표를 제공하고, $d$가 증가함에 따라 정제된다. 체스 프로그램과 같은 상호작용 환경에서 사용될 때, 이 기능은 프로그램이 지금까지 완료한 탐색에서 찾은 현재 최선의 수로 언제든지 플레이할 수 있게 한다. 이는 탐색의 각 깊이가 코재귀적(corecursion)으로 해답의 더 나은 근사치를 생성한다고 표현할 수 있지만, 각 단계에서 수행되는 작업은 재귀적이다. 이는 중간 결과를 생성하지 않는 전통적인 깊이 우선 탐색으로는 불가능하다.

점근적 분석

시간 복잡도

(균형 잡힌) 트리에서 IDDFS의 시간 복잡도는 너비 우선 탐색과 동일하게 $O(b^d)$이다.^:5 여기서 $b$는 분기 계수이고 $d$는 목표의 깊이이다.

증명

반복적 깊이심화 탐색에서 깊이 $d$의 노드는 한 번 확장되고, 깊이 $d-1$의 노드는 두 번 확장되며, 탐색 트리의 루트까지 계속해서 $d+1$번 확장된다.^:5 따라서 반복적 깊이심화 탐색의 총 확장 횟수는 다음과 같다.

$b^d+2b^{d-1}+3b^{d-2}+\cdots +(d-1)b^2+db+(d+1)=\sum _{i=0}^d(d+1-i)b^i$

여기서 $b^d$는 깊이 $d$에서의 확장 횟수, $2b^{d-1}$는 깊이 $d-1$에서의 확장 횟수 등이다. $b^d$를 인수로 묶으면 다음과 같다.

$b^d(1+2b^{-1}+3b^{-2}+\cdots +(d-1)b^{2-d}+d{b}^{1-d}+(d+1)b^{-d})$

이제 $x=\frac{1}{b}=b^{-1}$라고 하자. 그러면 다음과 같다.

$b^d(1+2x+3x^2+\cdots +(d-1)x^{d-2}+d{x}^{d-1}+(d+1)x^d)$

이는 무한 급수보다 작다.

$b^d(1+2x+3x^2+4x^3+\cdots )=b^d\left(\sum _{n=1}^{\mathrm{\infty }}n{x}^{n-1}\right)$

이는 수렴하여

$b^d(1-x{)}^{-2}=b^d\frac{1}{(1-x{)}^2}$, $abs(x)<1$일 때

즉, 우리는 다음을 얻는다.

$b^d(1+2x+3x^2+\cdots +(d-1)x^{d-2}+d{x}^{d-1}+(d+1)x^d)\le b^d(1-x{)}^{-2}$, $abs(x)<1$일 때

$(1-x{)}^{-2}$ 또는 ${(1-\frac{1}{b})}^{-2}$는 $d$(깊이)와 무관한 상수이므로, $b>1$인 경우(즉, 분기 계수가 1보다 큰 경우), 깊이 우선 반복적 깊이심화 탐색의 실행 시간은 $O(b^d)$이다.

예시

$b=10$ 및 $d=5$의 경우 숫자는 다음과 같다.

$\sum _{i=0}^5(5+1-i)10^i=6+50+400+3000+20000+100000=123456$

전체적으로, 깊이 $1$부터 깊이 $d$까지의 반복적 깊이심화 탐색은 $b=10$일 때 깊이 $d$까지의 단일 너비 우선 또는 깊이 제한 탐색보다 약 $11\mathrm{\%}$만 더 많은 노드를 확장한다.

분기 계수가 높을수록 반복적으로 확장되는 상태의 오버헤드가 낮아지지만,^:6 분기 계수가 2일 때도 반복적 깊이심화 탐색은 완전한 너비 우선 탐색보다 약 두 배만 더 오래 걸린다. 이는 반복적 깊이심화의 시간 복잡도가 여전히 $O(b^d)$임을 의미한다.

공간 복잡도

IDDFS의 공간 복잡도는 $O(d)$이다.^:5 여기서 $d$는 목표의 깊이이다.

증명

IDDFS는 어떤 시점에서 깊이 우선 탐색에 참여하므로, 확장하는 트리의 분기를 나타내는 노드 스택만 저장하면 된다. 최적 길이의 해답을 찾기 때문에 이 스택의 최대 깊이는 $d$이고, 따라서 최대 공간량은 $O(d)$이다.

일반적으로, 반복적 깊이심화는 탐색 공간이 크고 해답의 깊이를 알 수 없을 때 선호되는 탐색 방법이다.

예시

다음 그래프의 경우:

파일:Graph.traversal.example.svg

A에서 시작하는 깊이 우선 탐색은, 표시된 그래프에서 왼쪽 간선이 오른쪽 간선보다 먼저 선택되고, 이전에 방문한 노드를 기억하고 반복하지 않는다고 가정할 때(작은 그래프이기 때문에), 다음 순서로 노드를 방문한다: A, B, D, F, E, C, G. 이 탐색에서 가로지르는 간선은 트레모 트리를 형성하는데, 이는 그래프 이론에서 중요한 응용을 가진 구조이다.

이전에 방문한 노드를 기억하지 않고 동일한 탐색을 수행하면 A, B, D, F, E, A, B, D, F, E 등의 순서로 노드를 영원히 방문하게 되며, A, B, D, F, E 주기(cycle)에 갇혀 C나 G에 도달하지 못한다.

반복적 깊이심화는 이 루프를 방지하고 위와 같이 왼쪽에서 오른쪽으로 진행한다고 가정할 때 다음 깊이에서 다음 노드에 도달한다.

• 깊이 0: A
• 깊이 1: A, B, C, E

(반복적 깊이심화는 이제 C를 보았지만, 기존 깊이 우선 탐색에서는 보지 못했다.)

• 깊이 2: A, B, D, F, C, G, E, F

(여전히 C를 보았지만, 나중에 나온다. 또한 E를 다른 경로를 통해 보고, F로 두 번 되돌아간다.)

• 깊이 3: A, B, D, F, E, C, G, E, F, B

이 그래프의 경우, 깊이가 추가될수록 "ABFE" 및 "AEFB" 두 개의 주기가 알고리즘이 포기하고 다른 분기를 시도하기 전에 단순히 길어진다.

관련 알고리즘

반복적 깊이심화와 유사한 탐색 전략은 깊이 제한 대신 경로 비용 제한을 증가시켜 작동하는 반복적 길이 늘림 탐색이라고 불린다. 이는 경로 비용이 증가하는 순서로 노드를 확장한다. 따라서 처음 만나는 목표는 가장 저렴한 경로 비용을 가진 목표이다. 그러나 반복적 길이 늘림 탐색은 상당한 오버헤드를 발생시켜 반복적 깊이심화보다 덜 유용하다.

반복적 깊이심화 A*는 A* 알고리즘에서 계산되는 것과 유사한 "f"-값을 기반으로 반복적 깊이심화를 수행하는 최상 우선 탐색이다.

양방향 IDDFS

IDDFS에는 양방향 대응 알고리즘이 있다.^:6 이 알고리즘은 두 가지 탐색을 번갈아 수행한다. 하나는 소스 노드에서 시작하여 유향 아크를 따라 이동하고, 다른 하나는 타겟 노드에서 시작하여 유향 아크를 반대 방향으로(아크의 헤드 노드에서 아크의 테일 노드로) 진행한다. 탐색 프로세스는 먼저 소스 노드와 타겟 노드가 동일한지 확인하고, 그렇다면 단일 소스/타겟 노드로 구성된 자명한 경로를 반환한다. 그렇지 않으면, 전방 탐색 프로세스는 소스 노드의 자식 노드(집합 $A$)를 확장하고, 후방 탐색 프로세스는 타겟 노드의 부모 노드(집합 $B$)를 확장하며, $A$와 $B$가 교차하는지 확인한다. 교차한다면 최단 경로가 발견된 것이다. 그렇지 않으면 탐색 깊이가 증가하고 동일한 계산이 수행된다.

이 알고리즘의 한계는 홀수 개의 아크로 구성된 최단 경로가 감지되지 않는다는 것이다. 최단 경로 $⟨s,u,v,t⟩$가 있다고 가정해 보자. 깊이가 두 개의 홉에 도달하면 전방 탐색은 $u$에서 $v$로 진행하고, 후방 탐색은 $v$에서 $u$로 진행한다. 그림으로 보면, 탐색 경계가 서로를 통과하며, 대신 짝수 개의 아크로 구성된 최적이 아닌 경로가 반환된다. 이는 아래 다이어그램에 나와 있다.

파일:Bidirectional iterative deepening depth-first search search frontier pass through each other.png

양방향 IDDFS

공간 복잡도와 관련하여, 이 알고리즘은 두 탐색 프로세스가 만나는 중간 노드의 존재를 감지하기 위해 전방 탐색 프로세스에서 가장 깊은 노드에 색을 칠한다.

양방향 IDDFS를 적용하는 추가적인 어려움은 소스 노드와 타겟 노드가 서로 다른 강하게 연결된 구성 요소, 예를 들어 $s\in S,t\in T$에 있고 $S$를 떠나 $T$로 들어가는 아크가 없는 경우, 탐색이 결코 끝나지 않는다는 것이다.

시간 및 공간 복잡도

양방향 IDDFS의 실행 시간은 다음과 같다.

$2\sum _{k=0}^{n/2}{b}^k$

그리고 공간 복잡도는 다음과 같다.

$b^{n/2},$

여기서 $n$은 최단 $s,t$ 경로의 노드 수이다. 반복적 깊이심화 깊이 우선 탐색의 실행 시간 복잡도는 $\sum _{k=0}^n{b}^k$이므로, 속도 향상은 대략 다음과 같다.

$\frac{\sum _{k=0}^n{b}^k}{2\sum _{k=0}^{n/2}{b}^k}=\frac{\frac{1-b^{n+1}}{1-b}}{2\frac{1-b^{n/2+1}}{1-b}}=\frac{1-b^{n+1}}{2(1-b^{n/2+1})}=\frac{b^{n+1}-1}{2(b^{n/2+1}-1)}\approx \frac{b^{n+1}}{2b^{n/2+1}}=\Theta (b^{n/2}).$

의사코드

function Find-Shortest-Path(s, t) is
   if s = t then
       return <s>
   (B, F, Vf, Vb) := (empty stack, ∅, ∅, ∅)
   (Δ, lf, lb) := (0, 0, 0)
   forever do
       (F, Vf) := (∅, ∅)
       Depth-Limited-Search-Forward(s, Δ, F, Vf)
       if |Vf| = lf then
           return nil
       (lf, Vb) := (|Vf|, ∅)
       μ := Depth-Limited-Search-Backward(t, Δ, B, F, Vb)
       if μ $\ne$ nil then
           return Build-Path(s, μ, B, G)
       Vb := ∅
       μ := Depth-Limited-Search-Backward(t, Δ + 1, B, F, Vb)
       if μ $\ne$ nil then
           return Build-Path(s, μ, B, G)
       if |Bb| = lb  then
           return nil
       (lb, Δ) := (|Vb|, Δ + 1)

function Build-Path(s, μ, B) is
    π := Find-Shortest-Path(s, μ) (Recursively compute the path to the relay node)
    Pop(B)
    return π $\circ$ B (Append the stack starting from its top.)

function Depth-Limited-Search-Forward(u, Δ, F, V) is
    if u ∈ V then
        return
    V := V ∪ {u}
    if Δ = 0 then
        F := F ∪ {u} (Mark u as a frontier node.)
        return
    foreach child of u do
        Depth-Limited-Search-Forward(child, Δ − 1, F, V)

function Depth-Limited-Search-Backward(u, Δ, B, F, V) is
    if u ∈ V then
        return nil
    Push(B, u)
    if Δ = 0 then
        if u ∈ F  then
            return u (Reached the marked node, use it as a relay node)
        Pop(B)
        return nil
    V := V ∪ {u}
    foreach parent of u do
        μ := Depth-Limited-Search-Backward(parent, Δ − 1, B, F, V)
        if μ $\ne$ nil then
            return μ
    Pop(B)
    return nil