香川大学SLPからお届け！（Vol.87掲載）

著者：大村 空良

プログラミングにおいて重要な要素の一つが、プログラムの実行速度です。プログラムの実行速度は、より良いアルゴリズムを選択することで大きく改善できます。今回は、巡回セールスマン問題を解く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;
}