조합탐색(combinatorial search)

알고리즘 스터디

조합탐색(combinatorial search)

11.1 도입

조합탐색

• 완전탐색을 포함해 유한한 크기의 탐색 공간을 뒤지면서 답을 찾아 내는 알고리즘
• 탐색 공간(search space) 부분답과 완성된 답의 집합
• 목표 : 기본적으로 모두 최적해가 될 가능성이 없는 답들을 탐색하는 것을 방지하여 만들어 봐야 할 답의 수를 줄이는 것을 목표로 함.

조합탐색 최적화 기법

• 가지치기(pruning) : 탐색 과정에서 최적해로 연결될 가능성이 없는 부분을 잘라낸다. 
  예) 외판원 문제를 추는데, 길이가 10인 경로를 이미 찾아냈다고 하면, 더이상 탐색하지 않고 탐색을 중단하는 것

• 탐색의 순서를 바꾸거나, 탐색 시작 전에 탐용법을 이용해 적당히 좋은 답을 우선 찾아낸다.

11.2 조합 탐색 기법들

여행하는 외판원 문제(TSP)를 푸는 완전탐색 알고리즘에 기법들을 적용하면서 변화하는 수행 속도를 관찰해본다.

• 입력파일 
  소행, 중형, 대형, 초대형 네가지 입력. 
  각각 n=12, n=16, n=20, n=24 크기의 입력 20개씩을 가지고 있으며 각 입력은 2차원 평면세 n개의 점을 임의로 배치하고 이들 사이의 거리를 재서 만듬

목표는 이 동적 계획법 알고리즘 보다는 더 빨리 답을 얻는 것

최적화	소형(n=12)	중형(n=16)	대형(n=20)	초대형(n=24)
동적계획법	0.03 sec	0.58 sec	26.45 sec	768.21 sec

- 입력이 커질수록 수행시간이 급격히 증가하는 것을 볼 수 있다. 
- 만약 컴퓨터의 메모리가 모자랐다면 결국 가상 메모리를 사용 해야 했을 테고, 결과적으로 상상할 수 없을 정도로 느려졌을 것이다.

조합 탐색 뼈대의 구현

코드 11.1 TSP를 해결하는 완전 탐색의 구현

const double INF = le200;
const int MAX = 30;
int n; // 도시의 수
double dist[MAX][MAX]; // 두 도시간의 거리를 저장하는 배열
// 지금까지 찾은 최적의 해
doubel 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]==true) continue;
        push.push_back(next);
        visited[next]=true;
        search(path, visited, currentLnegth + dist[here][next]);
        visited[next]=false;
        path.push_back(next);
    }
}
void solve(){
    best = INF;
    vector<int> path = vector(1,0);
    Vector<bool> visited = vector(n, false);
    visited[0]=true;
    search(path, visited,0);
    return best;
}

• 이와 같은 단순한 알고리즘의 수행 속도는 어떨까? search가 만드는 경로의 수는 (n-1)!개.
• 11!는 약 4천만 정도되므로 소형 입력은 그럭저럭 풀수 있다.
• 중형 입력 경로는 12*13*14*15 ~ 30,000 배 는다. -> 풀기 불가능

최적화	소형(n=12)	중형(n=16)	대형(n=20)	초대형(n=24)
동적계획법	0.03 sec	0.58 sec	26.45 sec	768.21 sec
완전탐색	89.74 sec	시간초과	시간초과	시간초과

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

간단한 가지치기 : 지금까지 찾은 가장 좋은 답 이상일 경우 중단 
if(best <= currentLength) return;

최적화	소형(n=12)	중형(n=16)	대형(n=20)	초대형(n=24)
동적계획법	0.03 sec	0.58 sec	26.45 sec	768.21 sec
완전탐색	89.74 sec	시간초과	시간초과	시간초과
최적해보다 나빠지면 그만두기	2.58 sec	981.53 sec	시간초과	시간초과

간단한 휴리스틱을 이용한 가지치기

• 휴리스틱(heuristic) : 경험에 의거한 문제 풀이 기법. 사람이 어림짐작으로 문제를 푸는 과정을 알고리즘으로 옮긴 것이 휴리스틱이라고 생각하면 얼추 비슷하다.

• 과소평가(underestimate)하는 휴리스틱, 난관적인 휴리스틱(optimistic heuristic) 낙관적인 휴리스닉

휴리스틱 함수 작성하기

• 남은 도시를 모두 방문할 필요 없이, 가장 멀리 있는 도시 하나만 방문했다가 시작적으로 돌아가도 된다.
• 남은 도시들을 방문하는 방법이 꼭 일렬로 연결된 형태가 아니어도 된다.

단순한 휴리스틱 함수 구현

코드 11.2 단순한 휴리스틱을 이용한 가지치기의 구현

최적화	소형(n=12)	중형(n=16)	대형(n=20)	초대형(n=24)
동적계획법	0.03 sec	0.58 sec	26.45 sec	768.21 sec
완전탐색	89.74 sec	시간초과	시간초과	시간초과
최적해보다 나빠지면 그만두기	2.58 sec	981.53 sec	시간초과	시간초과
단순한 휴리스틱	0.85 sec	84.18 sec	시간초과	시간초과

가까운 도시부터 방문하기

코드 11.3 가까운 정점부터 방문하는 최적화의 구현

최적화	소형(n=12)	중형(n=16)	대형(n=20)	초대형(n=24)
동적계획법	0.03 sec	0.58 sec	26.45 sec	768.21 sec
완전탐색	89.74 sec	시간초과	시간초과	시간초과
최적해보다 나빠지면 그만두기	2.58 sec	981.53 sec	시간초과	시간초과
단순한 휴리스틱	0.85 sec	84.18 sec	시간초과	시간초과
가까운 도시부터 방문하기	0.52 sec	31.03 sec	시간초과	시간초과

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

코드 11.4 지나온 경로를 이용하는 두 가지 가지치기 전략의 구현

최적화	소형(n=12)	중형(n=16)	대형(n=20)	초대형(n=24)
동적계획법	0.03 sec	0.58 sec	26.45 sec	768.21 sec
완전탐색	89.74 sec	시간초과	시간초과	시간초과
최적해보다 나빠지면 그만두기	2.58 sec	981.53 sec	시간초과	시간초과
단순한 휴리스틱	0.85 sec	84.18 sec	시간초과	시간초과
가까운 도시부터 방문하기	0.52 sec	31.03 sec	시간초과	시간초과
부분 경로 뒤집는 가지치기	0.07 sec	1.13 sec	33.29 sec	1160.81 sec

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

코드 11.5 MST 휴리스틱의 구현

최적화	소형(n=12)	중형(n=16)	대형(n=20)	초대형(n=24)
동적계획법	0.03 sec	0.58 sec	26.45 sec	768.21 sec
완전탐색	89.74 sec	시간초과	시간초과	시간초과
최적해보다 나빠지면 그만두기	2.58 sec	981.53 sec	시간초과	시간초과
단순한 휴리스틱	0.85 sec	84.18 sec	시간초과	시간초과
가까운 도시부터 방문하기	0.52 sec	31.03 sec	시간초과	시간초과
부분 경로 뒤집는 가지치기	0.07 sec	1.13 sec	33.29 sec	1160.81 sec
휴리스틱을 MST로 교체	0.06 sec	0.37 sec	14.77 sec	836.43 sec

마지막 단계 메모이제이션하기

코드 11.6 부분적으로 메모이제이션을 사용하는 최적화의 구현

// 남은 도시의 수가 CACHED_DEPTH 이하면 동적 계획법으로 바꾼다.
const int CACHED_DEPTH = 5;
// dp(here, visited)=cache[here][남은 도시의 수][visited]
map<int,double> cache[MAX][CACHED_DEPTH+1]
/// here : 현재 위치
// visited : 각 도시의 방문 여부 
// 일 때, 나머지 도시를 모두 방문하고 시작점으로 돌아가는 최단 경로의 길이를 반환한다.
double dp(int here, int visited){
    // 기저사례 : 더 방문할 도시가 없으면 시작점으로 돌아간다.
    if(visited == (1<<n)-1) return dist[here][0];

    // 메모이제이션
    int remaining = n - __builtin_popcount(visited);
    double& ret = cache[here][remaining][visited];
    if(ret > 0) return ret;
    ret = INF;

    // 다음 도시를 하나씩 시도한다.
    for(int next = 0; next < n; ++next){
        if(visited & (1<<next)) continue;
        ret = min(ret, dp(next, visited + (1<<next)) + dist[here][next]);
    }
    return ret;
}

void search(vector<int>& path, int visited, double currentLength) {
// 생략
// 기저 사례 : 남은 도시 수가 CACHED_DEPTH 이하면 동적 계획법으로 바꾼다.
    if(path.size() + CACHED_DEPTH >= n){
        best = min(best, currentLength + dp(path.back(), visited));
        return;
    }
    // 생략
}
double solve(){
    // 생략
    // cache 초기화
    for(int i = 0; i < MAX; ++i)
        for(int j = 0; j <= CACHED_DEPTH; ++j)
            cache[i][j].clear();
    // 생략
}

최적화	소형(n=12)	중형(n=16)	대형(n=20)	초대형(n=24)
동적계획법	0.03 sec	0.58 sec	26.45 sec	768.21 sec
완전탐색	89.74 sec	시간초과	시간초과	시간초과
최적해보다 나빠지면 그만두기	2.58 sec	981.53 sec	시간초과	시간초과
단순한 휴리스틱	0.85 sec	84.18 sec	시간초과	시간초과
가까운 도시부터 방문하기	0.52 sec	31.03 sec	시간초과	시간초과
부분 경로 뒤집는 가지치기	0.07 sec	1.13 sec	33.29 sec	1160.81 sec
휴리스틱을 MST로 교체	0.06 sec	0.37 sec	14.77 sec	836.43 sec
메모이제이션	0.06 sec	0.28 sec	2.91 sec	25.24 sec

전문적 TSP 해결 기법들

• 여기서 소개한 알고리즘은 TSP를 해결하기 위한 방법과는 거리가 멈
• 실제로는 TSP만을 해결하기 위해 고안된 프로그램들 정수계획법, 선형계획법 등을 사용함.

출저 : 알고리즘 문제 해결 전략