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 Є SC(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です)。