香川大学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;
}

#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;
}

#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}}};')

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;
}

#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;
}

#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;
}

#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;

}