DPL_2_A:Traveling Salesman Problem

bitDP 動的計画法

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A&lang=jp

巡回セールスマン問題。有向グラフ G(V, E) 上のある頂点から出発して、出発点に戻る閉路の最短距離を求めよ。

制約

  • 2 <= |v| <= 15
  • 0 <= d_i <= 1000

考え方

bitDPである。頂点集合を S として、右から数えて i 番目のビットが1立っているときはその頂点 i を訪問済み。0 のときは未訪問として状態を管理する。もう一つの状態は、現在どこにいるか？という現在位置の状態である。これを v とする。

dp の遷移は、現在の頂点 v から未訪問の頂点 u への遷移を考えれば良い。求める解は k を出発点として dp[(1<<v)-1][k] の最小値である。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            int v = in.nextInt(), e = in.nextInt();
            int[][] mat = new int[v][v];
            for (int i = 0; i < v; i++) {
                Arrays.fill(mat[i], -1);
            }

            for (int i = 0; i < e; i++) {
                int s = in.nextInt(), t = in.nextInt(), d = in.nextInt();
                mat[s][t] = d;
            }

            int[][] dp = new int[1 << v][v];

            dp = new int[1 << v][v];
            for (int i = 0; i < 1 << v; i++) {
                Arrays.fill(dp[i], INF);
            }
            dp[0][0] = 0;

            for (int s = 0; s < 1<<v; s++) {
                for (int now = 0; now < v; now++) {
                    for (int to = 0; to < v; to++) {
                        if ((s >> to & 1) == 0 && mat[now][to] != -1) {
                            dp[s|1<<to][to] = Math.min(dp[s|1<<to][to], dp[s][now] + mat[now][to]);
                        }
                    }
                }
            }
            out.println(dp[(1<<v)-1][0] == INF ? -1 : dp[(1<<v)-1][0]);
        }

スタート地点を 0 に絞ってbitDPしても通ったのだが、[0, v-1] のすべての k に対してbitDPを求めなくても 0 からだけの値で問題ないのか？？
ある頂点から始めて、すべての頂点を1回ずつ訪れることが可能である時、[0, n-1] の頂点の閉路になっているので、どの頂点から始めても同じである。ということであった、

ポイント

頂点集合をビットで管理する以外は通常のナップザックDPと同じである。実際、DP遷移はDAGになっている。