[그래프] Graph6: BFS 양방향 탐색, IDS : 15-퍼즐

1. 최단 경로 전략

 

너비 우선 탐색은 최단 경로 문제를 푸는 가장 직관적이고 유명한 방법이지만,

 

모든 최단 경로 문제를 너비 우선 탐색만으로 풀 수 있는 것은 아니다.

 

문제에 따라서는 너비 우선 탐색보다 다른 탐색 알고리즘이 더 강력한 경우가 있다.

 

 

 

 

2. 15- 퍼즐

 

7	8	4	1
2	3		5
6	9	10	11
12	13	14	15

=>

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15

 

 

4 X 4 격자에 끼워진 열다섯 개의 숫자 타일을 순서에 맞게 맞추는 퍼즐이다.

 

빈 칸에 상하좌우로 인접한 타일 하나를 빈 칸으로 밀어넣는 것을 한번의 움직임이라 할 때,

 

이 퍼즐을 해결하기 위해 필요한 최소 움직임을 구하는게 오늘의 목적이다.

 

 

 

 

이 문제를 풀기 위한 첫번째 단계는 게임판의 상태를 정점으로 표현한 그래프를 만드는 것이다.

 

이와 같은 그래프를 상태 공간(state space) 라고 부른다.

 

게임판에는 빈 칸까지 포함해 열여섯 개의 타일이 있으므로, 상태 공간은 16!개의 정점을 갖게 된다.

 

한 번의 움직임으로 한 상태를 다른 상태로 바꿀 수 있을 때 두 정점을 간선으로 연결한다.

 

따라서 각 정점에는 최대 네개의 이웃 정점이 있다.

 

아래는 상태 공간의 일부를 보여주는 예시이다.

 

현재:

7	8	4	1
2	3		5
6	9	10	11
12	13	14	15

 

위:

7	8		1
2	3	4	5
6	9	10	11
12	13	14	15

아래:

7	8	4	1
2	3	10	5
6	9		11
12	13	14	15

왼쪽:

7	8	4	1
2		3	5
6	9	10	11
12	13	14	15

오른쪽:

7	8	4	1
2	3	5
6	9	10	11
12	13	14	15

 

 

 

 

 

3. BFS

 

암시 그래프를 너비 우선 탐색하여 15-퍼즐의 최소 움직임 수를 구할 수 있다.

 

게임판 = state 객체

 

getAdjacent = 상하좌우 state 모음

 

너비 우선 탐색에서 각 정점의 방문 여부를 저장하던 배열이 없어지고, STL map을 사용하였다.

 

코드는 다음과 같다.

 

이는 bfs와 거의 똑같다는것을 알 수 있다.

class State
{
    public:
    vector<State> getAdjacent() const;
    bool operator < (const State& rhs) const;
    bool operator == (const State& rhs) const;
};
 
typedef map<State, int> StateMap;
 
int bfs(State start, State finish) 
{
    if(start == finish) return 0;
    
    StateMap c;
 
    queue<State> q;
    q.push(start);
    c[start] = 0;
 
    while(!q.empty())
    {
        State here = q.front();
        q.pop();
        int cost = c[here];
 
        vector<State> adjacent = here.getAdjacent();
        for(int i = 0; i < adjacent.size(); ++i)
        {
            if(c.count(adjacent[i]) == 0)
            {
                if(adjacent[i] == finish) return cost + 1;
                c[adjacent[i]] = cost + 1;
                q.push(adjacent[i]);
            }
        }
    }
    return -1;
}

BFS 효율성 분석

너비 우선 탐색의 시간 복잡도는 O(|V| + |E|) 이다.

 

하지만 전체를 탐색하지 않으므로 계산을 달리 해야한다.

 

위 수행 시간은 현재 정점의 인접한 정점들을 검사하는 반복문이 지배한다.

 

한 정점에는 최대 상수개의 정점만 인접할 수 있기 때문에 

 

실질적으로 전체 시간 복잡도는 너비 우선 탐색이 방문하는 정점의 수에 비례하게 된다.

 

 

정점의 수에 영향을 주는것은 최단 거리 d 이다.

 

목표 정점이 가까우면 빨리 종료되고

 

멀리 있으면 늦게 종료된다

 

 

방문하는 정점의 개수에 영향을 미치는 다른 요소는 탐색의 분기 수(branching factor) b 이다.

 

분기 수는 경로의 길이가 하나 늘어날 때마다 닿을 수 있는 정점의 개수가 몇 배로 늘어나는지를 나타낸다.

 

최대 4개의 접점이 생기므로 이론상으로 만나는 정점의 개수가 네 배로 증가하겠지만

 

시작 정점을 제외한 모든 정점에서는 이 중 하나의 돌아가는 것이므로 실제 분기수는 3보다 작은 어떤 수 일 것이다.

 

 

최단 거리와 탐색의 분기 수 가 있으면 대강 몇개를 방문하는지 어림짐작할 수 있다.

 

시작점으로 부터 최단 거리가 i인 정점은 대략 b^i개가 있을 것이다. 

 

b가 2 이상일 때 0 부터 d까지의 모든 거리에 대해 b^i를 더하면 대략 O(b^d) 가 된다.

 

 

 

 

 

4. 양방향 탐색 (bidirectional search)

좀더 효율적인 방법으로는 양방향 탐색이 있다.

 

시작 정점에서 시작하는 정방향 탐색 목표 정점에서 시작해 거꾸로 올라오는 역방향 탐색을 동시에 하면서,

 

이 둘이 가운데서 만나면 종료하는 것이다,

 

이는 분기수에 따른 정점이 지수적으로 증가하는것을 많이 줄여준다.

 

탐색의 분기 수가 3 거리가 20일때 대략 너비탐색의 3만배 정도 탐색할 정점의 개수가 줄어든다.

 

 

정방향과 역방향 둘다 같은 큐에 넣지만 최단 거리를 저장할때 정방향은 양수, 역방향은 음수로 저장한다.

 

인접한 상태를 검사했는데, 서로 부호가 다르다는 것은 거기서 만난것을 의미한다.

 

class State;
 
int sgn(int x)
{
    if(!x)
        return 0;
    return x>0 ? 1: -1;
}
 
int incr(int x) 
{
    if(x<0)
        return x-1;
    return x+1;
}
 
int bidirectional(State start, State finish)
{
    map<State, int> c;
    queue<State> q;
    if(start == finish) return 0;
    
    q.push(start); c[start] = 1;
    q.push(finish); c[finish] = -1;
 
    while(!q.empty())
    {
        State here = q.front();
        q.pop();
 
        vector<State> adjacent = here.getAdjacent();
        for(int i = 0; i < adjacent.size(); i++)
        {
            map<State, int>::iterator it = c.find(adjacent[i]);
            if(it == c.end())
            {
                c[adjacent[i]] = incr(c[here]);
                q.push(adjacent[i]);
            }
            else if(sgn(it->second) != sgn(c[here]))
                return abs(it->second) + abs(c[here]) -1;
        }
    }
    return -1;
}

 

효율성 분석

양방향 탐색은 너비 우선 탐색보다 훨씬 적은 수의 정점만을 방문하고도  답을 찾을 수 있다.

 

두 방향 탐색은 각각 깊이 d/2 까지 너비 우선 탐색을 진행하기 때문에

 

b^(d/2) 개의 정점들을 방문하게 된다.

 

이들은 깊이가 d/2인 너비 우선 탐색을 두 번 하는 것과 같은 시간 복잡도를 가지고,

 

따라서 전체 시간 공간 복잡도는 O(b^(d/2)) 가 되어 bfs보다 훨씬 효율적이다.

 

 

유의 사항

양방향 탐색은 여러 경우에 굉장히 유용하지만 항상 사용할 수 있는 것은 아니다.

 

정방향 간선을 찾아내기는 쉽지만 각 정점마다 가능한 역방향 간선이 아주 많아서 역방향 탐색의 분기 수가 지나치게 큰 경우에는

 

사용하기 어렵다

 

15-퍼즐은 상태 공간이 양방향 그래프이기 때문에 적용하기 좋은 예이다.

 

양방향 탐색은 bfs보다 메모리 사용량이 훨씬 적다.

 

하지만 위처럼 사용하기 어려운 경우나 최단 거리가 너무 클경우는 다음과 같은 탐색을 사용한다.

 

5. 점점 깊어지는 탐색 (IDS)

 

대부분 수행 시간을 줄이기 위해 메모리를 더 사용하는 전략을 사용한다.

 

하지만 메모리가 물리적 메모리 양을 넘어가면 시간보다 메모리를 신경써야한다.

 

메모리는 쉽게 늘렸다 줄였다 할 수 없기 때문이다.

 

양방향 탐색에서도 방문하는 정점 수는 최단 거리에 따라 지수적으로 증가하기 때문에 메모리 문제가 발생할 수 있다.

 

따라서 규모가 큰경우 DFS 기반으로하는 방법을 사용한다.

 

 

 

dfs는 발견한 즉시 방문한다. 따라서 큐같은 자료 구조에 메모리를 저장할 일이 발생하지 않는다.

 

거기에 방문 여부를 기록하지 않으면 메모리를 거의 사용하지 않는다.

 

하지만 이와 같은 dfs는 다음과 같은 이유 때문에 최단경로를 찾기 힘들다

- dfs는 방문 순서 때문에 목표상태를 찾는다고해도 최단 경로인지 모름

- 방문을 기록하지 않기 때문에 한상태를 두번 아니면 사이클에 빠질 수 있다.

 

 

이와 같은 문제를 해결하기 위해 고안된 것이 점점 깊어지는 탐색(Iteratively Deepening Search, IDS)

 

ids는 임의의 깊이 제한 l을 정하고 이 제한보다 짧은 경로가 존재하는지를 우선 탐색으로 확인한다

 

답을 못찾을시 l을 늘려서 다시 시도한다.

 

 

다음은 ids의 구현이다.

 

지금까지 찾아낸 최단 경로의 길이를 best에 저장해두고

지금 경로가 best이상이면 탐색을 종료한다.

best를 깊이 한계에 1 더한 것으로 설정하고,

탐색 후에 이값이 깊이 한계 이하로 내려왔는지 확인하기만 하면 된다.

 

int best;
 
void dfs(State here, const State& finish, int steps)
{
    if(steps >= best) return;
    if(here == finish) {best = steps; return;}
    vector<State> adjacent = here.getAdjacent();
    for(int i = 0; i < adjacent.size(); i++)
       dfs(adjacent[i], finish, steps + 1);
}
 
int ids(State start, State finish, int growthStep)
{
    for(int limit = 4;;limit += growthStep)
    {
        best = limit + 1;
        dfs(start, finish, 0);
        if(best <= limit) return best;
    }
    return -1;
}

 

추가적인 최적화

최적해를 전역변수에 저장하고, 이보다 크면 가지치기하는 기법 을 보면

 

ids 는 조합 탐색과 관계있다.

 

때문에 휴리스틱을 이용하여 더 최적화 시킬 수 있다.

 

목표 정점까지 도달하기 위해 필요한 움직임 수의 하한을 계산한뒤,

 

이것이 지금까지 찾은 최단 거리나 깊이제한 이상이라면 탐색을 종료하는 것이다.

 

 

모든 타일에 대해 현재 위치와 목표위치 사이의 맨해튼 거리 를 더하는 것이다

(맨해튼 거리: 두 2차원 좌표 사이의 거리 |x1-x2| + |y1-y2|)

 

빈칸을 한 번 움직일때마다 타일 하나의 위치가 가로 1 혹은 세로로 1 바뀌기 때문에

 

앞으로의 움직임의 하한이 된다.

 

따라서 State의 멤버 함수로 이와 같은 값을 반환하는 estimate()가 있으면 

 

best보다 큰지 확인하는 if 문을 다음과 같이 변경할 수 있다

if(steps + here.estimate() >= best) return;

 

효율성 찾기

메모리를 적게 사용하는 dfs의 장점을 그대로 살리면서도, 최단 거리보다 먼 정점들은 탐색하지 않는다는 

 

너비 우선 탐색의 장점까지 가지고 있다.

 

하지만 한 정점을 여러번 반복해서 방문한다는 낭비가 생긴다.

 

 

목표 상태까지의 최단 거리가 d이고, 탐색의 분기수가 b라고하자.

 

이때 깊이 제한을 1 에서 시작해 1씩 늘려간다면,

 

시작점은 d+1번 방문되고,

 

시작점으로부터의 최단 거리가 1인 상태들은 d번 방문되고,

 

최단 거리가 2 인 상태들은 d-1번 방문된다

 

이를 풀어쓰면 다음과 같다.

 

 

(d+1)*b^0 + d*b^1 + (d-1)b^2 + ... + 2*b^(d-1) + 1*b^d

 

 

왼쪽으로 갈 때마다 방문 횟수는 1씩 늘고, 오른쪽으로 갈때마다 상태의 수는 b배씩 늘어난다.

 

이럴 때는 지수적으로 증가하는 b^d가 전체를 지배하기 때문에 결과적으로 dfs이 방문하는 상태의 수는 O(b^d)가 된다.

 

 

너비 우선 탐색이랑 같은 O(b^d) 이지만

 

상태를 방문했는지 여부를 확인하는 자료 구조를 유지해야하고,

 

가지치기 기법을 적용하기 쉽다는 점에서 점점 깊어지는 탐색이 더 빠른 경우도 많다.

 

 

점점 깊어지는 탐색의 메모리는 큐를 사용하지 않으므로 함수 콜 스택이 유일하다

 

따라서 최대 메모리 사용량은 탐색의 깊이에 비례하게 되고, O(d)의 메모리를 사용한다.

 

 

휴리스틱을 적용한 점점 깊어지는 탐색은 들쭉날쭉하지만 전반적으로 양방향 탐색에 뒤쳐지지 않는다.

 

 

6. 탐색 방법 선택하기

탐색 방법의 장단점을 고려하여 선택해야한다.

 

1. 상태 공간에서의 최단 경로를 찾는 경우, bfs 최우선 고려

    직관적이고 구현도 간단, 탐색의 깊이 한계가 정해져있지 않거나 너무 깊어서 메모리 사용량이 너무 큰지 확인

 

2. 상태 공간에서의 최단 경로를 찾는데, 탐색의 최대 길이가 정해짐, bfs하기에 메모리, 시간이 부족 = 양방향 탐색

    단, 목표상태에서 역방향으로 움직이기 쉬워야함

 

3. 위 두 탐색이 모두 메모리를 많이 사용하거나 너무 느린경우,

    최적화를 할 거리가 더 많을 경우, 점점 깊어지는 탐색사용

  

 

 

7. 15-퍼즐 State 객체의 구현

 

이 객체를 표현하는 자료 구조의 선택은 프로그램의 효율성에 큰 영향을 미친다.

 

유의할점

- 여러 연산을 가능한한 효율적으로 구현해야한다. 특히 비교연산자 나 인접한 상태 표현 계산은 반복적으로 수행되므로

- 가능한한 적은 메모리 사용. 상태객체는 큐에 들어가고 map의 key에도 들어간다. 복사하는데 시간과, 메모리 신경써야함.

 

 

15-퍼즐의 가장 적절한 상태 표현 방식은

 

단순한 방법:

    4*4 2차원 배열 : 어떤 위치에 무슨 타일인지 직접 접근, 인접한 상태 표현 쉬움, 그러나 메모리 양 많이 차지함

 

메모리 사용량 줄이는 방법:

    일대일 대응 함수를 이용 => 게임판의 상태를 [0, 16! -1] 범위의 정수로 표현가능

    이것은 64비트 정수 표현 범위 내이기 때문에, 정수 하나로 표현 가능하다.

    하지만 매번 대응시키고 상태를 복구하는 작업을 반복해야함, 인접한 상태를 얻는 연산에서 너무 느려짐

 

비트 마스크 이용:

    크기 16인 배열을 쓸 때 각 값은 0에서 15 사이 => 4비트 표현 가능

    비트 마스크를 사용하면 16칸에 대한 정보를 64 비트 정수 하나로 표현 가능

   상태 비교, map의 키로 사용 용이

    인접한 상태들을 찾기 위해서는 빈 칸과 인접한 타일을 교환해야하는데 반복문으로 찾는 연산이 필요하다.

    이는 부가적으로 현재 빈칸의 위치를 저장하는 변수를 덧붙임으로써 반복문으로 찾는 연산없이 수행할 수 있다.

 

 

 

 

 

 

 

- 알고리즘 문제해결전략 898p

 

[그래프] HANOI4 하노이의 네 탑