AtCoder で公開されている「典型アルゴリズム問題集」の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＝正しいプログラム）と判定されました。
最後に
すでに記事で紹介している内容ですが紹介しました。繰り返し紹介することによって、理解が深まればと考えています。
この問題集は、わたくしには、ちょうど良い難易度でした。引き続き解答案を紹介していきます。
