最近傍法(ニアレストネイバーアルゴリズム)で巡回セールスマン問題を解くC++プログラム

巡回セールスマン問題(TSP:Traveling Salesman Problem)は、「すべての都市をそれぞれ一度だけ訪れ、最後に出発地点へ戻る」という条件のもとで、移動コストの合計が最小となる経路を求める古典的な組合せ最適化問題です。本記事では、その代表的な近似解法である最近傍法(Nearest Neighbour Algorithm)を用いて、この問題をC++で実装する方法を解説します。

最近傍法のアルゴリズム

最近傍法は貪欲法(グリーディ法)に基づくシンプルな手法で、「現時点で最も良さそうな選択」を繰り返すことで、少ない計算コストで比較的良い解を得られるのが特徴です。

処理の手順

1. 任意の都市を出発点として選び、訪問済みとしてマークします。
2. 現在いる都市から、未訪問の都市の中で最も近い都市へ移動します。
3. すべての都市を訪問し終えるまで、手順2を繰り返します。
4. 最後に出発点へ戻り、巡回経路を完成させます。

擬似コード

Begin
    出発都市を current に設定し、訪問済みにする
    totalCost = 0 と初期化
    すべての都市を訪問するまで繰り返し:
        未訪問の都市の中から current に最も近い都市 next を探索
        totalCost に distance(current, next) を加算
        current を next に更新し、next を訪問済みにする
    totalCost に distance(current, 出発都市) を加算
    totalCost を出力
End

C++サンプルコード

以下は、4都市間の距離を隣接行列で定義し、最近傍法によって巡回経路とその総コストを求めるC++プログラムです。

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    // 都市間の距離を隣接行列で定義(4都市の例)
    int g[4][4] = {
        { 0, 10, 15, 20 },
        {10,  0, 35, 25 },
        {15, 35,  0, 30 },
        {20, 25, 30,  0 }
    };
    const int n = 4;

    vector<bool> visited(n, false);   // 各都市の訪問状態
    vector<int> path;                 // 訪問順序の記録用
    int current = 0;                  // 出発都市は 0 番
    visited[current] = true;
    path.push_back(current);
    int totalCost = 0;

    // 未訪問の都市のうち最も近い都市を順に選択
    for (int step = 1; step < n; ++step) {
        int nextCity = -1;
        int minDist = INT_MAX;
        for (int j = 0; j < n; ++j) {
            if (!visited[j] && g[current][j] < minDist) {
                minDist = g[current][j];
                nextCity = j;
            }
        }
        visited[nextCity] = true;
        totalCost += minDist;
        path.push_back(nextCity);
        current = nextCity;
    }

    // 最後に出発都市へ戻る
    totalCost += g[current][path.front()];
    path.push_back(path.front());

    cout << "訪問順序: ";
    for (size_t i = 0; i < path.size(); ++i) {
        cout << path[i];
        if (i + 1 < path.size()) cout << " -> ";
    }
    cout << "\n最小コスト: " << totalCost << endl;
    return 0;
}

実行結果

訪問順序: 0 -> 1 -> 3 -> 2 -> 0
最小コスト: 80

都市0を出発すると、直近の都市1(距離10)→ 都市3(距離25)→ 都市2(距離30)の順に移動し、最後に都市0へ戻る(距離15)ため、合計コストは 10 + 25 + 30 + 15 = 80 となります。

計算量と注意点

最近傍法の計算量は O(n²)(nは都市数)であり、全数探索の O(n!) と比べて非常に高速です。ただし、あくまで局所的な判断を積み重ねる手法のため、必ずしも最適解が得られるとは限らず、得られる解は近似解となります。実務では、最近傍法で求めた初期解を2-opt法などの改善手法でさらに洗練させるアプローチがよく用いられます。