chacoderのブログ

競技プログラミングそのほか

トップ > 巡回セールスマン問題

巡回セールスマン問題

巡回セールスマン問題（TSP　Travelling Salesperson Problem)

　蟻本P173から巡回セールスマン問題の検討です。

　巡回セールスマン問題は、超点数nの重み付き有向グラフの頂点０からスタートして、すべての点をちょうど１度づつめぐって帰ってくる閉路のうち、重みの総和の最小値を求める問題です。

多項式時間の効率的なアルゴリズムが知られていないNP困難の問題です。

DPによる解法

すでに訪れた頂点集合をS、現在vにいる状態から残りのすべての頂点をめぐって０に帰ってくるようなパスの重みの総和の最小値をdp[S][v]と表すと以下の漸化式が成り立ちます。

dp[V][0]=0　
dp[S][v]=min(dp[s U {u}][u]+d(v,u)|u ∉S)

再帰で書く場合にメモ化のために集合をどう管理するかが課題になります。

コード例

#include <bits/stdc++.h>
using namespace std;
static const int MAX_N=15;
static const int INF=100000000;

int n;
int d[MAX_N][MAX_N];
int dp[1<<MAX_N][MAX_N];

int rec(int S,int v){
  //メモ確認
  if(dp[S][v]>=0){
    return dp[S][v];
  }
  if(S == (1<<n)-1 && v==0){
    return dp[S][v] = 0;
  }
  int res = INF;
  for(int u=0;u<n;u++){
    if(!(S>>u&1)){
      //(S|1<<u　でSにuを追加
      res=min(res,rec(S | 1<<u,u)+d[v][u]);
    }
  }
  return dp[S][v] =res;
}

int main(){
  cin>>n;
  //辺数　m
  int m;
  cin>>m;
  
  //from x to y const z
  int x,y,z;
  memset(d,INF,sizeof(d));
  for(int i=0;i<m;i++){
    cin>>x>>y>>z;
    d[x][y]=z;
  }
    
  //dpテーブルを-1で初期化
  memset(dp,-1,sizeof(dp));
  
  //出力
  cout<<rec(0,0)<<endl;
  return 0;
}

入力例1

蟻本の例です。

5 8
0 1 3
4 0 7
4 1 6
0 3 4
2 0 4
3 4 3 
1 2 5
2 3 5

出力例1

22

入力例2

UTPC2011の例です。
０オリジンにするためデクリメントしています。
https://atcoder.jp/contests/utpc2011/tasks/utpc2011_11

5 5
1 1 10
1 2 20
2 3 30
3 4 40
4 0 50

出力例2

150

検討メモ

INFを大きくしすぎるとエラーになります。
10e6はOKでしたが10e7はエラーになります。

集合をbitで管理するbitDPの書き方はbit全探索で使った書き方と同じです。

初期化に使った関数のmemsetは別記事にしました。
配列の初期化とmemset - chacoderのブログ

再帰の計算量はかなり大きくなります
頂点数５の入力例1のケースも２のケースもrec関数の呼び出しを166回しています。
頂点数４のケースをつくってみたら53回でした。

理論計算量は　O ( (n^2)*(2^n) ) とのことなので、５頂点の場合800、４頂点の場合256です。
30頂点程度で10e12ぐらいになるのでメモ化再帰しても数時間かかりそうです。