巡回セールスマン問題を2-Opt法で解いてみた

巡回セールスマン問題を2-Opt法によりc++で解いてみました。
2-Opt法は図1のように巡回経路中のクロスしている部分を繋ぎ変えて、経路を短縮する方法です。
残念ながら参考にしたサイトはすでに消えてしまっていて、リンクを貼ることはできませんでした。

図1
![fig3a.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/222722/5485cbe1-8be3-1557-e32b-b0ae5fca52e2.png)

図2　初期経路（n=100、L=5446.6）
![_or-opt_240603_003.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/222722/cc13b633-7d75-e85a-dfff-5e962edfdbf3.jpeg)

図3　最終経路（n=100、L=868.5）
![_2-opt_240603_002.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/222722/d35001c1-3928-bec0-90fc-bf6c3d298cd8.jpeg)

```c++:Console2opt.cpp
// 2-Opt

#include <iostream>
using namespace std;

#define NUM_TOWN 20    // 町の数
#define AREA_SCALE 100.0    // 町が存在するエリアの大きさ（正方形の一辺の長さ）

double town_map[NUM_TOWN][2];    // 町のx, y座標
int route[NUM_TOWN];    // 巡回経路

// ルートの中の二つの町の行く順番を交換
void swap(int* route1, int i, int j)
{
	int tmp = route1[i];
	route1[i] = route1[j];
	route1[j] = tmp;
}

// 町の座標をランダムに生成
void create_random_map()
{
	for (int i = 0; i < NUM_TOWN; i++)
		for (int j = 0; j < 2; j++)
			town_map[i][j] = AREA_SCALE * (double)rand() / ((double)RAND_MAX + 1);
}

// 都市間の距離を計算
double calc_dist(int i, int j)
{
	double dx = town_map[i][0] - town_map[j][0];
	double dy = town_map[i][1] - town_map[j][1];
	double dist = sqrt(dx * dx + dy * dy);
	return dist;
}

// 指定された巡回経路の長さを計算
double calc_length(int route1[])
{
	double sum_dist = 0.0;
	for (int i = 0; i < NUM_TOWN; i++)
		sum_dist += calc_dist(route1[i], route1[(i + 1) % NUM_TOWN]);
	return sum_dist;
}

// 巡回経路の初期化
void init_route()
{
	for (int i = 0; i < NUM_TOWN; i++)
		route[i] = i;
}

// 巡回経路と総距離の出力
void print_route()
{
	for (int i = 0; i < NUM_TOWN; i++)
		cout << route[i] + 1 << " ";
//		cout << route[i] << " ";
	cout << endl;

	double length = calc_length(route);
	cout << "Total Distance: " << length << endl;
}

// 町の座標を出力
void print_town_map()
{
	for (int i = 0; i < NUM_TOWN; i++) {
		cout << route[i] + 1 << " ";
		cout << town_map[route[i]][0] << " " << town_map[route[i]][1] << endl;
	}
}

// 2点間の距離を計算するマクロ
#define DIST(n,m)  calc_dist(route[(n) % NUM_TOWN], route[(m) % NUM_TOWN])

// 経路を繋ぎ変えたとき距離が短縮されるかどうかを計算し、短縮される場合は
// 経路を繋ぎ変えてtrueを返す
bool two_opt(int i, int j)
{
	bool fImproved = false;
	double diff = DIST(i, i + 1) + DIST(j, j + 1) - (DIST(i, j) + DIST(i + 1, j + 1));
	if (diff > 0) {
		for (int k = 0; k < (j - i) / 2; k++)
			// 部分経路を逆順に並び替える
			swap(route, (i + 1 + k) % NUM_TOWN, (j - k) % NUM_TOWN);
		fImproved = true;   // 改善した
	}
	return fImproved;
}

// 経路を短縮できる部分がなくなるまで、経路の繋ぎ変えを繰り返す
void calc_2_opt()
{
	bool fImproved = true;
	while (fImproved == true) {
		fImproved = false;
		for (int i = 0; i < NUM_TOWN; i++) {
			for (int j = i + 2; j < i + NUM_TOWN - 1; j++) {
				if (two_opt(i, j) == true) {
					fImproved = true;
				}
			}
		}
	}
}

int main()
{
	unsigned int seed = (unsigned)time(NULL);
	cout << "Seed = " << seed << endl;
	srand(seed);

	create_random_map();
	init_route();

	cout << "Number of town: " << NUM_TOWN << endl;

	cout << endl << "Town map" << endl;
	print_town_map();

	cout << endl << "First root" << endl;
	print_route();

	calc_2_opt();

	cout << endl << "Last root" << endl;
	print_route();

	return 0;
}
```

```title:実行結果
Seed = 1720711285
Number of town: 20

Town map
1 90.4907 4.93774
2 78.8177 93.9514
3 22.9614 8.54797
4 96.3806 61.734
5 41.1896 40.097
6 90.1001 74.2859
7 46.0358 27.1393
8 36.911 71.933
9 53.1006 63.1653
10 85.5164 71.1365
11 75.354 72.1924
12 25.0244 70.993
13 66.1224 92.337
14 96.8109 30.2673
15 50.5432 93.9362
16 2.6062 55.5206
17 23.6298 97.8699
18 12.0453 91.0217
19 43.0481 9.70459
20 22.7325 51.0406

First root
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Total Distance: 1155.5

Last root
5 7 3 19 1 14 4 6 10 11 2 13 15 17 18 12 16 20 8 9
Total Distance: 431.153

```