著者：大村 空良
プログラミングにおいて重要な要素の一つが、プログラムの実行速度です。プログラムの実行速度は、より良いアルゴリズムを選択することで大きく改善できます。今回は、巡回セールスマン問題を解くC++プログラムを、アルゴリズムを変更して高速化した例を紹介します。
シェルスクリプトマガジン Vol.87は以下のリンク先でご購入できます。
図2 図1の巡回セールスマン問題を解くC++コード「sample1.cpp」
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#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」
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#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」
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
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」
|
1 2 3 4 5 6 7 8 9 10 11 12 |
#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」
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#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」
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#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; } |
