巡回セールスマン問題： Python, C++ アルゴリズム

巡回セールスマン問題 (TSP) とは何ですか?

巡回セールスマン問題 (TSP) は、理論的コンピューターサイエンスの古典的な組み合わせ論の問題です。この問題は、すべてのノードを XNUMX 回だけ訪問し、元の都市に戻るという条件で、グラフ内の最短経路を見つけるように求められます。

問題文には、都市のリストと各都市間の距離が示されています。

目的： 元の都市からスタートするには、一度だけ他の都市を訪問し、再度元の都市に戻ります。私たちの目標は、往復ルートを完了するための最短経路を見つけることです。

TSPの例

ここでは、1、2、3、4 が都市を表し、各エッジに関連付けられた重みがそれらの都市間の距離を表すグラフが表示されます。

目標は、元の都市から開始し、他の都市またはノードを XNUMX 回だけ訪問しながらグラフを横断し、元の都市に戻るツアーの最短パスを見つけることです。

上のグラフの場合、最適なルートは最小コストパスに従うことです。 1-2-4-3-1. この最短ルートの費用は 10+25+30+15 = 80 になります。

巡回セールスマン問題に対するさまざまな解決策

巡回セールスマン問題 (TSP) は、多項式時間アルゴリズムがないため、NP 困難問題として分類されます。都市の数が増えると、複雑さは指数関数的に増加します。

巡回セールスマン問題 (tsp) を解決するには、複数の方法があります。一般的なソリューションには次のようなものがあります。

強引なアプローチは単純な方法です 巡回セールスマンの問題を解決するために。このアプローチでは、まず考えられるすべてのパスを計算し、次にそれらを比較します。 n 個の都市で構成されるグラフ内のパスの数は次のとおりです。 n! この強引なアプローチで巡回セールスマン問題を解決するには、計算コストが非常に高くなります。

分岐限定メソッド: このアプローチでは、問題はサブ問題に分割されます。これらの個々の部分問題を解決することで、最適な解決策が得られます。

このチュートリアルでは、巡回セールスマンの問題を解決するための、この分岐限定メソッドの再帰バージョンである動的プログラミングアプローチを示します。

動的プログラミング 考えられるすべてのルートを解析して最適解を求める手法です。巡回セールスマンの問題を比較的高いコストで解決する的確な解決方法の一つです。貪欲なメソッド最適に近いソリューションを提供します。

このアプローチの計算の複雑さは O(N^2 * 2^N) これについてはこの記事の後半で説明します。

最近傍法 は、最も近い隣接ノードを選択するヒューリスティックベースの貪欲なアプローチです。このアプローチは、動的アプローチよりも計算コストが低くなります。ただし、最適なソリューションが保証されるわけではありません。この方法は、最適に近いソリューションに使用されます。

巡回セールスマン問題のアルゴリズム

動的プログラミングアプローチを使用して、巡回セールスマン問題 (TSP) を解決します。

アルゴリズムを開始する前に、いくつかの用語について理解しておきましょう。

頂点と辺の集合であるグラフ G=(V, E)。
V は頂点のセットです。
E はエッジのセットです。
頂点はエッジを介して接続されます。
Dist(i,j) は、XNUMX つの頂点 i と j 間の非負の距離を示します。

S が都市のサブセットであり、{1, 2, 3, …, n} に属していると仮定します。ここで、1、2、3…n は都市、i、j はそのサブセット内の XNUMX つの都市です。ここで、cost(i, S, j) は、S 内のノードを訪れる最短経路の長さとして定義されます。これは、それぞれ i と j として開始点と終了点を持つちょうど XNUMX 回です。

たとえば、cost (1, {2, 3, 4}, 1) は最短パスの長さを示します。ここで、

開始都市は 1 です
都市 2、3、4 は XNUMX 回のみ訪問されます
終点は1です

動的計画アルゴリズムは次のようになります。

cost(i, , i) = 0 と設定します。これは、i で開始および終了し、コストが 0 であることを意味します。
|S| のとき> 1 の場合、cost(i, S, 1) = ∝ (i !=1 ) と定義します。なぜなら、最初は、他の都市を経由して都市 i から都市 1 に到達するための正確なコストがわからないからです。
ここで、1 から開始してツアーを完了する必要があります。そうやって次の都市を選ばなければいけない――

コスト(i, S, j)=最小コスト(i, S−{i}, j)+dist(i,j) ただし、i∈S および i≠j

与えられた図の場合、隣接行列は次のようになります。

dist(i,j)	1	2	3	4
1	0	10	15	20
2	10	0	35	25
3	15	35	0	30
4	20	25	30	0

アルゴリズムがどのように機能するかを見てみましょう。

ステップ1） 都市 1 から出発し、他の都市を一度訪問し、都市 1 に戻る旅を検討しています。

ステップ2） S は都市のサブセットです。私たちのアルゴリズムによれば、すべての |S| > 1 に対して、距離 cost(i, S, 1) = ∝ を設定します。ここで cost(i, S, j) は、都市 i から開始し、S の都市を XNUMX 回訪れ、現在都市 j にいることを意味します。距離がまだわからないため、このパスコストを無限大に設定します。したがって、値は次のようになります。

コスト (2, {3, 4}, 1) = ∝ ; この表記は、都市 2 から開始し、都市 3、4 を通過して 1 に到達することを示しています。また、パスコストは無限大です。同様に-

コスト(3, {2, 4}, 1) = ∝

コスト(4, {2, 3}, 1) = ∝

ステップ3） ここで、S のすべてのサブセットについて、次のことを見つける必要があります。

コスト(i, S, j)=最小コスト(i, S−{i}, j)+dist(i,j)、ただしj∈Sおよびi≠j

これは、i から開始し、都市のサブセットを 1 回通過し、都市 j に戻るための最小コストのパスを意味します。移動が都市 1 から始まることを考慮すると、最適なパスコストは =cost(1, {他の都市}, XNUMX) となります。

それを実現する方法を見てみましょう。

ここで、S = {1, 2, 3, 4} となります。 2つの要素があります。したがって、サブセットの数は 4^16、つまり XNUMX になります。それらのサブセットは次のとおりです。

1) |S| = ヌル:

{Φ}

2) |S| = 1:

{{1}, {2}, {3}, {4}}

3) |S| = 2:

{{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}

4) |S| = 3:

{{1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {1, 3, 4}}

5) |S| = 4:

1 から開始するので、都市 1 を含むサブセットを破棄できます。

アルゴリズムの計算:

1) |S| = Φ:

コスト (2, Φ, 1) = dist(2, 1) = 10

コスト (3, Φ, 1) = dist(3, 1) = 15

コスト (4, Φ, 1) = dist(4, 1) = 20

2) |S| = 1:

コスト (2, {3}, 1) = dist(2, 3) + コスト (3, Φ, 1) = 35+15 = 50

コスト (2, {4}, 1) = dist(2, 4) + コスト (4, Φ, 1) = 25+20 = 45

コスト (3, {2}, 1) = dist(3, 2) + コスト (2, Φ, 1) = 35+10 = 45

コスト (3, {4}, 1) = dist(3, 4) + コスト (4, Φ, 1) = 30+20 = 50

コスト (4, {2}, 1) = dist(4, 2) + コスト (2, Φ, 1) = 25+10 = 35

コスト (4, {3}, 1) = dist(4, 3) + コスト (3, Φ, 1) = 30+15 = 45

3) |S| = 2:

コスト (2, {3, 4}, 1) = 最小 [ dist[2,3]+コスト(3,{4},1) = 35+50 = 85,

dist[2,4]+コスト(4,{3},1) = 25+45 = 70 ] = 70

コスト (3, {2, 4}, 1) = 最小 [ dist[3,2]+コスト(2,{4},1) = 35+45 = 80,

dist[3,4]+コスト(4,{2},1) = 30+35 = 65 ] = 65

コスト (4, {2, 3}, 1) = 最小 [ dist[4,2]+コスト(2,{3},1) = 25+50 = 75

dist[4,3]+コスト(3,{2},1) = 30+45 = 75 ] = 75

4) |S| = 3:

コスト (1, {2, 3, 4}, 1) = 最小 [ dist[1,2]+コスト(2,{3,4},1) = 10+70 = 80

dist[1,3]+コスト(3,{2,4},1) = 15+65 = 80

dist[1,4]+コスト(4,{2,3},1) = 20+75 = 95 ] = 80

したがって、最適な解決策は次のようになります 1-2-4-3-1

疑似コード

Algorithm: Traveling-Salesman-Problem 
Cost (1, {}, 1) = 0 
for s = 2 to n do 
   for all subsets S belongs to {1, 2, 3, … , n} of size s 
      Cost (s, S, 1) = Infinity
   for all i Є S and i ≠ 1 
      Cost (i, S, j) = min {Cost (i, S – {i}, j) + dist(i, j) for j Є S and i ≠ j} 
Return min(i) Cost (i, {1, 2, 3, …, n}, j) + d(j, i)

Cでの実装/C++

ここでの実装は次のとおりです C++:

#include <bits/stdc++.h>
using namespace std;
#define V 4
#define MAX 1000000
int tsp(int graph[][V], int s)
{
    vector<int> vertex;
    for (int i = 0; i < V; i++)
        if (i != s)
            vertex.push_back(i);
    int min_cost = MAX;
    while(next_permutation(vertex.begin(), vertex.end()))
     {
        int current_cost = 0;
        int j = s;
        for (int i = 0; i < vertex.size(); i++) {
            current_cost += graph[j][vertex[i]];
            j = vertex[i];
        }
        current_cost += graph[j][s];
        min_cost = min(min_cost, current_cost);
        return min_cost;
	}
}
int main()
{
    int graph[][V] = { { 0, 10, 15, 20 },{ 10, 0, 35, 25 },{ 15, 35, 0, 30 },{ 20, 25, 30, 0 } };                      
    int s = 0;
    cout << tsp(graph, s) << endl;
    return 0;
}

出力：

での実装 Python

from sys import maxsize
from itertools, import permutations
V = 4
def tsp(graph, s):
	vertex = []
	for i in range(V):
		if i != s:
			vertex.append(i)
    min_cost = maxsize
	next_permutation=permutations(vertex)
	for i in next_permutation:
		current_cost = 0
		k = s
		for j in i:
			current_cost += graph[k][j]
			k = j
		current_cost += graph[k][s]
		min_cost = min(min_cost, current_cost)
		return min_cost
graph = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]
		s = 0
print(tsp(graph, s))

出力：

TSP へのアカデミックソリューション

コンピュータ科学者は、巡回セールスマン問題の改良された多項式時間アルゴリズムを何年もかけて研究してきました。今のところ、この問題は依然として NP 困難です。

ただし、近年、複雑さをある程度軽減した次のようなソリューションがいくつか公開されています。

古典的な対称 TSP は、ゼロサフィックス法によって解決されます。
生物地理学に基づく最適化アルゴリズムは、ＴＳＰとして計画可能な最適化問題を解決するための移行戦略に基づいている。
多目的進化アルゴリズムは、NSGA-II に基づいて複数の TSP を解決するために設計されています。
マルチエージェントシステムは、固定リソースで N 都市の TSP を解決します。

巡回セールスマン問題の応用

巡回セールスマン問題 (TSP) は、最も純粋な形式と修正された形式の両方で現実世界に適用されます。そのうちのいくつかは次のとおりです。

マイクロチップの企画、物流、製造: チップ挿入の問題はマイクロチップ業界では当然発生します。これらの問題は、巡回セールスマン問題として計画できます。
DNAシークエンシング: 巡回セールスマン問題を少し修正すると、DNA 配列決定に使用できます。ここで、都市は DNA フラグメントを表し、距離は XNUMX つの DNA フラグメント間の類似性の尺度を表します。
天文学巡回セールスマン問題は、天文学者がさまざまな天体の観測に費やす時間を最小限に抑えるために利用されます。
最適制御問題: 巡回セールスマン問題定式化は最適制御問題に応用できます。他にもいくつかの制約が追加される可能性があります。

TSPの複雑性分析

時間計算量： 全部で2あります^N各ノードのサブ問題。したがって、部分問題の総数は N*2 になります。^N。各副問題を解決するには直線的な時間が必要です。起点ノードが指定されていない場合は、N 個のノードに対してループを実行する必要があります。
したがって、最適解の総時間計算量は、ノード数 * サブ問題の数 * 各サブ問題を解くのにかかる時間になります。時間計算量は、O(N² * 2^N)。
スペースの複雑さ： 動的プログラミング手法では、メモリを使用して C(S, i) を保存します。ここで、S は頂点セットのサブセットです。合計2つあります^N各ノードのサブセット。したがって、空間計算量は O(2^N) です。

次に、次について学びます。エラトステネスのふるいアルゴリズム

よろしければ：