DAA-巡回セールスマン問題
問題文
旅行者はリストからすべての都市を訪問する必要があります。ここでは、すべての都市間の距離がわかっており、各都市は1回だけ訪問する必要があります。彼が各都市を一度だけ訪れて元の都市に戻る最短ルートはどれですか？
解決
巡回セールスマン問題は、最も悪名高い計算上の問題です。力ずくのアプローチを使用して、考えられるすべてのツアーを評価し、最適なツアーを選択できます。ためにn グラフ内の頂点の数、 (n - 1)! 可能性の数。
動的計画法を使用したブルートフォースの代わりに、多項式時間アルゴリズムはありませんが、より短い時間で解を得ることができます。
グラフを考えてみましょう G = (V, E)、 どこ V 都市のセットであり、 E重み付きエッジのセットです。縁e(u, v) その頂点を表します u そして v接続されている。頂点間の距離u そして v です d(u, v)、これは負ではないはずです。
私たちが都市で始めたとしましょう 1 そしていくつかの都市を訪れた後、私たちは今都市にいます j。したがって、これは部分的なツアーです。私たちは確かに知る必要がありますj、これにより、次に訪問するのに最も便利な都市が決まります。また、これまでに訪れたすべての都市を知っておく必要があります。そうすれば、どの都市も繰り返さないようになります。したがって、これは適切なサブ問題です。
都市のサブセットの場合 S Є {1, 2, 3, ... , n} それが含まれています 1、および j Є S、 C(S, j) の各ノードを訪問する最短経路の長さ S 一度だけ、 1 で終わる j。
いつ|S| > 1、私たちは定義しますC(S, 1) = ∝パスはで開始および終了できないため 1。
さあ、表現しましょう C(S, j)小さなサブ問題の観点から。から始める必要があります1 そしてで終わる j。次の都市を次のように選択する必要があります
$$ C（S、j）= min \：C（S- \ lbrace j \ rbrace、i）+ d（i、j）\：where \：i \ in S \：and \：i \ neq jc（ S、j）= minC（s- \ lbrace j \ rbrace、i）+ d（i、j）\：where \：i \ in S \：and \：i \ neq j $$
Algorithm: Traveling-Salesman-Problem
C ({1}, 1) = 0
for s = 2 to n do
for all subsets S Є {1, 2, 3, … , n} of size s and containing 1
C (S, 1) = ∞
for all j Є S and j ≠ 1
C (S, j) = min {C (S – {j}, i) + d(i, j) for i Є S and i ≠ j}
Return minj C ({1, 2, 3, …, n}, j) + d(j, i)分析
最大で$ 2 ^ nn $のサブ問題があり、それぞれが解決するのに線形の時間がかかります。したがって、合計実行時間は$ O（2 ^ nn ^ 2）$です。
例
次の例では、巡回セールスマン問題を解決する手順を説明します。
上記のグラフから、次の表が作成されます。
| 1 | 2 | 3 | 4 | |
| 1 | 0 | 10 | 15 | 20 |
| 2 | 5 | 0 | 9 | 10 |
| 3 | 6 | 13 | 0 | 12 |
| 4 | 8 | 8 | 9 | 0 |
S =Φ
$$ \ small Cost（2、\ Phi、1）= d（2,1）= 5 \ small Cost（2、\ Phi、1）= d（2,1）= 5 $$
$$ \ small Cost（3、\ Phi、1）= d（3,1）= 6 \ small Cost（3、\ Phi、1）= d（3,1）= 6 $$
$$ \ small Cost（4、\ Phi、1）= d（4,1）= 8 \ small Cost（4、\ Phi、1）= d（4,1）= 8 $$
S = 1
$$ \ small Cost（i、s）= min \ lbrace Cost（j、s –（j））+ d [i、j] \ rbrace \ small Cost（i、s）= min \ lbrace Cost（j、s ）-（j））+ d [i、j] \ rbrace $$
$$ \ small Cost（2、\ lbrace 3 \ rbrace、1）= d [2,3] + Cost（3、\ Phi、1）= 9 + 6 = 15cost（2、\ lbrace3 \ rbrace、1）= d [2,3] + cost（3、\ Phi、1）= 9 + 6 = 15 $$
$$ \ small Cost（2、\ lbrace 4 \ rbrace、1）= d [2,4] + Cost（4、\ Phi、1）= 10 + 8 = 18cost（2、\ lbrace4 \ rbrace、1）= d [2,4] + cost（4、\ Phi、1）= 10 + 8 = 18 $$
$$ \ small Cost（3、\ lbrace 2 \ rbrace、1）= d [3,2] + Cost（2、\ Phi、1）= 13 + 5 = 18cost（3、\ lbrace2 \ rbrace、1）= d [3,2] + cost（2、\ Phi、1）= 13 + 5 = 18 $$
$$ \ small Cost（3、\ lbrace 4 \ rbrace、1）= d [3,4] + Cost（4、\ Phi、1）= 12 + 8 = 20cost（3、\ lbrace4 \ rbrace、1）= d [3,4] + cost（4、\ Phi、1）= 12 + 8 = 20 $$
$$ \ small Cost（4、\ lbrace 3 \ rbrace、1）= d [4,3] + Cost（3、\ Phi、1）= 9 + 6 = 15cost（4、\ lbrace3 \ rbrace、1）= d [4,3] + cost（3、\ Phi、1）= 9 + 6 = 15 $$
$$ \ small Cost（4、\ lbrace 2 \ rbrace、1）= d [4,2] + Cost（2、\ Phi、1）= 8 + 5 = 13cost（4、\ lbrace2 \ rbrace、1）= d [4,2] + cost（2、\ Phi、1）= 8 + 5 = 13 $$
S = 2
$$ \ small Cost（2、\ lbrace 3、4 \ rbrace、1）= \ begin {cases} d [2、3] + Cost（3、\ lbrace 4 \ rbrace、1）= 9 + 20 = 29 \ \ d [2、4] + Cost（4、\ lbrace 3 \ rbrace、1）= 10 + 15 = 25 = 25 \ small Cost（2、\ lbrace 3,4 \ rbrace、1）\\\ lbrace d [ 2,3] + \ small cost（3、\ lbrace4 \ rbrace、1）= 9 + 20 = 29d [2,4] + \ small Cost（4、\ lbrace 3 \ rbrace、1）= 10 + 15 = 25 \ end {cases} = 25 $$
$$ \ small Cost（3、\ lbrace 2、4 \ rbrace、1）= \ begin {cases} d [3、2] + Cost（2、\ lbrace 4 \ rbrace、1）= 13 + 18 = 31 \ \ d [3、4] + Cost（4、\ lbrace 2 \ rbrace、1）= 12 + 13 = 25 = 25 \ small Cost（3、\ lbrace 2,4 \ rbrace、1）\\\ lbrace d [ 3,2] + \ small cost（2、\ lbrace4 \ rbrace、1）= 13 + 18 = 31d [3,4] + \ small Cost（4、\ lbrace 2 \ rbrace、1）= 12 + 13 = 25 \ end {cases} = 25 $$
$$ \ small Cost（4、\ lbrace 2、3 \ rbrace、1）= \ begin {cases} d [4、2] + Cost（2、\ lbrace 3 \ rbrace、1）= 8 + 15 = 23 \ \ d [4、3] + Cost（3、\ lbrace 2 \ rbrace、1）= 9 + 18 = 27 = 23 \ small Cost（4、\ lbrace 2,3 \ rbrace、1）\\\ lbrace d [ 4,2] + \ small cost（2、\ lbrace3 \ rbrace、1）= 8 + 15 = 23d [4,3] + \ small Cost（3、\ lbrace 2 \ rbrace、1）= 9 + 18 = 27 \ end {cases} = 23 $$
S = 3
$$ \ small Cost（1、\ lbrace 2、3、4 \ rbrace、1）= \ begin {cases} d [1、2] + Cost（2、\ lbrace 3、4 \ rbrace、1）= 10 + 25 = 35 \\ d [1、3] + Cost（3、\ lbrace 2、4 \ rbrace、1）= 15 + 25 = 40 \\ d [1、4] + Cost（4、\ lbrace 2、3 \ rbrace、1）= 20 + 23 = 43 = 35 cost（1、\ lbrace 2,3,4 \ rbrace）、1）\\ d [1,2] + cost（2、\ lbrace 3,4 \ rbrace 、1）= 10 + 25 = 35 \\ d [1,3] + cost（3、\ lbrace 2,4 \ rbrace、1）= 15 + 25 = 40 \\ d [1,4] + cost（4 、\ lbrace 2,3 \ rbrace、1）= 20 + 23 = 43 = 35 \ end {cases} $$
最小コストパスは35です。
コストから始める {1, {2, 3, 4}, 1}、の最小値を取得します d [1, 2]。いつs = 3、1から2（コストは10）のパスを選択してから、逆方向に進みます。いつs = 2、の最小値を取得します d [4, 2]。2から4（コストは10）のパスを選択してから、逆方向に進みます。
いつ s = 1、の最小値を取得します d [4, 3]。パス4から3（コストは9）を選択し、次に進みます。s = Φステップ。の最小値を取得しますd [3, 1] （コストは6です）。
