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

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

巡回セールスマン問題（TSP）は、理論計算機科学における古典的な組み合わせ最適化問題です。都市のグラフが与えられたとき、TSPはすべてのノードをちょうど一度ずつ訪れ、出発都市に戻る最短経路を求める問題です。

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

目的： 出発都市からスタートし、他のすべての都市をそれぞれ一度ずつ訪れ、出発都市に戻る。目標は、最短の往復ルートを見つけることである。

TSPの例

下のグラフでは、1、2、3、4が都市を表し、各辺の重みはそれらの都市間の距離を表しています。

目標は、出発都市から始まり、他のすべての都市をちょうど一度ずつ訪れ、出発都市に戻る最短のツアーを見つけることです。

上記のグラフの場合、最適なルートは 1-2-4-3-1最短ツアーの費用は 10 + 25 + 30 + 15 = 80.

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

巡回セールスマン問題は、既知の多項式時間アルゴリズムでは厳密に解くことができないため、NP困難問題に分類される。その複雑さは、都市の数に対して指数関数的に増加する。

TSPを攻撃する方法は複数あります。最も一般的なアプローチは次のとおりです。

力任せのアプローチ： 単純な方法では、考えられるすべての経路を計算して比較します。n 個の都市を持つグラフの経路の数は n!そのため、約10都市を超えるような場合、総当たり攻撃は計算コストが非常に高くなる。

分枝限定法： この問題は複数の部分問題に分割され、それらの部分問題の解を組み合わせることで最適な解が得られます。効果的な枝刈りによって、現在の最良コストを下回れない部分的な経路は破棄されます。

このチュートリアルでは、 動的プログラミングアプローチこれは、分岐限定法のメモ化バージョンであり、ベルマン・ヘルド・カープアルゴリズムに一致する。

動的計画法: これは、重複部分を再利用して最適解を求める正確な方法です。ping 部分問題の結果。ほぼ最適解よりも遅い。 貪欲なメソッドしかし、常にグローバル最適解を返します。

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

最近傍法： 常に最も近い未訪問都市へジャンプする、ヒューリスティックな貪欲法。動的計画法よりもはるかに安価だが、最適な経路を保証するものではないため、厳密な最小値よりも速度が重要な場合など、準最適な解を求める際に用いられる。

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

TSPを解くために動的計画法を用います。アルゴリズムを開始する前に、いくつかの用語を整理しておきましょう。

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

S を {1, 2, 3, …, n} から抽出した都市のサブセットとし、i と j はそのサブセット内の 2 つの都市とする。 cost(i, S, j) は、i から始まり、S 内のすべての都市をちょうど 1 回ずつ訪れ、j で終わる最短経路の長さです。

たとえば、 cost(1, {2, 3, 4}, 1) 最短経路を表す。

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

動的計画法の漸化式は次のとおりです。

• 作成セッションプロセスで cost(i, {}, i) = 0つまり、コストゼロでiから出発し、iで終了するということです。
• 　　 |S| > 1、定義 cost(i, S, 1) = ∞ の i ≠ 1なぜなら、実際のツアー料金はまだ不明だからです。
• 都市1から始めて、次の都市を選択します。 cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ] の i ∈ S (NAIST) と i ≠ j.

上記のグラフの場合、隣接行列は次のようになります。

アルゴリズムの進行手順は以下のとおりです。

ステップ1） 旅は都市1から始まり、他のすべての都市を一度ずつ訪れ、都市1に戻ります。

ステップ2） S は都市のサブセットです。|S| > 1 のすべての都市について、初期化します。 cost(i, S, 1) = ∞。 ここに cost(i, S, j) これは、i から始まり、S の都市を 1 回ずつ訪れ、j に到達するツアーを表します。この時点では距離が不明なので、無限遠から始めます。したがって、値は次のとおりです。

cost(2, {3, 4}, 1) = ∞ これは、都市2から出発し、都市3と4を経由して都市1に到達するが、費用は不明であることを意味する。同様に：

cost(3, {2, 4}, 1) = ∞

cost(4, {2, 3}, 1) = ∞

ステップ3） S のすべての部分集合について、以下を計算する。

cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ]ここで、 j ∈ S (NAIST) と i ≠ j.

これは、i から始まり、都市のサブセットを 1 回訪問し、j​​ に戻る最小コストのツアーです。ツアーは都市 1 から始まるため、最適なコストは cost(1, {other cities}, 1).

繰り返し処理を段階的に行う

S = {1, 2, 3, 4} です。要素は 4 つあるので、部分集合の数は 2^4 = 16それらの部分集合は次のとおりです。

1) |S| = 0: {Φ}

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, 2, 3, 4}}

ツアーは都市1から始まるため、中間コストを計算する際に、都市1を含むすべての部分集合を破棄することができます。

アルゴリズムの計算は次のように展開されます。

1) |S| = Φ:

• cost(2, Φ, 1) = dist(2, 1) = 10
• cost(3, Φ, 1) = dist(3, 1) = 15
• cost(4, Φ, 1) = dist(4, 1) = 20

2) |S| = 1:

• cost(2, {3}, 1) = dist(2, 3) + cost(3, Φ, 1) = 35 + 15 = 50
• cost(2, {4}, 1) = dist(2, 4) + cost(4, Φ, 1) = 25 + 20 = 45
• cost(3, {2}, 1) = dist(3, 2) + cost(2, Φ, 1) = 35 + 10 = 45
• cost(3, {4}, 1) = dist(3, 4) + cost(4, Φ, 1) = 30 + 20 = 50
• cost(4, {2}, 1) = dist(4, 2) + cost(2, Φ, 1) = 25 + 10 = 35
• cost(4, {3}, 1) = dist(4, 3) + cost(3, Φ, 1) = 30 + 15 = 45

3) |S| = 2:

• cost(2, {3, 4}, 1) = min [ dist(2, 3) + cost(3, {4}, 1) = 35 + 50 = 85, dist(2, 4) + cost(4, {3}, 1) = 25 + 45 = 70 ] = 70
• cost(3, {2, 4}, 1) = min [ dist(3, 2) + cost(2, {4}, 1) = 35 + 45 = 80, dist(3, 4) + cost(4, {2}, 1) = 30 + 35 = 65 ] = 65
• cost(4, {2, 3}, 1) = min [ dist(4, 2) + cost(2, {3}, 1) = 25 + 50 = 75, dist(4, 3) + cost(3, {2}, 1) = 30 + 45 = 75 ] = 75

4) |S| = 3:

• cost(1, {2, 3, 4}, 1) = min [ dist(1, 2) + cost(2, {3, 4}, 1) = 10 + 70 = 80, dist(1, 3) + cost(3, {2, 4}, 1) = 15 + 65 = 80, dist(1, 4) + cost(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 in S and i != 1
        Cost (i, S, j) = min {Cost (i, S - {i}, j) + dist(i, j) for j in S and i != j}
Return min(i) Cost (i, {1, 2, 3, ..., n}, j) + d(j, i)

Cでの実装/C++

実装は以下のとおりです。 C++以下のバージョンでは、ソースの初期のバグが修正されています。 return すべてのツアーを列挙する代わりに、最初の順列の後に処理を終了してしまうバグ。

#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;
    do {
        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);
    } while (next_permutation(vertex.begin(), vertex.end()));

    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;
}

出力：

80

での実装 Python

その Python 実装は C++ バージョン。ソースの from itertools, import コンマのタイプミス、位置がずれた return 内側のループの内側、そして、 s = 0.

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
    for perm in permutations(vertex):
        current_cost = 0
        k = s
        for j in perm:
            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))

出力：

80

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

コンピュータ科学者たちは、巡回セールスマン問題に対するより優れた多項式時間アルゴリズムを求めて何十年も研究を続けてきた。しかし、今のところTSPはNP困難問題のままである。

いくつかの公開されている手法は、特定のTSPインスタンス群における実用上の複雑さを軽減する。

• 古典的な対称TSPは、 ゼロサフィックス法.
• その 生物地理学に基づく最適化アルゴリズム TSPに対応する最適化問題を解決するために、移行戦略を使用します。
• その 多目的進化アルゴリズム これは多目的TSP向けに設計されており、NSGA-IIをベースに構築されています。
• その マルチエージェントシステム この手法は、限られた計算リソースでN都市のTSP問題を解決する。
• その リン・カーニハンヒューリスティック そしてその後継者 州立病院 数百万の都市を対象とした場合でも、最適値から2～3%以内の精度でツアーを提供します。
• コンコード 切除平面法と分岐限定法を用いて、数万の都市を含むベンチマークインスタンスの正確な最適解を計算する。

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

巡回セールスマン問題は、現実世界では純粋な形と変形された形の両方で現れます。主な応用例は以下のとおりです。

• 計画、物流、マイクロチップ製造： マイクロチップ業界におけるチップ挿入問題は、ロボットアームの移動時間を最小化するために、巡回セールスマン問題の変形としてモデル化される。
• DNAシーケンス解析： DNAシーケンス解析では、都市がDNA断片を表し、距離が断片間の類似性を表すように修正されたTSPが用いられる。
• 天文学： 天文学者は、観測対象間で望遠鏡を旋回させるのに要する時間を最小限に抑えるために、TSP（巡回セールスマン問題）を利用する。
• 最適な制御： TSP（巡回セールスマン問題）の定式化は、複数の制約条件を満たしながら経路探索コストを最小化しなければならない最適制御問題をモデル化するものである。
• ラストマイル配送: AmazonUPSや食品配達アプリなどは、ドライバーの配送先を順番に並べるために、動的なTSP（巡回セールスマン問題）の変形版を解く。
• 倉庫ピッキング: ロボットと人間のピッカーは、配送センター内の移動時間を短縮するために、TSP（巡回セールスマン問題）で最適化されたルートに従って作業を行う。

TSPの複雑性分析

• 時間計算量： Held-Karpの動的計画法アプローチは2つの問題を解決します。^N 各開始ノードのサブセットにより、 N × 2^N 部分問題。各部分問題の組み合わせには線形時間が必要です。起点ノードが指定されていない場合は、N 個のノードを巡る外側のループが必要です。全体の時間計算量は O(N² × 2^N).
• スペースの複雑さ： DPテーブルには C(S, i) 頂点集合の各部分集合Sについて。^N ノードあたりのサブセット数なので、空間計算量は O(N × 2^N)これはしばしば次のように書かれます O(2^N) Nを固定値として扱う場合。

次に、 エラトステネスのふるいアルゴリズム.

よくあるご質問