[알고리즘] 상태 공간 트리의 탐색

1. 상태 공간 트리

- 문제 해결 과정의 중간 상태를 각각 한 노드로 나타낸 트리.

- TSP를 예로 들어 상태 공간 트리를 설명함.

 

TSP

- 그래프에서 모든 정점을 순회하고 돌아오는 사이클을 해밀토니안 사이클이라 함.

- 완전 그래프에서 해밀토니안 사이클은 수없이 많은데 TSP는 그중 짧은 것을 찾는 문제.

- TSP의 형태는 다양하지만 이차원 평면상에 n개의 정점이 있고, 이 정점들로 구성된 가장 짧은 해밀토니안 사이클을 찾는 문제가 가장 단순한 형태의 TSP 문제.

- 첫 번째 그림은 TSP 예로 평면에 6개의 정점이 존재함. 두 번째와 세 번째 그림은 해밀토니안 사이클의 예.  이 중 오른쪽의 그림은 모든 가능한 해밀토니안 사이클 중 가장 짧은 해밀토니안 사이클, 즉 최적해.

- TSP는 임의의 두 정점 u,v를 잇는 두 간선(u,v)와 (v,u)의 길이가 동일함.

- 즉, 간선이 하나 있으면 이것은 양방향으로 동일한 길이를 가짐. 이것을 대칭형 TSP라 함. 이 성질이 만족되지 않는 비대칭 TSP도 있음.

- 어떤 비대칭 TSP의 정점들 간 거리를 인접 행렬로 나타낸 것.

- 여기서는 두 정점 사이의 두 간선 길이가 반드시 같지는 않음.

- TSP 예를 대상으로 모든 경우의 수를 탐색하는 알고리즘.

- 과정을 트리로 나타낸 것.

- 이런 방식으로 모든 경우의 수를 탐색하는 것을 사전식 탐색이라 함.

- 사전에서 1페이지부터 끝까지 알파벳 순으로 모든 단어를 검사하는 것과 같음.

- 각 노드는 하나의 부분 경로를 나타내는 것으로, 문제 풀이 과정의 진행 상황 또는 상태를 나타내고 있음.

- 여기서 부분 경로는 수열로 표시되었음.

- 트리의 각 노드가 방문된 순서를 나타냄.

- 리프 노드 아래의 수는 완성된 해밀토니안 사이클의 길이.

- 정점들이 순서대로 모두 나열되어 있는데 이는 대응되는 해밀토니안 사이클.

- 모든 정점을 방문하고 돌아오는 사이클은 어디서 시작하든 상관이 없으므로 시작점을 1로 고정함.

- 이런 식으로 5개의 정점을 가진 TSP의 최적해를 찾으려면 모두 4!, 즉 24개의 해를 검사해보아야 함.

- 이렇게 문제 풀이가 진행된 상태를 각각 노드로 나타냈다고 해서 상태 공간 트리라 함.

 

2. 백트래킹

- DFS는 백트래킹의 골격을 이루는 알고리즘.

- 백트래킹은 DFS와 같은 방식으로 탐색하는 모든 방법을 뜻함.

- 탐색을 하다가 더 갈 수 없으면 왔던 길을 되돌아가 다른 길을 찾는다고 해서 이런 이름이 붙음.

- 백트래킹은 주로 재귀적으로 구현함.

- 백트래킹 알고리즘마다 DFS에서 조금씩 변형은 일어나지만 기본적으로는 모두 DFS의 범주에 속함.

- 백트래킹 알고리즘이 상태 공간 트리를 명시적으로 만드는 것은 아니지만, 알고리즘의 진행 과정은 상태 공간 트리의 루트에서 시작해서 DFS 방식으로 탐색을 해나가는 것과 대응됨.

 

 미로 찾기 문제

- 백트랙킹의 간단한 예시로는 미로 찾기 문제가 있음.

 

- 다음의 그림은 미로 찾기 문제의 한 예시임.

- 이렇게 생긴 미로가 있을 때 S는 시작 지점이고, T는 목표 지점임.

 

- 아래의 그림은 이 미로를 탐색하다가 선택을 해야하는 지점, 즉 분기점들을 정점으로 나타냄.

 

- 이 미로 찾기 문제의 탐색 과정은 이러한 모습의 상태 공간 트리로 표현할 수 있음.

- 백트래킹은 이렇게 가보고 되돌아오고를 반복하는 것임.

- 운이 좋으면 시행착오를 덜 거치고 목적지에 도달할 것이고, 최악의 경우에는 모든 경우를 다 거친 다음 목적지에 도착할 수 있음.

 

미로 찾기를 위한 백트래킹 알고리즘

- 알고리즘이 끝난 후 S에서 T에 이르는 경로를 알려면 T에서 시작해 prev[]를 통해 따라가면 S에 이르게 됨.

- 이의 역방향이 해답 경로.

- 이 알고리즘은 사실상 DFS와 같음.

maze ( v )
{
    visited[v] = YES;
    if ( v = T ) then { return "성공" ; }    // 끝냄
    for each x ∈ L(v)
        if ( visited[x] = NO ) then {    // L(v) : 정점 v와 인접한 정점 집합
            prev[x] <- v;
            maze(x);
        }
}

 

 색칠 문제

- 여러 개의 구역으로 구성되어있고, k개의 색상을 사용해서 인접한 정점은 같은 색상이 칠해지지 않도록 그래프를 칠할 수 있는지 묻는 문제임.

 

- 오른쪽의 그림은 서로 인접한 구역을 화살표로 표시함.

 

- 아래의 그림은 각 구역을 정점 하나로 표현하고 인접한 구역끼리 간선으로 연결하고, 보기 편하도록 정리함.

 

색칠 문제를 위한 백트래킹 알고리즘

- k개의 색상으로 그래프를 칠할 수 있는지 체크하는 백트래킹 알고리즘임.
- 칠해야 할 정점의 총수는 n임.

- 최초에는 kColoring(1,1)을 호출함.

- kColoring(i, c)를 호출하는 시점에는 정점 1부터 i-1까지가 k개 또는 그 이하의 색상으로 칠해져 있음.

- 이 상태에서 정점 i에 색상 c를 칠하고 끝까지 잘 마무리할 수 있는지 조사하는 알고리즘.

- 우선 정점 i에 색상 c를 칠하면 지금까지 칠해놓은 정점들과 색이 충돌하지 않는지 체크함.

- 이를 위해서는 정점 i에 인접하면서 이미 칠이 되어 있는 정점 중 색상 c로 칠해진 정점이 있는지 확인함. ( valid(i, c) )

- 이 단계를 통과하면 다음 과정을 진행함.

- 정점 i가 마지막 정점이면 성공적으로 완료되었음을 선언함.

- 정점 i가 마지막 정점이 아니면 다음 정점을 하나 선택해 색상을 하나씩 칠해보는 과정을 반복함.

kColoring(i, c)
// i : 정점, c : color
// 질문 : 정점 i-1까지는 제대로 칠이 된 상태에서 정점 i를 색상 c로 칠하려면 K개의 색으로 충분한가?
{
    if ( valid( i,c) ) then {
        color[i] <- c;
        if ( i = n ) then { return TRUE ; }
        else {
            result <- FALSE;
            d <- 1;    // d : color
            while ( result = FALSE and d ≤ k ) {
                result <- kColoring( i+1, d);
                d++;
            }
        }
        return result;
    } else { return FALSE; }
}

valid(i, c)
// i : 정점, c : color
// 질문 : 정점 i-1까지는 제대로 칠이 된 상태에서 정점 i를 색상 c로 칠하면 이들과 색이 겹치지 않는가?
{
    for j <- 1 to i-1 {
        // 정점 i와 j 사이에 간선이 있고, 두 정점이 같은 색상이면 안 됨.
        if ( (i,j) ∈ E and color[j] = c ) then return FALSE;
    }
    return TRUE;
}

 

상태 공간 트리

- 그래프를 세 가지 색으로 칠할 수 있는지 알고리즘을 사용해서 체크하는 과정을 상태 공간 트리로 나타낸 것.

- 각 노드에 표시된 2개의 수는 함수 kColoring()의 두 입력 값을 나타냄.

- X로 표시된 노드들은 해당 함수 호출이 FALSE로 끝난 경우.

- 대부분 백트래킹은 그리 효율적인 선택이 아니지만 이런 식으로 가지치기가 일어나므로 모든 경우의 수를 확인하는 알고리즘은 아님.

 

3. 한정 분기

- 사전식 탐색을 할 때는 탐색할 경우의 수가 (n-1)!에 비례해서 늘어나므로 정점의 수 n이 조금만 커져도 현실적인 시간에 탐색이 불가능함.

- 이 탐색 과정을 잘 살펴보면 상당한 비율의 정점을 방문하지 않아도 된다는 사실을 발견할 수 있음.

ex ) 어떤 부분 경로의 길이가 지금까지 찾아놓은 가장 좋은 해를 초과한다면 그 부분 경로에서 더 이상 진행을 해보아야 희망이 없음.

- 이제부터 예로 보일 TSP의 한정 분기 방법은 이 원리를 조금 더 개량해서 보지 않아도 될 정점 수를 가능하면 많이 늘림.

 

한정 분기

- 1960년 랜드와 도이가 제안한 방법. 처음에는 선형 계획법을 해결하기 위해 제시되었음.

- 한정 분기의 영어 표현은 Branch and Bound로 분기를 한정적으로 하여 쓸데없는 시간 낭비를 줄이는 방법임.

 

한정 분기를 위한 두 가지 요소

① 모든 경우의 수를 나열하는 방법이 있어야 함.

② 분기를 더 이상 할 필요가 없음을 판단할 수 있는 방법을 제공해야 함.

- 최적해를 찾을 가능성이 없다는 판단이 서면 더 이상 진행하지 않고 다음 후보를 찾음.

- 이 판단은 주로 지금까지 찾은 가장 좋은 해보다 더 좋아질 수 있는지로 이루어짐.

- 이것을 가지치기(Prunning)라고 함.

 

가지치기의 원리

- 어느 시점에 가능한 선택이 여섯 가지가 있을 때, 선택을 해도 최적해를 찾을 확률이 없다면 이들은 선택 대상에서 제외할 수 있음.

- 그림에서 검은색으로 칠해진 경우들. 한정 분기는 이런 선택을 해야 할 차례가 오면 그냥 넘김. (가지치기)

- 즉, 한정된 분기를 이용하여 쓸데없는 시간 낭비를 줄이고 최적해에 빨리 이르고자 함.

- 지금까지 찾은 가장 좋은 해의 품질이 좋을수록 탐색 대상이 되는 경우는 줄어들게 됨.

- 즉, 가지치기가 더 많이 일어나서 시간을 절약할 수 있음.

- 그러므로 한정 분기에서는 초기에 좋은 해를 찾는 것이 유리함.

- 가장 좋지 않는 경우는 초기에 나쁜 해가 나오고, 점차 해가 개선되는 경우. 이 경우에는 거의 모든 해를 확인해야할 수도 있음.

- 실용적인 방법인 휴리스틱 알고리즘을 사용해 괜찮은 해를 구한 다음 이것을 기준해로 사용하는 것.

 

- 특히, 컴퓨터 과학의 난제인 NP-하드 문제들은 비교적 쓸 만한 알고리즘들이 많이 연구되어 있으므로 이들을 활용하면 됨.

- 예를 들어, TSP 문제의 경우 LK 알고리즘을 쓰면 정점이 몇 백 개 정도 되는 문제에 대해서는 몇 번만 수행하면 최적해를 찾는 수준에 이르러 있음.

- 몇 천 개짜리 문제는 LK계열의 알고리즘과 유전 알고리즘을 결합하면 몇 번의 수행으로 최적해를 찾는 수준.

 

슈퍼 컴퓨터를 이용해 아주 큰 TSP 문제의 최적해를 구할 때 쓸 수 있는 방법

- 이 문제에 대해 지금까지 다양한 방법으로 시도한 결과가 알려져 있으면 그중 가장 좋은 해를 기준해로 삼음.

- 슈퍼 컴퓨터에 있는 수만 개(또는 수천 개, 수십만 개)의 CPU에 서로 다른 경우들을 분담시킴.

- 수행 중 슈퍼 컴퓨터 내의 어떤 CPU에서 현재까지 기준해보다 좋은 해가 발견되면 이것을 새로운 기준해로 삼고 다른 모든 CPU에도 알려 갱신함.

- 큰 문제에 대해서는 몇 년 동안 계속 수행될 수도 있는데 이 기간 중에 현재 슈퍼 컴퓨터가 사용하고 있는 기준해보다 더 좋은 해를 다른 연구자가 발견하면 모든 CPU가 이것을 기준해로 갱신할 수 있도록 함.

 

4. A* 알고리즘

- A* 알고리즘은 그래프의 시작점에서 도착점에 이르는 최단 경로를 찾는 알고리즘.

- 그래프에서 최단 경로 문제에 적용되기도 하지만 상태 공간 트리도 그래프의 일종이므로 적용될 수 있고, 실제로 상태 공간 트리의 탐색에서 A* 알고리즘을 더 많이 사용함.

- 다만, 이미 그래프의 최단 경로를 구하는 다익스트라 알고리즘을 배웠으므로 이와 비교해서 설명하면 A* 알고리즘을 더 쉽게 이해할 수 있음.

 

최적 우선 탐색

- 최적 우선 탐색은 그래프에서 탐색하는 방법 중 하나로, 각 정점이 각자의 매력 함수 값 g(x)를 갖고 있는 경우에 적용됨.

- 시작점에서부터 출발하여 지금까지 방문하지 않은 정점 중 g(x)값이 가장 매력적인 것부터 방문하는 탐색 방법임.

- 최단 경로 계산을 위한 다익스트라 알고리즘과 최소 비용 신장 트리를 위한 프림 알고리즘은 최적 우선 탐색의 한 예.

- 다익스트라 알고리즘에서는 지금까지 계산해놓은 시작점에서 정점 x에 이르는 최단 거리가 g(x)가 됨.

- 프림 알고리즘은 정점 x를 연결하는 최소 비용이 g(x)가 됨.

 

 최단 경로 찾기 문제

- 다익스트라 알고리즘은 최단 경로를 찾는 알고리즘이지만 특정한 목적점 하나를 명시하지 않고 하나의 시작점만 주면 다른 모든 정점에 이르는 최단 거리를 구함.

- 단 하나의 목적점에 이르는 최단 거리만 찾으려면 다익스트라 알고리즘을 수행하다가 목적점에 이르는 최단 경로가 발견되는 순간 탐색을 중단하면 됨.

- 이런 목적으로 다익스트라 알고리즘을 사용할 경우 상당한 낭비가 있을 수 있음.

- 다익스트라 알고리즘은 목적점이 하나가 아니기에 하나의 목적점에 초점을 맞출 수가 없기 때문.

- 이 알고리즘은 잔여 거리를 고려하지 않고 g(x), g(y)만 고려해서 선택하는 알고리즘. 목적점이 하나가 아니기 때문에 잔여 거리를 고려할 수도 없음.

 

- 각 정점에서 잔여 거리를 정확하게 미리 알 수 있는 경우는 거의 없지만, 추정할 수 있는 경우는 많음. 예를 들어, 지도에서 두 지점간의 최단 경로는 좌표상의 직선 거리를 추정치로 사용할 수 있음.

 

A* 알고리즘

- 최적 우선 탐색에 목적점에 이르는 추정치를 같이 사용해서 다음 정점을 선택하는 탐색 방법.

- 이 알고리즘은 두 함수 g(x)와 h(x)를 사용해 판단함. g(x)는 앞에서 사용한 g(x)와 같음. h(x)는 정점 x에서 목적점까지 추정 잔여 거리임.

- 이 추정 거리 h(x)는 정점 x에서 목적점까지 실제 최단 거리보다는 크지 않아야 함.

- 이것이 더 커지면 A* 알고리즘의 핵심을 이루는 이론이 성립되지 않음.

- A* 알고리즘은 g(x) + h(x)값이 가장 작은 정점부터 선택함.

- h(x)가 실제치보다 크지 않다는 조건을 만족하고 모든 정점 쌍 (x, y)에 대하여 h(x) ≤ w(x,y) + h(y)를 만족하면 A* 알고리즘은 최적해를 보장함. 이 성질 h(x) ≤ w(x,y) + h(y)를 단조성이라 함.

 

- 정점을 나타내는 동그라미 안에 있는 수치는 지금까지 계산해좋은 각 정점에 이르는 최단 거리( g(x) ).

- 오른쪽의 그림은 각 정점에서 목적점까지 직선 거리( h(x) )를 나타냄.

- 집합 S에 추가되는 정점은 g(x) + h(x)가 가장 작은 정점이 됨.

- 각 정점의 바깥에 괄호로 표시된 수치가 g(x) + h(x)임.

- 아무리 짧아도 직선 거리보다 짧을 수는 없으므로 h(x)는 실제 최단 잔여 거리보다 크지 않아야 한다는 조건을 만족함.

- h(x,y)가 정점 x와 y 사이의 직선 거리라면 유클리드 공간에서는 (x,y)에 대하여 삼각 부등식 h(x) ≤ h(x,y) + h(y)를 만족함.

- h(x,y) ≤ w(x,y)이므로 h(x) ≤  w(x,y) + h(y)임.

A*(G,s,t)
// G = (V, E) : 주어진 그래프
// s : 시작점, t : 목적점
{
    Q <- V; // Q : S에 속하지 않은 정점 집합
    for each u ∈ Q {
        g[u] <- ∞; f[u] <- ∞;
        h[u] <- 정점 u에서 목적점 t까지 추정 거리;
    }
    g[s] <- 0;
    f[s] <- h[s];
    while ( Q ≠ ∅ ) {
        u <- deleteMin( Q,f);
        if ( u = t ) then return ; // t에 이르는 최단 경로 발견!
        else {
            for each v ∈ L(u) // L(u) : u와 연결된 정점 집합
                if ( v ∈ Q and g[u] + w(u,v) < g[v] ) then {
                    g[v] <- g[u] + w(u,v);
                    prev[v] <- u;
                    f[v] <- g[v] + h[v];
                }
        }
    }
}

deleteMin(Q, f[])
{
    집합 Q에서 f값이 가장 작은 정점 u를 리턴함;
}