bitDPで巡回セールスマン問題を解いてみる

頂点数が18程度の巡回セールスマン問題の解法を紹介します。

巡回セールスマン問題

巡回セールスマン問題

• 都市の集合と2都市間の移動コストが与えられる。
• 全ての都市をちょうど一度ずつ訪れて出発地に戻る閉路のうちで、総移動コストが最小のものを求める。

都市 $N$ の数が問題になります。仮に順列全探索を行う場合

• $N=10$ の場合
  閉路は10の階乗（10!）= 3628800 通りある。1通り当たり、10回の移動コストを加える必要があり、約 3.6 × 10⁷ 回の演算が必要となります。
• $N=11$ の場合
  11! × 11 は、約 4.4 × 10⁸ 回の演算が必要となります。
  $N=12$ の場合
  12! × 12 は、約 5.7 × 10⁹ 回の演算が必要となります。

競技プログラミングの採点サーバは、1秒あたり10⁸程度のループが処理できると考えられています。N=11の場合は微妙で、N=12の場合は間に合わないと思われます。

bitDPの適用

bitDPは、与えられた集合の部分集合を遷移させるDP（Dynamic Programming : 動的計画法）です。

巡回セールスマン問題では、配列 dp の第一の添え字で訪れた都市の集合を、第二の添え字で最後に訪れた都市を表します。

先にコードを示します。dist[j][k] は、都市jから都市kの移動コストを表します。

	vector<vector<int>> dp((1 << n), vector<int>(n, INF));
	dp[0][0] = 0;
	for (int i = 0; i < (1 << n); ++i) {
		for (int j = 0; j < n; ++j) {
			if (((i & (1 << j)) == 0)&&(i != 0)) {
				continue;
			}
			for (int k = 0; k < n; ++k) {
				if ((i & (1 << k)) == 0) {
					int v = (i | (1 << k));
					dp[v][k] = min(dp[v][k], dp[i][j] + dist[j][k]);
				}
			}
		}
	}

プログラムの解説です。

• 閉路なので、都市0から都市0の閉路の最小値として考えます。これは、出発する都市に最小値は依存しないためです。
• 添え字 i は、n個の都市の部分集合を2進数で表現しています（3行目）。
• 添え字 j は、最後（直前）に訪れた都市です。
• 添え字 k は、まだ訪れていない都市です。
  • 最初の都市0は訪れていないことにしているため、i=0 の時は、すべての都市について、j → k 間の処理をします（2行目の初期化と5行目の後半の条件）。
  • v = (i | (1 << k)) は、都市 k を加えた都市の集合となります。

dp[(1 << n) – 1][0] が最小値となります。うまいやり方だと思います。

計算量は、$O \left(N^2\,2^N \right)$ となります（プログラムの構造をご覧ください）。$N=12$ の場合、 5.9 × 10⁵ となります。$N=18$ の場合でも 8.5 × 10⁷ です。競技プログラミングでは、$N=13$ から $N=18$ の範囲で問題が出される場合が多いようです。

テスト

AIZU ONLINE JUDGE で出題されている問題でアルゴリズムをテストします。以下が問題のリンク先です。

DPL 2_A問題 Traveling Salesman Problem

都市数 $n$ の制約は、$2 \leqq n \leqq 15$ となっています。このため順列全探索では、時間が間に合いません。bitDPを適用してこの問題を解きます。※テンプレートと変数名を合わせるため、頂点の数を n、設定された辺の数を m としました。

また、距離を表す dist は設定がない場合は、INF（問題範囲外の大きな数）を設定して、dist[j][k] が INF のときは、更新しないようにしています（28行目に追加した条件）。

プログラムは以下です。AC判定となります。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define INF (1LL << 30)

int main()
{
	int n, m;
	cin >> n >> m;
	vector<vector<int>> dist(n, vector<int>(n, INF));
	for (int i = 0; i < m; ++i) {
		int s, t, d;
		cin >> s >> t >> d;
		dist[s][t] = d;
	}

	vector<vector<int>> dp((1 << n), vector<int>(n, INF));
	dp[0][0] = 0;
	for (int i = 0; i < (1 << n); ++i) {
		for (int j = 0; j < n; ++j) {
			if (((i & (1 << j)) == 0)&&(i != 0)) {
				continue;
			}
			for (int k = 0; k < n; ++k) {
				if (((i & (1 << k)) == 0)&&(dist[j][k] < INF)) {
					int v = (i | (1 << k));
					dp[v][k] = min(dp[v][k], dp[i][j] + dist[j][k]);
				}
			}
		}
	}

	if (dp[(1 << n) - 1][0] == INF) {
		cout << -1 << endl;
	} else {
		cout << dp[(1 << n) - 1][0] << endl;
	}

	return 0;
}

最後に

応用範囲が広い bitDPですが、この巡回セールスマン問題への適用を起点にして、理解を深めていきたいです。