著者：大村 空良
プログラミングにおいて重要な要素の一つが、プログラムの実行速度です。プログラムの実行速度は、より良いアルゴリズムを選択することで大きく改善できます。今回は、巡回セールスマン問題を解くC++プログラムを、アルゴリズムを変更して高速化した例を紹介します。
シェルスクリプトマガジン Vol.87は以下のリンク先でご購入できます。
図2 図1の巡回セールスマン問題を解くC++コード「sample1.cpp」
#include <bits/stdc++.h>
using namespace std;
int main() {
int n = 4, ans = 1e9-1, sum;
int a[4][4] = {
{0, 3, 7, 8},
{3, 0, 4, 4},
{7, 4, 0, 3},
{8, 4, 3, 0}
};
vector<int> v_ans, v = {0, 1, 2, 3};
do {
//初期化
sum = 0;
//距離を足す
for (int i = 1; i < n; i++) {
sum += a[v[i-1]][v[i]];
}
sum += a[v[n-1]][v[0]];
//比較
if (ans > sum) {
ans = sum;
v_ans = v;
}
} while (next_permutation(v.begin(), v.end()));
//結果表示
for_each(v_ans.begin(), v_ans.end(),
[](int& item) { item++; });
copy(v_ans.begin(), v_ans.end(),
ostream_iterator<int>(cout, "→"));
cout << v_ans[0] << endl;
cout << ans << endl;
return 0;
}図3 都市数を変えられるように図2のコードを拡張した「sample2.cpp」
#include <bits/stdc++.h>
#include "sales.h"
using namespace std;
int main() {
int ans = 1e9-1, sum;
vector<int> v_ans;
do {
sum = 0;
for (int i = 1; i < n; i++) {
sum += a[v[i-1]][v[i]];
}
sum += a[v[n-1]][v[0]];
if (ans > sum) {
ans = sum;
v_ans = v;
}
} while (next_permutation(v.begin(), v.end()));
for_each(v_ans.begin(), v_ans.end(),
[](int& item) { item++; });
copy(v_ans.begin(), v_ans.end(),
ostream_iterator<int>(cout, "→"));
cout << v_ans[0] << endl;
cout << ans << endl;
return 0;
}図4 ヘッダーファイル生成用のPythonスクリプト「make_header.py」
import random
import sys
text = "dummy"
while not text.isdecimal():
print("整数値を入力してください: ",
file=sys.stderr, end='')
text = input()
num = int(text)
if num > 15 or num < 1:
sys.exit(1)
array = [[0] * num for i in range(num)]
random.seed()
for i in range(num):
for j in range(num):
if i != j:
if array[j][i] != 0:
array[i][j] = array[j][i]
else:
array[i][j] = random.randint(1, 9)
print('#include <vector>')
print('using namespace std;')
print(f'int n = {num};')
print(f'int a[{num}][{num}] = {{')
for i in range(num):
line = str(array[i])[1:-1]
print('{' + line + '},')
print('};')
line = list(range(0, num))
line = str(line)[1:-1]
print(f'vector<int> v = {{{line}}};')図5 フィボナッチ数を求めるC++コード「sample3.cpp」
#include <bits/stdc++.h>
using namespace std;
unsigned long long fib(char n) {
if ((n <= 0) || (n > 93)) return 0;
if (n == 1) return 1;
return fib(n - 1) + fib(n - 2);
}
int main() {
char n = 5;
cout << fib(n) << endl;
return 0;
}図7 動的計画法を用いて改良したコード「sample4.cpp」
#include <bits/stdc++.h>
using namespace std;
unsigned long long fib(char n) {
if ((n <= 0) || (n > 93)) return 0;
if (n == 1) return 1;
unsigned long long f[128];
f[0] = 0;
f[1] = 1;
for (char i = 2; i <= n; i++) {
f[i] = f[i - 1] + f[i - 2];
}
return f[n];
}
int main() {
char n = 5;
cout << fib(n) << endl;
return 0;
}図10 動的計画法を用いて改良したコード「sample5.cpp」
#include <bits/stdc++.h>
#include "sales.h"
using namespace std;
int main() {
int dp[(1<<n)][n];
for (int i = 0; i < (1<<n); i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = 1e9-1;
}
}
dp[0][0] = 0;
for (int i = 0; i < (1<<n); i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
if (i==0 || !(i & (1<<k)) && (i & (1<<j))) {
if( j != k ) {
dp[i | (1<<k)][k] = min(dp[i | (1<<k)][k],
dp[i][j] + a[j][k]);
}
}
}
}
}
cout << dp[(1<<n) - 1][0] << endl;
return 0;
}