ひとりで勝手にはじめた蟻本読書会 フェニック木 BIT（Binary Indexed Tree） 蟻本読書会 の続きです。
巡回セールスマン問題は、複数の決められた地点を巡回して元の位置に戻る際、どう回れば最も移動距離が少ないか、という問題です。これは地域の移動手段であるバスの経路を決める際にも応用できる実用的な問題です。
巡回する都市の数が N 個あると、これらを巡回する方法は N! 通りあります。これらをすべて調べるのは現実的ではありません。都市数が20を超えるとほぼ不可能です。ただし動的計画法で計算量をO（N＾2 × 2＾N）へ減らす方法は存在します。
Contents
動的計画法で巡回セールスマン問題を解く
C – 巡回セールスマン問題
N 個の都市があり、0, 1, …, N – 1 と番号付けられている。全ての異なる 2 都市の間には道が存在し、都市
i から都市 j に移動するときのコストは A[i, j] である。あなたは今都市 0 にいる。ここから都市 0 以外の都市をちょうど 1 回ずつ訪れ、都市 0 に戻ってくる経路を作りたい。そのような経路における合計コストの最小値を求めよ。
入力されるデータ
N
A[0,0] A[0,1] … A[0,N-1]
A[1,0] A[1,1] … A[1,N-1]
…
A[N-1,0] A[N-1,1] A[N-1,N-1]（ただし、2 ≦ N ≦ 13
i ≠ j のとき 1 ≦ A[i,j] ≦ 10^9
i ＝ j のとき A[i,j] = 0 ）
N 桁の2進法を使えば N 個の都市それぞれについて訪問済みなのか未訪問なのかをひとつの変数で表すことができます。S をすでに訪問した都市の集合、i を最後に訪問した都市の番号とすると d(i, S) = (スタート地点から都市 i までの距離) とすることができます。
S’ = S と j の論理和とすると d(S’, j) = d(S, i) + (都市 i と 都市 j の距離) となります。またN 桁の2進法のすべてのビットが立っている数は（2 の N 乗 – 1）です。シフト演算子を使えば (1 << N) - 1 となります。2次元配列を定義してこれを更新していけば dp[(1 << N) - 1, 0] の値が解となります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N = int.Parse(Console.ReadLine()); long[,] A = new long[N, N]; for (int i = 0; i < N; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); for (int j = 0; j < N; j++) A[i, j] = vs[j]; } long inf = long.MaxValue; long[,] dp = new long[1 << N, N]; // 全体を大きな値で初期化 for (int i = 0; i < 1 << N; i++) { for (int col = 0; col < N; col++) dp[i, col] = inf; } // 最初に訪問する都市 for (int i = 0; i < N; i++) dp[1 << i, i] = A[0, i]; for (int row = 1; row < 1 << N; row++) { for (int col = 0; col < N; col++) { if (dp[row, col] == inf) // 対象外 continue; for (int next = 0; next < N; next++) { if (((row >> next) & 1) != 1) // 未訪問の都市 { int s = row | (1 << next); // 未訪問の都市を訪問済みの都市に追加 if (dp[s, next] > dp[row, col] + A[col, next]) // こちらのほうが近ければ更新 dp[s, next] = dp[row, col] + A[col, next]; } } } } Console.WriteLine(dp[(1 << N) - 1, 0]); } } |
時間制限付きの巡回セールスマン問題
G – Revenge of Traveling Salesman Problem
G – Revenge of Traveling Salesman Problem
街には建物が N 個あり、道路が M 本ある。建物の番号は 1-indexed でつけられており、店は建物 1 とする。また 道路 i は建物 s_i と建物t i を結んでいて、距離は d_i である。
その街は不審者対策として一定の時間を過ぎると道路を閉鎖する。道路 i はセールスマンが出発してから時間 time_i 経つと道路が閉鎖される。だからその道路を通る際は時間 time_i 以内に道路を通り終えなければならない。
最短経路と最短時間で戻ってくる方法の総数はどのくらいあるのだろうか？
ただしセールスマンは時間 1 につき距離 1 進む。また道路は双方向に移動可能である。入力されるデータ
N M
s_1 t_1 d_1 time_1
s_2 t_2 d_2 time_2
…
s_M t_M d_M time_M（ただし、
1 ≦ N ≦ 16
1 ≦ d_i ≦ 1,000,000,000,000
1 ≦ time_i ≦ 1,000,000,000,000 ）
これは時間制限付きの巡回セールスマン問題です。時間の経過とともに都市間の移動ができなくなったり移動のコストが変化する問題です。dp を遷移するまえに経過時間を調べて通行可能である場合のみ遷移します。dp[(1 << N) - 1, 0] が初期値からかわっていない場合はスタート地点に戻ってくる方法はないということになります。 最短経路だけでなく、最短時間で戻ってくる方法の総数も数えなければならないので、そのために別の配列（dp2）を用意します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
using System; using System.Collections.Generic; using System.Linq; class Edge { public Edge(long to, long cost, long time) { To = to; Cost = cost; Time = time; } public long To = 0; public long Cost = 0; public long Time = 0; } class Program { static void Main() { int N, M; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; M = vs[1]; } List<Edge>[] list = new List<Edge>[N]; for (int i = 0; i < N; i++) list[i] = new List<Edge>(); for (int i = 0; i < M; i++) { long[] vs = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); long s = vs[0] - 1; long t = vs[1] - 1; long d = vs[2]; long time = vs[3]; list[s].Add(new Edge(t, d, time)); list[t].Add(new Edge(s, d, time)); } long inf = long.MaxValue; long[,] dp = new long[1 << N, N]; long[,] dp2 = new long[1 << N, N]; // 巡回路の個数を数える for (int i = 0; i < 1 << N; i++) { for (int col = 0; col < N; col++) dp[i, col] = inf; } foreach (Edge edge in list[0]) { long cost = edge.Cost; int b = 1 << (int)edge.To; dp[b, edge.To] = cost; dp2[b, edge.To] = 1; } for (int row = 0; row < 1 << N; row++) { for (int col = 0; col < N; col++) { if (dp[row, col] == inf) continue; foreach (Edge edge in list[col]) { int next = (int)edge.To; long cost = edge.Cost; // edge.Time 経過前に通ることができない通路でなければ通れない if (dp[row, col] + cost > edge.Time) continue; if (((row >> next) & 1) != 1) { int s = row | (1 << next); // もっと短い時間で巡回できるなら巡回路の個数を更新する // 時間が同じなら巡回路の個数を合算する if (dp[s, next] == dp[row, col] + cost) dp2[s, next] += dp2[row, col]; if (dp[s, next] > dp[row, col] + cost) { dp[s, next] = dp[row, col] + cost; dp2[s, next] = dp2[row, col]; } } } } } if (dp[(1 << N) - 1, 0] == inf) Console.WriteLine("IMPOSSIBLE"); else Console.WriteLine($"{dp[(1 << N) - 1, 0]} {dp2[(1 << N) - 1, 0]}"); } } |
