巡回セールスマン問題（TSP）とは？ビットDPで最短経路を求めるアルゴリズムとC++実装

巡回セールスマン問題（TSP）とは

巡回セールスマン問題（Travelling Salesman Problem：TSP）は、ある都市を出発点としたセールスマンが、リスト上のすべての都市を一度ずつ訪問し、最後に出発地へ戻るとき、移動コストの合計が最小となる経路を求める古典的な組合せ最適化問題です。各都市間の移動コストはあらかじめ与えられているものとします。

この問題では、どの都市からでも他の任意の都市へ直接移動できる必要があるため、扱うグラフは完全グラフでなければなりません。

グラフ理論の観点で言えば、この問題は最小重みハミルトン閉路を見つけることに相当します。

入力と出力

入力には、都市間の移動コストをまとめたコスト行列を用います。

入力：
コスト行列
0  20 42 25 30
20  0 30 34 15
42 30  0 10 10
25 34 10  0 25
30 15 10 25  0

出力：
Distance of Travelling Salesman: 80

アルゴリズム

ここでは、ビットマスク動的計画法（Bitmask DP）を用いた再帰関数 travellingSalesman(mask, pos) を使用します。都市の訪問状況をビット列（マスク）で管理し、計算結果をdpテーブルにキャッシュすることで、同じ状態の再計算を防ぎます。また、すべてのノードが訪問済みであることを示す値として VISIT_ALL を用意します。

入力： 訪問済み都市を表すmask値、現在位置pos
出力： すべての都市を訪問する最短経路のコスト

Begin
    if mask = VISIT_ALL, then //すべての都市を訪問済みの場合
        return cost[pos, 0]
    if dp[mask, pos] ≠ -1, then //すでに計算済みの場合
        return dp[mask, pos]
    finalCost := ∞

    for all cities i, do
        tempMask := (1 を左へ i 回シフト)
        if mask AND tempMask = 0, then //都市iが未訪問なら
            tempCost := cost[pos, i] +
            travellingSalesman(mask OR tempMask, i)
            finalCost := finalCost と tempCost の最小値
    done

    dp[mask, pos] = finalCost
    return finalCost
End

C++での実装例

#include<iostream>
#define CITY 5
#define INF 9999
using namespace std;

int cost[CITY][CITY] = {
    {0, 20, 42, 25, 30},
    {20, 0, 30, 34, 15},
    {42, 30, 0, 10, 10},
    {25, 34, 10, 0, 25},
    {30, 15, 10, 25, 0}
};

int VISIT_ALL = (1 << CITY) - 1;

int dp[32][5];   // サイズ (2^n, n) の配列を用意

int travellingSalesman(int mask, int pos) {
    if(mask == VISIT_ALL)      // すべての都市が訪問済みの場合
        return cost[pos][0];   // 現在の都市から出発地へのコストを返す

    if(dp[mask][pos] != -1)    // すでに計算済みの場合
        return dp[mask][pos];

    int finalCost = INF;

    for(int i = 0; i < CITY; i++) {
        if((mask & (1 << i)) == 0) {   // i番目のビットが0なら都市iは未訪問
            int tempCost = cost[pos][i] + travellingSalesman(mask | (1 << i), i);   // 都市iを訪問済みとして再帰呼び出し
            finalCost = min(finalCost, tempCost);
        }
    }
    return dp[mask][pos] = finalCost;
}

int main() {
    int row = (1 << CITY), col = CITY;
    for(int i = 0; i < row; i++)
        for(int j = 0; j < col; j++)
            dp[i][j] = -1;   // dp配列を-1で初期化
    cout << "Distance of Travelling Salesman: ";
    cout << travellingSalesman(1, 0);   // 初期状態のmaskは0001（0番目の都市は訪問済み）
}

実行結果

Distance of Travelling Salesman: 80

計算量について

このアルゴリズムの時間計算量は O(2ⁿ × n²)、空間計算量は O(2ⁿ × n) です。すべての順列を調べ上げる全数探索（(n−1)! 通り）に比べれば大幅に効率化されていますが、それでも指数オーダーであるため、都市数が増えると計算量は急激に増大します。そのため、大規模なインスタンスに対しては、貪欲法・局所探索法・遺伝的アルゴリズムなどの近似解法やヒューリスティクスが実務でよく利用されます。