algospot.com :: 질문과 답변: JM-book p.417~p.420 관련 질문입니다.

JM-book p.417~p.420 관련 질문입니다.

안녕하세요.
JM book으로 공부중인 학생입니다.
p.417~p.420관련 질문이 있어 글 남깁니다.

TSP문제를 빠르게 풀어내기 위해 책에 소개된 여러 방법을 모두 구현해보았습니다.
책에 소개된 내용대로라면 mst heuristic을 사용하는 경우보다
마지막 5단계를 DP하는 경우가 더욱 빠른 결과를 내어 놓아야합니다.

하지만 제 코드는
TSP3 문제에 대해서 mst heuristic을 사용하는 경우 : 395ms,
마지막 5단계만 DP를 하는 경우 : 시간초과
로서 책의 소개와는 다른 결과를 내어 놓습니다.

책에 실려 있는 코드와 제 코드를 비교해 볼 때,
다른 점은 크게 세 가지 입니다.

가상의 도시 0번 도시를 설정함.
모든 도시로부터 거리가 0인 가상의 도시 0번 도시를 설정하고,
모든 경로가 0번 도시로 부터 시작된다고 가정합니다.
가까운 도시부터 방문함.
미리 정점별로 가까운 정점들을 오름차순으로 저장해놓고,
가까운 곳부터 방문합니다.
DP함수에 남은 도시의 수를 직접 전달합니다.
__builtin_popcount함수를 사용하지 않습니다.

이 세가지 말고는 크게 다른 점이 없는데, 왜 제 코드는 DP를 사용해도
수행시간에 개선이 없는지 궁금합니다.
(TSP1, TSP2에 대해서는 모두 옳은 답을 내놓습니다.)

1.mst heuristic 코드와 주석

#include<iostream>
#include<vector>
#include<algorithm>

#define MAX_CITY 20
#define INF 2000000000

using namespace std;

int N;
//가상의 도시 0번 도시를 설정할 것이므로 배열의 크기를 하나 더 크게 잡습니다.
double BEST,DIST[MAX_CITY+1][MAX_CITY+1]={0,};
//가까운 도시부터 방문하기 위한 벡터입니다.
//NEAREST_CITY[i]에는 i번째 도시에서 가까운 도시부터 그 인덱스가 차례로 저장됩니다.
vector<vector<pair<int,double> > > NEAREST_CITY;
//MST를 만들기 위해 간선을 가중치의 오름 차순으로 저장할 벡터입니다.
vector<pair<pair<int,int>,double> > EDGES;
//각각의 요소를 오름차순으로 정렬하기 위한 비교클래스입니다.
class COMPARE{
    public:
        bool operator()(const pair<int,double>& r1,const pair<int,double>& r2){
            return r1.second<r2.second;
        }
        bool operator()(const pair<pair<int,int>,double>& r1,const pair<pair<int,int>,double>& r2){
            return r1.second<r2.second;
        }
};
//분리집합 구조체입니다.
class DISJOINT_SET{
    public:
        DISJOINT_SET* parent;
        int vertex;
};

//분리집합의 최상단 노드를 찾아줍니다.
DISJOINT_SET* find_set(DISJOINT_SET* r);
//두 분리 집합을 합집합 해줍니다. 교집합이 없는 경우만 연산에 대해 참을 반환하고 수행합니다.
bool union_set(DISJOINT_SET* r1,DISJOINT_SET* r2);
//답을 내주는 함수입니다.
double answer(void);
//각종 풀이에 필요한 전처리 과정을 수행 합니다.
void preprocessing(void);
//주어진 방문정보에 대해, mst를 생성합니다.
double mst(int visit);
//exhaustive search로 직접 문제를 풀어내는 함수입니다.
void solve(vector<int>& path,int visit,double current);

int main(void){
    int TC;
    cin>>TC;
    while(TC--){
        cin>>N;
        //가상의 도시 0번 도시를 설정하기 때문에 다음과 같이 입력을 받습니다.
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                cin>>DIST[i][j];
        }}
        N++;
        cout.precision(20);
        cout<<answer()<<endl;
    }
    return 0;
}

DISJOINT_SET* find_set(DISJOINT_SET* r){
    DISJOINT_SET* temp=r;
    while(temp->parent!=NULL){temp=temp->parent;}
    return temp;
}
bool union_set(DISJOINT_SET* r1,DISJOINT_SET* r2){
    bool ret=false;
    DISJOINT_SET* s1=find_set(r1);
    DISJOINT_SET* s2=find_set(r2);
    if(s1!=s2){
        s2->parent=s1;
        ret=true;
    }
    return ret;
}
double answer(void){
    int visit=1;
    vector<int> path(1,0);
    BEST=INF;
    preprocessing();
    solve(path,visit,0);
    return BEST;
}
void preprocessing(void){
    //NEAREST_CITY를 미리 저장 해둡니다.
    NEAREST_CITY.clear();
    vector<pair<int,double> > temp;
    for(int i=0;i<N;i++){
        temp.clear();
        for(int j=0;j<N;j++){
            temp.push_back(make_pair(j,DIST[i][j]));
        }
        sort(temp.begin(),temp.end(),COMPARE());
        NEAREST_CITY.push_back(temp);
    }
    //EDGES를 미리 저장 해둡니다.
    EDGES.clear();
    for(int i=1;i<N;i++){
        for(int j=1;j<i;j++){
            EDGES.push_back(make_pair(make_pair(i,j),DIST[i][j]));
    }}
    sort(EDGES.begin(),EDGES.end(),COMPARE());
    return;
}
double mst(int visit,int here){
    double ret=0;
    int f,t;
    //분리집합을 도시의 갯수만큼 생성해줍니다.
    DISJOINT_SET DJ_SET[MAX_CITY+1];
    for(int i=1;i<N;i++){
        DJ_SET[i].parent=NULL;
        DJ_SET[i].vertex=i;
    }
    //MST는 here도 미방문인 상태에서 구해져야 합니다.
    visit-=(1<<here);
    //EDGES를 순회하면서 MST를 kruskal algorithm으로 구성합니다.
    for(int i=0;i<EDGES.size();i++){
        f=EDGES[i].first.first;
        t=EDGES[i].first.second;
        if((visit&(1<<f))==0&&(visit&(1<<t))==0){
            if(union_set(&DJ_SET[f],&DJ_SET[t])){
                ret+=EDGES[i].second;
    }}}
    //MST의 가중치의 총 합을 반환합니다.
    return ret;
}
void solve(vector<int>& path,int visit,double current){
    int nv,here=path.back();
    //현재만든 경로에, 남은 도시시를 통해 얻어지는 MST정보를 이용하여 가지치기 합니다.
    if(BEST<=current+mst(visit,here)){return;}
    if(visit+1==(1<<N)){
        BEST=min(BEST,current+DIST[here][0]);
    }
    else{
        for(int i=0;i<N;i++){
            NEAREST_CITY[here][i].first;
            if((visit&(1<<NEAREST_CITY[here][i].first))==0){
                path.push_back(NEAREST_CITY[here][i].first);
                nv=(visit|(1<<NEAREST_CITY[here][i].first));
                solve(path,nv,current+DIST[here][NEAREST_CITY[here][i].first]);
                path.pop_back();
    }}}
    return;
}

2.마지막 5단계만을 DP하는 코드와 주석

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>

#define MAX_CITY 20
#define INF 2000000000
#define CACHE_DEPTH 5

using namespace std;

int N;
//가상의 도시 0번 도시를 설정할 것이므로 배열의 크기를 하나 더 크게 잡습니다.
double BEST,DIST[MAX_CITY+1][MAX_CITY+1]={0,};
//가까운 도시부터 방문하기 위한 벡터입니다.
//NEAREST_CITY[i]에는 i번째 도시에서 가까운 도시부터 그 인덱스가 차례로 저장됩니다.
vector<vector<pair<int,double> > > NEAREST_CITY;
//방문정보를 key로, cache값을 value로 갖는 캐시를 설정합니다.
map<int,double> CACHE[MAX_CITY+1][CACHE_DEPTH+1];
//각각의 요소를 오름차순으로 정렬하기 위한 비교클래스입니다.
class COMPARE{
    public:
        bool operator()(const pair<int,double>& r1,const pair<int,double>& r2){
            return r1.second<r2.second;
        }
};

//답을 내주는 함수입니다.
double answer(void);
//각종 풀이에 필요한 전처리 과정을 수행 합니다.
void preprocessing(void);
//현재도시, 미방문도시의 수, 도시들의 방문정보를 인자로 받아 DP를 수행하는 함수 입니다.
double dp(int here,int remain,int visit);
//exhaustive search로 직접 문제를 풀어내는 함수입니다.
void solve(vector<int>& path,int visit,double current);

int main(void){
    int TC;
    cin>>TC;
    while(TC--){
        cin>>N;
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                cin>>DIST[i][j];
        }}
        N++;
        cout.precision(20);
        cout<<answer()<<endl;
    }
    return 0;
}

double answer(void){
    int visit=1;
    vector<int> path(1,0);
    BEST=INF;
    preprocessing();
    solve(path,visit,0);
    return BEST;
}
void preprocessing(void){
    //NEAREST_CITY를 미리 저장 해둡니다.
    NEAREST_CITY.clear();
    vector<pair<int,double> > temp;
    for(int i=0;i<N;i++){
        temp.clear();
        for(int j=0;j<N;j++){temp.push_back(make_pair(j,DIST[i][j]));}
        sort(temp.begin(),temp.end(),COMPARE());
        NEAREST_CITY.push_back(temp);
    }
    //map으로 이루어진 cache를 초기화 해줍니다.
    for(int i=0;i<MAX_CITY+1;i++){
        for(int j=0;j<CACHE_DEPTH+1;j++){
            CACHE[i][j].clear();
    }}
    return;
}
double dp(int here,int remain,int visit){
    //남은 도시가 없다면 0을 리턴합니다.
    if(remain==0){return 0;}
    double& ret=CACHE[here][remain][visit];
    //map의 초기화 값이 0임을 이용합니다.
    if(ret==0){
        ret=INF;
        for(int i=0;i<N;i++){
            if((visit&(1<<i))==0){
                ret=min(ret,DIST[here][i]+dp(i,remain-1,visit+(1<<i)));
    }}}
    return ret;
}
void solve(vector<int>& path,int visit,double current){
    int nv,here=path.back();
    //남은 도시가 CACHE_DEPTH개 이하인 경우 DP로 전환합니다.
    if(N-path.size()<=CACHE_DEPTH){
        BEST=min(BEST,current+dp(here,N-path.size(),visit));
        return;
    }
    if(visit+1==(1<<N)){
        BEST=min(BEST,current+DIST[here][0]);
    }
    else{
        for(int i=0;i<N;i++){
            NEAREST_CITY[here][i].first;
            if((visit&(1<<NEAREST_CITY[here][i].first))==0){
                path.push_back(NEAREST_CITY[here][i].first);
                nv=(visit|(1<<NEAREST_CITY[here][i].first));
                solve(path,nv,current+DIST[here][NEAREST_CITY[here][i].first]);
                path.pop_back();
    }}}
    return;
}

제가 잘못생각하고 있는 부분이나, 코드에 오류가 있다면 알려주세요.ㅠㅠ

10년 전

8개의 댓글이 있습니다.

VOCList

CACHE가 map 으로 선언되어있는데, 잘 생각해보면 맵을 쓸 필요가 없습니다. map을 쓰는 이유는 우리가 참조하려는 인덱스가 매우 sparse할 경우에 편의를 위해서 쓰는 경우가 대부분인데, 이 경우엔 CACHE의 세번째 인자 범위가 엄밀하게 주어지고 해당 범위 안의 모든 인덱스를 참조할 가능성이 있기에 맵이 의미가 없어지고, 따라서 double CACHE[21][21][1 << 21]으로 선언해 주시는 것이 무의미한 시간 손실을 줄이는데 도움이 되겠지요.

하지만 사실 21 * 21 * (1 << 21) * 8 바이트는 굉장히 큰 메모리인데요, 사실 잘 생각해 보시면 remain 변수의 값은 사실 visit 변수에서 추측이 가능한 정보입니다. remain 차원을 포기하고 21 * (1 << 21) 개의 변수만을 선언한다면 메모리 관리 측면에서도 훨씬 효율적이 되어 선언할만한 변수 사이즈가 되겠네요.

10년 전 link

canuyes

우선 답변 감사드립니다.
그런데, cache를 map으로 선언한 부분이나,
remain을 따로 한 차원을 더 해가며 선언한 이유는 다음과 같습니다.
(책에 소개된 내용을 근거로 함.)

다섯개 이하의 도시가 남았을 때에만 메모이제이션함. 실제사용될 공간의수는 21*(21C5+21C4+21C3+21C2+21C1)에 불과함. (인덱스가 sparse해짐.) 따라서 map을 사용.
map은 저장된 값의 갯수가 많을 수록 접근 비용이 증가함. 저장되는 cache값의 갯수가 늘어나면 늘어날수록 접근비용이 증가함. 따라서, 비교적 적은 비용의 remain정보로 map을 나누어줌.

VOCList님의 설명대로 구현해본 코드입니다.
질문코드와 크게 다르지 않아 주석은 달지 않았습니다.

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#define MAX_CITY 20
#define INF 2000000000
#define CACHE_DEPTH 5

using namespace std;

int N;
double BEST,DIST[MAX_CITY+1][MAX_CITY+1]={0,};
vector<vector<pair<int,double> > > NEAREST_CITY;
double CACHE[MAX_CITY+1][1<<(MAX_CITY+1)];
class COMPARE{
    public:
        bool operator()(const pair<int,double>& r1,const pair<int,double>& r2){
            return r1.second<r2.second;
        }
};
double answer(void);
void preprocessing(void);
double dp(int here,int visit);
void solve(vector<int>& path,int visit,double current);

int main(void){
    int TC;
    cin>>TC;
    while(TC--){
        cin>>N;
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                cin>>DIST[i][j];
        }}
        N++;
        cout.precision(20);
        cout<<answer()<<endl;
    }
    return 0;
}

double answer(void){
    int visit=1;
    vector<int> path(1,0);
    BEST=INF;
    preprocessing();
    solve(path,visit,0);
    return BEST;
}
void preprocessing(void){
    NEAREST_CITY.clear();
    vector<pair<int,double> > temp;
    for(int i=0;i<N;i++){
        temp.clear();
        for(int j=0;j<N;j++){temp.push_back(make_pair(j,DIST[i][j]));}
        sort(temp.begin(),temp.end(),COMPARE());
        NEAREST_CITY.push_back(temp);
    }
    for(int i=0;i<MAX_CITY+1;i++){
        memset(CACHE[i],0,sizeof(double)*(1<<(MAX_CITY+1)));
    }
    return;
}
double dp(int here,int visit){
    if(visit+1==(1<<N)){return 0;}
    double& ret=CACHE[here][visit];
    if(ret==0){
        ret=INF;
        for(int i=0;i<N;i++){
            if((visit&(1<<i))==0){
                ret=min(ret,DIST[here][i]+dp(i,visit+(1<<i)));
    }}}
    return ret;
}
void solve(vector<int>& path,int visit,double current){
    int nv,here=path.back();
    if(N-path.size()<=CACHE_DEPTH){
        BEST=min(BEST,current+dp(here,visit));
        return;
    }
    if(visit+1==(1<<N)){
        BEST=min(BEST,current+DIST[here][0]);
    }
    else{
        for(int i=0;i<N;i++){
            NEAREST_CITY[here][i].first;
            if((visit&(1<<NEAREST_CITY[here][i].first))==0){
                path.push_back(NEAREST_CITY[here][i].first);
                nv=(visit|(1<<NEAREST_CITY[here][i].first));
                solve(path,nv,current+DIST[here][NEAREST_CITY[here][i].first]);
                path.pop_back();
    }}}
    return;
}

10년 전 link

canuyes

에휴..3000자 넘어가니 업로드가 안되네요 ㅠㅠ. 이어 씁니다.

위 코드는 올바른 답을 내주긴 합니다만, cache가 크다 보니
8*21*(1<<21) : 344064kb로서 메모리 초과가 납니다.

다른 방법들에는 어떤것들이 있을까요? ㅠㅠ
아, 그리고 원래 배열 접근보다 map에 대한 접근이 더 느린가요?
답변 기다립니다. ㅠㅠ

10년 전 link
canuyes

TSP에 자주 쓰이는 최적화방법도 아니라하고,
다소 책에 국한되는 내용이라 다른곳에 질문키가 애매하네요
어디가 문제일까요?
참고로 tsp3에서 mst와 dp를 함께 사용한 답안보다
mst만 사용한 답안이 더욱 빨리 수행되었어요ㅠ

10년 전 link
sven

배열 접근은 시간 복잡도가 상수인 반면, map 은 크기의 로그에 비례하는 것 같습니다.
http://www.cplusplus.com/reference/map/map/operator[]/

10년 전 link
canuyes

답변 감사드립니다.
정말 당연한건데..매일 별 생각없이 생각하다보니
잊고 말았네요 ㅠ
그나저나 진짜 원인이 뭘까요? ㅠㅠ

10년 전 link
VOCList

그러네요 저게 메모리가 생각보다 크네.. 고민을 해 봐야겠네영 ㅜㅜ

10년 전 link
canuyes

ㅠㅠ막막허네유 ㅠㅠ

10년 전 link
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.

SINCE 2007

다가오는 이벤트들

JM-book p.417~p.420 관련 질문입니다.

1.mst heuristic 코드와 주석

2.마지막 5단계만을 DP하는 코드와 주석

8개의 댓글이 있습니다.