[완전 탐색] Combinatorial search 조합 탐색

1. 조합 탐색

 

동적 계획법이나 분할 정복 등의 디자인 패러다임은 적절히 적용 될 때는 매우 유용하나

모든 문제에 적용할 수 없다.

 

이럴 경우 결국 완전 탐색으로 풀어야 한다.

 

완전 탐색은 탐색 공간의 크기에 직접적으로 비례한다.

따라서 문제의 규모가 클 경우 사용하기 어렵다는 문제가 발생한다.

 

이런 완전 탐색을 포함해, 유한한 크기의 탐색 공간을 뒤지면서 답을 찾아내는 알고리즘들을

알고리즘 문제해결 전략에서는 

조합탐색이라고 부른다.

 

조합 탐색에는 다양한 최적화 기법이 있으며

모두 기본적으로 모두 최적해가 될 가능성이 없는 답들을 탐색하는 것을 방지하여

만들어 봐야 할 답의 수를 줄이는 것을 목표로 한다.

 

조합 탐색을 최적화하기 위해 어떤 방법을 사용해야 할지 찾아내는 것은 

문제 자체에 대한 깊은 식견을 요구하며, 속도와 정확도 사이의 상층 관계, 다양한 입력 형태 사이의

상층 관계 등을 모두 고려해야 한다.

 

이렇게 어려운 문제이기 때문에 조합 탐색에는 딱히 정답이 없고

활발하게 연구 되고 있는 주제이다.

 

 

2. 조합 탐색 최적화 기법

 

가지치기(pruning)기법:

탐색 과정에서 최적해로 연결될 가능성이 없는 부분들을 잘라낸다.

현재 상태에서 답의 나머지를 완성했을 때 얻을 수 있는 가장 좋은 답이 지금까지 우리가 알고있는

최적해보다 나쁘다면 탐색을 더 할 필요가 없다.

 

가지치기의 기초적인 예:

지금까지 찾아낸 최적해보다 부분해가 이미 더 나빠졌다면, 현재 상태를 마저 탐색하지 않고 종료해버림.

 

똑똑한 가지치기 기법들은 여러 방법을 이용해 현재 상태에서 얻을 수 있는 가장 좋은 답의 상한을 찾아낸다.

 

좋은 답을 빨리 찾아내는 기법들은 탐색의 순서를 바꾸거나, 탐색 시작 전에 탐욕법을 이용해 적당히 좋은 답을

우선 찾아내면 탐색의 효율이 좋아진다.

 

 

3. 조합 탐색 최적화 기법 적용

외판원 문제(TSP) 를 조합탐색에 적용해보자

1. 뼈대: 완전 탐색

#include <iostream>
#include <vector>
 
using namespace std;
 
const double INF = 1e200;
const int MAX = 30;
int n;
double dist[MAX][MAX];
 
double best;
 
void search(vector<int>& path, vector<bool>& visited, double currentLength)
{
    int here = path.back();
 
    if(path.size() == n) 
    {
        best = min(best, currentLength + dist[here][0]);
        return;
    }
 
    for(int next = 0; next < n; ++next)
    {
        if (visited[next]) continue;
        path.push_back(next);
        visited[next] = true;
        search(path, visited, currentLength + dist[here][next]);
        visited[next] = false;
        path.pop_back();
    }
}
 
double solve()
{
    best = INF;
    vector<bool> visited(n, false);
    vector<int> path(1, 0);
    visited[0] = true;
    search(path, visited, 0);
    return best;
}

 

2. 최적해 보다 나빠지면 그만두기

 

best가 전역변수로 갱신되므로 다음 과 같은 한 줄을 추가하면 된다.

if(best <= currentLength) return;

 

3. 간단한 휴리스틱을 이용한 가지치기 (heuristic)

 

조합 탐색에서 방문하는 상태의 수는 탐색의 깊이가 깊어질수록 증가하기 때문에 탐색중 

'이 부분에서는 최적해가 나올 수 없다'는 것을 가능한 한 일찍 알아내는 것이 유리하다

 

휴리스틱 = 경험에 의거한 문제 풀이 기법. = 어느 정도 현실에 가까운 답을 빨리 찾기 위한 용도 = 적당히 그럴듯한

 

휴리스틱을 이용한 가지치기는 남은 조각들을 푸는 최적해를 찾기는 오래걸려도

적당히 어림짐작하기는 훨씬 빠르다.

 

한 상태가 주어질 때 아직 남은 도시들을 방문하기 위한 경로가 얼마나 길지를 적당히

어림짐작하는 휴리스틱 함수를 만들어야한다.

 

지금 까지 가장 좋은 답의 길이 : best

현재 부분 경로의 길이 : length

 

일때 

 

앞으로 길이가 best-length 미만인 경로로 남은 도시들을 모두 방문하고 시작점으로 돌아갈 수 있어야한다.

이 때 휴리스틱 함수가 답을 찾기 위해 그 보다 긴 경로가 필요하다고 하면 탐색을 중단할 수 있다.

 

실제보다 길다고 잘못 짐작 할 수 있기 때문에

휴리스틱의 반환 값이 항상 남은 최단 경로의 길이 보다 작거나 같아야한다.

== 과소평과하는 휴리스틱(underestimate)  == 낙관적인 휴리스틱(optimistic)

 

4. 단순한 휴리스틱 함수 작성하기

과소평가하는 휴리스틱함수를 만들려면 

항상 실제 답 이하이면서도 가능한 한 큰값을 구해야한다

 

휴리스틱 함수를 만드는 과정은 문제마다 다르기 때문에 정해진 방법이 존재하지 않는다.

좋은 방법 중 하나는 문제의 제약 조건을 일부 없앤 더 단순한 형태의 문제를 푸는 것이다.

 

tsp를 다음과 같이 변형해보자

 

- 남은 도시를 모두 방문할 필요 없이, 가장 멀리 있는 도시 하나만 방문했다가 시작점으로 돌아감

- 남은 도시들을 방문하는 방법이 꼭 일렬로 연결된 형태가 아니어도 된다.

 

=>

 

아직 방문하지 않은 도시들에 대해 인접한 간선 중 가장 짧은 간선의 길이를 더하는 것.

가장 짧은 간선의 길이만을 모으면 실제 최단 경로 이하의 값만 된다.

 

#include <iostream>
#include <vector>
 
using namespace std;
 
const double INF = 1e200;
const int MAX = 30;
int n;
double dist[MAX][MAX];
 
double best;
 
//각도시에인접한간선 중 가장짧은것 전처리
double minEdge[MAX];
 
double simpleHeuristic(vector<bool>& visited)
{
    double ret = minEdge[0];
    for (int i = 0; i < n; ++i)
        if(!visited[i])
            ret += minEdge[i];
    return ret;
}
 
void search(vector<int>& path, vector<bool>& visited, double currentLength)
{
    if(best <= currentLength + simpleHeuristic(visited)) return;
 
    int here = path.back();
 
    if(path.size() == n) 
    {
        best = min(best, currentLength + dist[here][0]);
        return;
    }
 
    for(int next = 0; next < n; ++next)
    {
        if (visited[next]) continue;
        path.push_back(next);
        visited[next] = true;
        search(path, visited, currentLength + dist[here][next]);
        visited[next] = false;
        path.pop_back();
    }
}
 
double solve()
{
    for (int i = 0; i < n; ++i) 
    {
        minEdge[i] = INF;
        for (int j = 0; j < n; ++j)
            if(i != j) minEdge[i] = min(minEdge[i], dist[i][j]);
    }
    best = INF;
    vector<bool> visited(n, false);
    vector<int> path(1, 0);
    visited[0] = true;
    search(path, visited, 0);
    return best;
}

완전 탐색에 비교하면 수행시간이 열배., 백배 빨라진다고 한다.

 

5. 가까운 도시부터 방문하기(탐욕)

TSP를 해결하는 조합탐색은 각 재귀 호출마다 다음에는 어느 도시를 방문할지를 결정하는 방식으로 구현된다.

이때 더 가까운 것부터 방문하면 좋은 답을 더 빨리 찾아낼 수 있는 경우가 있다.

 

각 도시마다 다른 모든 도시들을 거리 순으로 미리 정렬해서 저장해둬야한다.

 

=> 탐욕적 알고리즘으로 초기해를 구하는 것과 같은 효과

 

6. 지나온 경로를 이용한 가지치기

지금 까지 만든 부분 답을 검사해서 가지치기할  수도있다.

알고리즘 문제해결전략 411p

지금까지 만든 경로가 시작 상태에서 현재 상태까지 도달하는 최적해가 아니라고하면

최적해는 앞으로도 못찾을 것이고 탐색을 중단해야한다.

 

검사해서 최적해인지를 알기가 쉽지 않다.

따라서 대개 지나간 길을 돌아보는 가지치기는 탐색의 각 단계에서 현재 까지 만든 부분해에

간단한 조작을 가해보고, 결과적으로 답이 더 좋아진다면 탐색을 중단하는 식으로 구현된다.

 

Tsp에서는 두개의 인접한 도시를 골라서 이 둘의 순서를 바꿔 본 뒤, 경로가 더 짧아지면 탐색을 

중단하는 가지치기를 구현할 수 있다.

 

(.....,.., p, a, b, q, .... here)

 

위 경로에서 a, b의 순서를 바꿔 p - q 구간의 거리가 더 짧아지면 최적해를 찾을 가능성이 없으니

탐색을 중단하는 함수를 만들면 된다.

이 함수는 항상 현재 도시 이전의 두 도시만을 뒤집는다.

bool pathSwapPruning(const vector<int>& path)
{
    if (path.size() < 4) return false;
    int p = path[path.size() - 4];
    int a = path[path.size() - 3];
    int b = path[path.size() - 2];
    int q = path[path.size() - 1];
 
    return dist[p][a] + dist[b][q] > dist[p][b] + dist[a][q];
}

이 함수를 좀더 일반화하면

더 나은 성능을 얻을 수 있다.

 

두 도시 순서를 바꾸는 대신,.

전체 경로의 일부분을 통째로 뒤집는 것 이다.

 

p - a - b - c - d - e - q - - - here

 

p - e - d - c - b - a - q - - - here

 

이 경로가 더 짧다면 가지치기 할 수 있다.

 

이 때 경로 자체의 길이는 똑같기 때문에, 달라지는 것은

p와 q에 인접하는 도시 뿐이다.

 

이런 탐색은 자기 자신을 교차하는 경로를 만드는지를 검사하는 것이다.

 

한마디로 꼬인 경로를 푸는것과 마찬가자이다.

 

코드는 다음과 같다

bool pathReversePruning(const vector<int>& path)
{
    if(path.size() < 4) return false;
    
    int b = path[path.size() -2];
    int q = path[path.size() -1];
    for(int i = 0 ; i + 3 < path.size() ; i++)
    {
        int p = path[i];
        int a = path[i+1];
        
        if(dist[p][a] + dist[b][q] > dist[p][b] + dist[a][q])
            return true;     
    }
    return false;
} 

 

이 두 가지치기는 거의 동적 계획법과 비슷한 수준의 속도로 수행된다.

 

7. MST 휴리스틱을 이용한 가지치기의 구현

 

단순한 휴리스틱이아니라 좀더 현실에 가까운 답을 계산하는 휴리스틱 알고리즘이 있다면

bfs 조합탐색을 더욱 효과적으로 변형할 수 있다.

 

단순한 휴리스틱에서 더 제약이 있는 문제를 해결하는 알고리즘을 구현해보자.

 

1. 한 간선은 최대 한 번만 선택가능

2. 선택하지 않은 간선을 모두 지웠을 때 그래프가 둘 이상으로 쪼개지면 안됨.

 

즉, 선택한 간선들만 남겼을 때 아직 방문하지 않은 정점들과 현재 정점이 연결되어 있게끔 해야한다.

 

이것은 그래프 알고리즘중 하나인 MST(최소 스패닝 트리)

 

현재 위치에서 시작해서 아직 방문하지 않은 정점들을 모두 방문하고, 시작점으로 돌아오는 최단 경로또한

시작부분으로 돌아온는 선하나만 제외하면 정점들을 모두 연결하는 스패닝트리이다.

 

따라서 최소 스패닝 트리의 가중치의 합은 항상 최단 경로보다 작음을 알 수 있다.

 

크루스칼 스패닝 트리 알고리즘을 이용해 mst를 구하고, 간선 가중치의 합으로부터 탐색의 하한 값을

예상하는 구현은 다음과 같다.

 

크루스칼 알고리즘: 총 n-1개의 간선으로 이루어짐. 가장 작은 가중치를 가진 간선을 선택.  그 간선이 사이클을 만들지 않으면 mst에 포함시킴. n-1개가 될때까지 반복.

 

struct DisjointSet {
    DisjointSet(int n); // n개의 원소로 구성된 집합자료구조 생성
    int find(int here); // here가 포함된 집합 대표를 반환한다.
    bool merge(int a, int b); //a가 포함된 집합과 b가 포함된 집합을 합?
};
//모든 도시 간의 도로를 길이 순으로 정렬해 저장해둔다.
vector<pair<double, pair<int, int> > > edges;
 
double mstHeuristic(int here, const vector<bool>& visited)
{
    DisjointSet sets(n);
    double taken = 0;
    for(int i = 0; i < edges.size(); ++i)
   { // a -> b
        int a = edges[i].second.first, b = edges[i].second.second;
        if(a != 0 && a != here && visited[a]) continue;
        if(b != 0 && b != here && visited[b]) continue;
        if(sets.merge(a, b))
            taken += edges[i].first;
    }
    return taken;
}
 
double solve()
{ //초기화
    edges.clear();
    for (int i = 0; i < n; ++i)
        for(int j = 0; j < i; j++)
            edges.push_back(make_pair(dist[i][j], make_pair(i, j)));
    sort(edges.begin(), edges.end());
    // 생략
}

이 알고리즘은 동적 계획법보다 빠르게 동작하는 구간이 있는 알고리즘이다.

단순한 휴리스틱보다 수행하는데 많은 시간이 걸리지만 그만큼 훨씬 정확한 값을 찾아준다

 

8. 메모이제이션하기.

조합 탐색 과정에서 같은 상태를 두 번 이상 맞닥뜨리는 것은 흔한 일이다.

 

a에서 시작하고 남은 도시들이 같은 경우 

 

즉 a이전 까지의 모든 조합 이후의 최소거리는 모두 같다는 거다.

 

하지만 메모이제이션을 하는데 제약이 있다.

 

1. 메모리가 부족

    남은 조각의 수가 미리 정해둔 수 k 이하일때만 메모이제이션을 해야한다.

2. 가지치기를 사용하는 함수는 쉽게 메모이제이션을 할 수 없다.

    가지치기로 인해 현재 상태까지 오기 위한 경로에 따라 반환 값이 달라질 수 있다.

 

그러므로

가지치기를 사용하지 않는 동적 계획법 함수를 별도로 작성한뒤, 

마지막 k 단계에 도달하면 이 함수를 사용하도록 구현해야한다.

 

 

 

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