巡回セールスマン問題を工夫せずに解く

はじめに

RPGゲームでドロップアイテムを求め周回していると「効率化したい」と思う事があるでしょう。敵のリポップ位置が決まっているならなおさら、理論上最高効率となる順路を知りたくなります。

このように「N箇所の目的地を一度ずつ訪れて元の場所に戻ってくる際、最適な順路はどうなるか」を求める問題は「巡回セールスマン問題」と呼ばれています。セールスマンは一刻も早くノルマを終わらせて家へ帰りたいのでしょう。お仕事ご苦労様です。

さて、この問題を数式を使ってちゃちゃっと解く方法は存在せず、全通り試して最短経路はどれか判断するしか方法がありません。こうなると手計算は不可能なので、コンピュータに解いてもらいましょう。
しかしながら、実はこの問題はコンピュータにとっても難しいのです。営業先が15個くらいまでならどうにかなりますが、それ以上になると計算が終わらないのです。

今回はそれを身を持って体験したいと考え、試してみることにしました。

目的

巡回セールスマン問題を一切工夫無しで解くとどのくらいの時間がかかるのかを調べる。

具体的な問題設定は以下の通りとする。
「原点にあるセーブポイントを出発し、N箇所ある敵の出現位置を巡って、再びセーブポイントに戻ってくるとする。N箇所の座標情報を元に、移動距離が最小となるような順路を求めよ」

方法

上記の問題を解くプログラムを組み、N=1から13まで変えながら処理時間を測る。なお、Nが14以上の場合については、それまでの結果から推測する事とする。
開発言語はC++で、GNU C++ Compilerを使ってコンパイルを行った。コンパイルオプションは特に指定せずデフォルトのままである。

なお、実行環境は13th Gen Intel(R) Core(TM) i7-13700である。

結果

N	秒数
1	1us
2	1us
3	1us
4	2us
5	6us
6	35us
7	249us
8	2ms 95us
9	19ms 971us
10	209ms 555us
11	2s427ms 370us
12	30s 579ms 202us
13	419s 167ms 383us

敵の出現箇所が10か所の場合、最短経路を求める計算は僅か0.2秒強しか掛からなかった。しかし11か所では処理時間が約11倍の2.4秒、12か所ではそのさらに12倍の30.5秒とどんどん増えていく。
このままいくと、例えば敵の出現箇所が18か所の場合は13年半ほどかかり、19か所なら256年、20か所なら4000年もかかる計算となる。

結論

目的地の個数が十数個の場合は何も考えずに全通り試しても問題ないものの、目的地の個数がそれ以上になると何らかの工夫を行わない限り計算が終わらない事が分かった。

ソースコード

今回使ったソースコードの全文を添付します。

TSP.h

#ifndef TSR_H_
#define TSR_H_
#include <cmath>
#include <algorithm>
#include <chrono>

struct PointF {
  float x;
  float y;
  constexpr float DistanceTo(const PointF& pt) {
    float dx = pt.x - x;
    float dy = pt.y - y;
    return std::sqrt(dx * dx + dy * dy);
  }
};

void TSP(PointF* points, const int num_points, int* result,
         long long* elapsed = nullptr) {
  int order[num_points];
  float min_distance = INFINITY;
  for (int i = 0; i < num_points; ++i) {
    order[i] = i;
  }

  auto time_start = std::chrono::system_clock::now();

  do {
    float distance = points[order[0]].DistanceTo({0.0f, 0.0f});
    for (int i = 1; i < num_points; i++) {
      distance += points[order[i]].DistanceTo(points[order[i - 1]]);
    }
    distance += points[order[num_points - 1]].DistanceTo({0.0f, 0.0f});

    if (distance < min_distance) {
      std::copy(order, order + num_points, result);
      min_distance = distance;
    }
  } while (std::next_permutation(order, order + num_points));

  auto time_stop = std::chrono::system_clock::now();

  if (elapsed) {
    *elapsed = std::chrono::duration_cast<std::chrono::microseconds>(time_stop -
                                                                     time_start)
                   .count();
  }
}

#endif  // !TSR_H_

source.cpp

#include <iostream>
#include <fstream>
#include <string>
#include <cstdlib>

#include "TSP.h"

const int MAX_POINTS = 13;

void Visualize(PointF* points, const int num_points, int* order) {
  std::string filename = "result" + std::to_string(num_points) + ".svg";
  std::ofstream ofs(filename);
  ofs << "<svg version=\"1.1\"";
  //ofs << " width=\"200\" height=\"200\"";
  ofs << " viewBox=\"-100 -100 200 200\"";
  ofs << " xmlns=\"http://www.w3.org/2000/svg\">\n";
  ofs << "<rect x=\"-100\" y=\"-100\" width=\"200\" height=\"200\" stroke=\"black\" fill=\"transparent\" stroke-width=\"1\"/>\n";
  for (int i = 0; i < num_points + 1; ++i) {
    int x1 = static_cast<int>(i == 0 ? 0 : points[order[i - 1]].x * 100.0f);
    int y1 = static_cast<int>(i == 0 ? 0 : points[order[i - 1]].y * 100.0f);
    int x2 = static_cast<int>(i == num_points ? 0 : points[order[i]].x * 100.0f);
    int y2 = static_cast<int>(i == num_points ? 0 : points[order[i]].y * 100.0f);
    ofs << "<line";
    ofs << " x1 =\"" + std::to_string(x1) + "\"";
    ofs << " y1 =\"" + std::to_string(y1) + "\"";
    ofs << " x2 =\"" + std::to_string(x2) + "\"";
    ofs << " y2 =\"" + std::to_string(y2) + "\"";
    ofs << " stroke=\"blue\" stroke-width=\"2\"/>\n";
  }
  ofs << "<circle";
  ofs << " cx =\"0\"";
  ofs << " cy =\"0\"";
  ofs << " r=\"3\" stroke=\"transparent\" fill=\"black\"/>\n";
  for (int i = 0; i < num_points; ++i) {
    int x = static_cast<int>(points[i].x * 100.0f);
    int y = static_cast<int>(points[i].y * 100.0f);
    ofs << "<circle";
    ofs << " cx =\"" + std::to_string(x) + "\"";
    ofs << " cy =\"" + std::to_string(y) + "\"";
    ofs << " r=\"3\" stroke=\"transparent\" fill=\"red\"/>\n";
  }
  ofs << "</svg>";
}

int main(void) {
  std::srand(3);
  PointF points[MAX_POINTS];

  float scale = 1.0f / static_cast<float>(RAND_MAX >> 1);
  for (int i = 0; i < MAX_POINTS; ++i) {
    points[i].x = static_cast<float>(std::rand()) * scale - 1.0f;
    points[i].y = static_cast<float>(std::rand()) * scale - 1.0f;
  }

  int result[MAX_POINTS];
  for (int i = 1; i < MAX_POINTS + 1; i++) {
    long long elapsed;
    TSP(points, i, result, &elapsed);
    Visualize(points, i, result);
    long long microseconds = elapsed % 1000LL;
    long long miliseconds = (elapsed / 1000LL) % 1000;
    long long seconds = (elapsed / 1000000LL);
    std::cout << i << "\t";
    if (seconds > 0) std::cout << seconds << "s";
    if (seconds > 0 || miliseconds > 0) std::cout << miliseconds << "ms";
    std::cout << microseconds << "us" << std::endl;
  }
}

出力された最短経路図(一部)

4か所の場合

8か所の場合

12か所の場合