【C++】巡回セールスマン問題（TSP）を解くプログラム｜全順列探索による最短経路の求め方

巡回セールスマン問題（Travelling Salesman Problem、TSP）は、すべての都市を一度ずつ訪れ、最後に出発地点の都市へ戻るまでの最短経路を求める古典的な組合せ最適化問題です。グラフ理論においては、グラフ上のすべてのノードをカバーする最短経路を見つけるために用いられる手法です。

本記事では、next_permutationによる全順列探索を利用して、グラフの最短経路を求めるC++プログラムを紹介します。

アルゴリズム

Begin
   変数 vr = 4 をグローバルに定義する。
   巡回セールスマン問題を実装する整数型関数 TSP を宣言する。
   2次元行列としてグラフ grph[][] と整数型変数 p を宣言し、引数として渡す。
   vector 型の変数 ver を宣言する。
   for (int i = 0; i < vr; i++)
      if (i != p) ならば
         push_back(i) を呼び出し、出発頂点以外のすべての頂点の値を格納する。
         グラフの最小重みを格納するため、m_p = INT_MAX で初期化する。
   do
        整数型変数 cur_pth と k を宣言する。
           cur_pth = 0 で初期化する。
           k = p で初期化する。
       for (int i = 0; i < ver.size(); i++)
           cur_pth += grph[k][ver[i]]。
           k = ver[i]。
       cur_pth += grph[k][p]。
       m_p = min(m_p, cur_pth) により最小重みの値を更新する。
       while (next_permutation(ver.begin(), ver.end()))。
       m_p を返す。
   整数型の2次元行列としてグラフ grph[][] を宣言する。
      grph[][] の各値を初期化する。
   整数型変数 p を宣言する。
      p = 0 で初期化する。
   「The result is: 」を出力する。
   TSP() 関数の戻り値を出力する。
End.

サンプルコード

#include <bits/stdc++.h>
using namespace std;
#define vr 4
int TSP(int grph[][vr], int p) // 巡回セールスマン問題を実装 {
   vector<int> ver; //
   for (int i = 0; i < vr; i++)
      if (i != p)
         ver.push_back(i);
         int m_p = INT_MAX; // グラフの最小重みを格納
   do {
      int cur_pth = 0;
      int k = p;
      for (int i = 0; i < ver.size(); i++) {
         cur_pth += grph[k][ver[i]];
         k = ver[i];
      }
      cur_pth += grph[k][p];
      m_p = min(m_p, cur_pth); // 最小重みの値を更新
   }
   while (next_permutation(ver.begin(), ver.end()));
   return m_p;
}
int main() {
   int grph[][vr] = { { 0, 5, 10, 15 }, // 行列形式で表したグラフの値
      { 5, 0, 20, 30 },
      { 10, 20, 0, 35 },
      { 15, 30, 35, 0 }
   };
   int p = 0;
   cout<< "\n The result is: "<< TSP(grph, p) << endl;
   return 0;
}

実行結果

The result is: 75

プログラムのポイント

• 出発頂点（p = 0）以外の頂点を vector に格納し、next_permutation ですべての訪問順序（順列）を生成します。
• 各順列について、出発点から全頂点を経由して出発点に戻るまでの総コストを計算し、これまでの最小値より小さければ更新します。
• 最終的な最小コストは 75 となります。

なお、この手法の計算量は O((n−1)!) であり、頂点数が増えると爆発的に増加します。そのため、実用的な規模の問題では動的計画法（DP）を用いた Held-Karp アルゴリズムなど、より効率的な手法が採用されることが一般的です。