最近傍アルゴリズムをC++で実装！巡回セールスマン問題の最小コストを求める方法

概要

本記事では、巡回セールスマン問題（TSP：Traveling Salesman Problem）を解くために用いられる最近傍アルゴリズムをC++で実装する方法を解説します。このプログラムは、すべてのノードを訪問するために必要な最小コストを、各辺を一度だけ通過するという条件のもとで計算します。

必要な関数と擬似コード

アルゴリズムの流れ

Begin
   Initialize c = 0, cost = 1000;
   Initialize g[][].
   function swap() is used to swap two values x and y.
   function cal_sum() to calculate the cost which take array a[] and size of array as input.
   Initialize sum = 0.
   for i = 0 to n
      compute s += g[a[i % 3]][a[(i + 1) % 3]];
   if (cost > s)
      cost = s
   function permute() is used to perform permutation:
   If there is one element in array
      call cal_sum().
   else
      for j = i to n
         swap (a+i) with (a + j)
         cal_sum(a+1, n)
         swap (a+i) with (a + j)
End

処理の流れを日本語で整理すると、以下のようになります。

• c：カウンタ変数、cost：現時点での最小コスト（初期値は十分大きな値1000）として初期化します。
• swap()：2つの値 x と y を入れ替える関数です。
• cal_sum()：配列 a[] とそのサイズを受け取り、経路全体のコストを計算します。現在の最小コストより小さければ更新します。
• permute()：配列の順列を再帰的に生成し、それぞれの順列に対して cal_sum() を呼び出してコストを評価します。

サンプルコード

#include<iostream>
using namespace std;

int c = 0, cost = 1000;
int g[3][3] = { {1,2,3},{4,5,8},{6,7,10}};

void swap(int *x, int *y) {
   int t;
   t = *x;
   *x = *y;
   *y = t;
}

void cal_sum(int *a, int n) {
   int i, s = 0;
   for (i = 0; i <= n; i++) {
      s += g[a[i % 3]][a[(i + 1) % 3]];
   }
   if (cost > s) {
      cost = s;
   }
}

void permute(int *a, int i, int n) {
   int j, k;
   if (i == n) {
      cal_sum(a, n);
   } else {
      for (j = i; j <= n; j++) {
         swap((a + i), (a + j));
         cal_sum(a + 1, n);
         swap((a + i), (a + j));
      }
   }
}

int main() {
   int i, j;
   int a[] = {1, 2, 3}; // 配列の要素
   permute(a, 0, 2);
   cout << "minimum cost:" << cost << endl;
}

コードのポイント

• 3×3 の配列 g[][] がグラフの重み（各ノード間の移動コスト）を表しています。
• cal_sum() では a[i % 3] と a[(i + 1) % 3] を使うことで、最後のノードから最初のノードへ戻る経路も含めてコストを計算できます。
• permute() はバックトラッキングの考え方を用いて、「スワップ → 評価 → 元に戻す」を繰り返しながら、すべての順列を網羅的に調べます。

実行結果

minimum cost:3

まとめ

このプログラムでは、順列をすべて生成してコストを比較することで、すべてのノードを訪問する際の最小コストを求めています。ただし、ノード数が増えると計算量は階乗オーダーで急増するため、大規模な問題には動的計画法や貪欲法などのヒューリスティクス手法と組み合わせるのが有効です。まずは小規模な例でアルゴリズムの動きを理解することをおすすめします。