AtCoder

典型アルゴリズム問題集 C問題(巡回セールスマン問題)を解く

AtCoder_Typical_algorithm

AtCoder で公開されている「典型アルゴリズム問題集」のC問題をC++で解いてみました。

C問題 二分探索

問題はリンク先をご覧ください。

C 巡回セールスマン問題

巡回セールスマン問題を紹介します。

解答案

以下を「巡回セールスマン問題」と呼んでいます。

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

$N = 8$ 程度であれば、順列をすべて全探索することで解くことができます。C++の場合、next_permutation を使って解くことができます。

今回の場合、$2 \leqq N \leqq 13$ と制約が大きくなり順列全探索では解くことができません。この大きさの場合、bitDPという方法が使えます。この方法については、別記事ですでに紹介していました。

C++ プログラム例

bitDP を使って解きました。コストが32bit整数に収まらない場合があります。このため、64bit整数で処理をしました。

以下が、C++プログラムとなります。

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

using namespace std;

typedef long long int ll;
#define INF (1LL << 60)

int main()
{
	int n;
	cin >> n;
	vector<vector<ll>> a(n, vector<ll>(n));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> a[i][j];
		}
	}

	vector<vector<ll>> dp((1 << n), vector<ll>(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] + a[j][k]);
				}
			}
		}
	}

	cout << dp[(1 << n) - 1][0] << endl;

	return 0;
}

AC(Accepted=正しいプログラム)と判定されました。

最後に

すでに記事で紹介している内容ですが紹介しました。繰り返し紹介することによって、理解が深まればと考えています。

この問題集は、わたくしには、ちょうど良い難易度でした。引き続き解答案を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA