[algospot] TSP3

정말로 이 책을 여기까지 풀면서 생각해보지도 못했던 방법들을 많이 사용하게 되는 것 같습니다.

[TSP3] 문제 😭😊😒😂😄

NP-Complete 문제의 가장 유명한 예 중 하나인 여행하는 외판원 문제 (Traveling Salesman Problem) 은, 여러 개의 도시와 그 도시 간의 거리가 주어졌을 때, 각 도시를 정확히 한 번씩 방문하는 가장 짧은 경로를 찾는 문제이다. 이 문제를 다항 시간에 해결할 수 있는 방법은 현재까지는 존재하지 않지만, 도시의 숫자가 작은 경우에는 비교적 사용 가능한 시간 안에 문제를 해결할 수 있다.

AOJ 에서 이 문제는 같은 내용을 가진 문제 여러 개로 구성된다. 문제 번호에 비례해 도시의 개수가 올라가므로, 뒤로 갈수록 더욱 효율적인 방법을 써야 해결할 수 있다.

도시의 수 N <= 20 라고 할 때, 여행하는 외판원 문제를 해결하는 프로그램을 작성하라.

[풀이]

처음은 모든 경우의 수를 구하는 무작위 대입을 사용합니다.
이후 불가능한 경우의 수를 미리 제거해주기 위해 가지치기를 합니다.
먼저 pathReversePruning()을 이용하여 만약 p,a,b,q,here 가 연결되어 있는데 q,b,a,p 가 더 최소 길이를 가진다면 기존 p,a,b,q,here는 최적해가 될수 없으므로 가지치기 합니다.

다음 최소 스패닝 트리(MST)를 구현해 아직 방문하지 않은 길이의 최소 합과 현재까지의 구한 길이를 합한 값이 이전에 구한 best값 보다 크다면 가지치기 해줍니다. -> 이를 위해 사전에 vector<pair<double, pair<int,int> > edges 길이를 기준으로 정렬되어있는 컨테이너를 초기화 해줍니다. 또한 상호배타적인 set을 구현하여 merge 가능하면 합치지만 아니면 가지치기합니다.

마지막으로 메모이제이션을 이용하여 문제를 해결합니다. 도시의 수가 많아지면 메모리에 저장해야 하는 값이 엄청나게 커지므로 이를 방지하기 위해 CACHED_DEPTH 라는 값을 정해주어 도시 수가 얼마 남지 않았을때 사용합니다. 여기서 cache는 현재위치, 남은 정점의 수를 인덱스로 가지는 map의 2차원 배열로 이루어집니다.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 이 주어진다. 각 테스트 케이스의 첫 줄에는 도시의 수 N (3 <= N <= 20) 이 주어진다. 그 후 N 줄에, 각 N 개씩의 실수로 도시간의 거리가 주어진다. 도시들은 1 부터 N 까지의 숫자로 표현되며, i 번째 줄의 j 번째 실수는 i번째 도시와 j번째 도시 사이의 거리이다. 각 거리는 0 이상 1415 이하이고, 소수점 밑 열 자리까지 주어진다.

주어진 행렬은 대칭이며, 입력되는 거리들은 삼각 부등식 (triangle inequality) 을 만족한다고 가정해도 좋다.

출력

테스트 케이스마다 한 줄에 최소 경로의 길이를 소수점 밑 열 자리까지 출력한다. 1e-7 이하의 절대/상대 오차가 있어도 맞는 답으로 인정한다.

입력 예제

2
3
0000000000  611.6157225201  648.7500617289
6157225201  0.0000000000  743.8557967501
7500617289  743.8557967501  0.0000000000
4
0000000000  326.0008994586  503.1066076077  290.0250922998
0008994586  0.0000000000  225.1785728436  395.4019367384
1066076077  225.1785728436  0.0000000000  620.3945520632
0250922998  395.4019367384  620.3945520632  0.0000000000

출력 예제

1260.3657842490
841.2045646020

전체 코드는 다음과 같습니다.

//
//  TSP3.cpp
//  AALGGO
//
//  Created by inhyeok on 2021/10/27.
//

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <map>
#include <bitset>
using namespace std;
ifstream fin("TSP.txt");

const double INF = 1e200;
const int MAX = 20;
const int CACHED_DEPTH = 5; // 다섯개 남았을떄 DP 사용한다.

int N; // 도시의 수
double best; // 지금까지 최적해

double dist[MAX][MAX]; // 두 도시간의 거리를 저장.
double minEdge[MAX]; // 각 도시의 가장 짧은 거리를 저장해둔다.

vector<int> nearest[MAX]; // 각 도시마다 가까운 순서대로 정렬해 둔다.
vector<pair<double, pair<int, int> > > edges; // 모든 도시간의 도로를 길이 순으로 정렬

map<int, double> cache[MAX][CACHED_DEPTH+1];

struct DisjointSet{
    int num, component;
    vector<int> parent, rank;
    DisjointSet(int N) : num(N), component(N), parent(N), rank(N){
        for(int i=0; i<num; i++){
            parent[i] = i;
            rank[i] = 0;
        }
    }
    int find(int here){
        if(here == parent[here]) // 부모 노드를 찾으면 리턴
            return here;
        return parent[here] = find(parent[here]);
    }
    bool merge(int a, int b){ // a가 포함된 집합과 b가 포함된 집합을 합친다
        a = find(a);
        b = find(b);
        if(a==b)
            return false; // 이미 연결되어 있음
        if(rank[a] > rank[b])
            swap(a,b);
        parent[a] = b;
        if(rank[a] == rank[b]) rank[b]++;
        component--;
        return true;
    }
};

/* 최소길이만 따짐 mst보다 성능 안좋음
double simpleHeuristic(vector<bool>& visited){
    double ret = minEdge[0];
    for(int i=0; i<N; i++){
        if(!visited[i])
            ret+= minEdge[i];
    }
    return ret;
}
*/

bool pathReversePruning(const vector<int>& path){
    if(path.size()< 3) return false;
    int b = path[path.size()-2];
    int q = path[path.size()-1];

    for(int i=0; i+2 < 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;
}

double mstHeuristic(int here, const vector<bool>& visited){
    DisjointSet DS(N);
    double taken = 0;
    for(int i=0; i<edges.size(); i++){
        int a = edges[i].second.first;
        int b = edges[i].second.second;
        if(a!=here && visited[a]) continue;  // 간선이 here가 아니고 방문했던 곳이면 패쓰
        if(b!=here && visited[b]) continue;
        if(DS.merge(a,b)) taken += edges[i].first; // 겹치는 부분이 없으면 상호배타되어 최소의 간선의 합을 구함
    }
    return taken;
}

//남은 도시 수가 CACHED_DEPTH 이하개이면 dp로 푼다.
double dp(int here, int visited){

    if(visited == (1<<N) -1) return 0.0;
    // 메모이제이션
    int remaining = N - __builtin_popcount(visited); // __builtin_popcount 비트 1의 개수를 리턴해줌.
    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, vector<bool>& visited, double currentLength){
    int here = path.back();
    // 뒤집었을때 더 짧다면
    if(pathReversePruning(path)) return;
    //현재 길이 + 남은 도시의 mst최소 길이 합 보다 작다면 최적값이 되지못함.
    if(best <= currentLength + mstHeuristic(here, visited)) return;

    // 기저사례 남은 도시 수가 CAHCED_DEPTH 이하면 dp 사용
    if(path.size() + CACHED_DEPTH >= N ) {
        int mask = 0;
        for(int i=0 ; i<N; i++){
            if(visited[i]) mask += (1<<i);
        }
        double cand = currentLength + dp(here, mask);
        best = (best > cand) ? cand : best;
        return;
    }

    for(int i = 0; i < nearest[here].size(); i++){
        int next = nearest[here][i];
        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(){
    // nearest 각 도시에서 가장 가까운 도시순 대로 정렬
    for(int i=0; i<N; i++){
        vector<pair<double,int> > order;
        for(int j=0 ; j<N; j++){
            if(i!=j) order.push_back(make_pair(dist[i][j], j));
        }
        sort(order.begin(),order.end());
        nearest[i].clear();
        for(int j=0; j<N-1; j++) nearest[i].push_back(order[j].second);
    }
    // edges 설정
    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());

    //cache 초기화
    for(int i=0; i<MAX; i++){
        for(int j=0; j<=CACHED_DEPTH; j++)
            cache[i][j].clear();
    }
    best = INF;

    for(int i=0; i<N; i++){
        vector<int> path(1,i);
        vector<bool> visited(N, false);
        visited[i] = true;
        search(path, visited,0);
    }

    return best;


    /* mst보다 느림
    // minEdge 제일가까운 간선 저장 하는것 초기화
    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]);
        }
    } */
}


int main(){

    int test_case = 0;
    fin >> test_case;
    for(int test=0; test<test_case; test++){
        fin >> N;
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                fin >> dist[i][j];
            }
        }
        cout.precision(10);
        cout.setf(ios::fixed, ios::floatfield);
        cout << solve() << endl;
    }
    return 0;
}

TSP3

Twitter Facebook LinkedIn

[algospot] TSP3

[TSP3] 문제 😭😊😒😂😄

[풀이]

입력

출력

입력 예제

출력 예제

전체 코드는 다음과 같습니다.

Comments

You May Also Enjoy

SSD랑 HDD의 차이점

Container Orchestration?

MAC : mds_stores cpu 점유율 문제 해결

Recommender System with Deep Learning