Go to Qiita Advent Calendar 2024 Top
LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@rustcat

巡回セールスマン問題を山登り法で解いてみた

Last updated at Posted at 2024-07-22

巡回セールスマン問題を山登り法によりc++で解いてみました。

図1は初期経路です。

図2は、評価関数としてExchange(ランダムに選んだ二つの都市の番号の入れ替え)を採用したものです。あまり効率はよくなく、多くのクロスポイントが残ってしまいました。

図3は評価関数として2-Optを採用したものです。最適化の効率はかなり上がりました。
2-Optなのでクロスポイントは全て解消されています。

図4は評価関数としてOr-Opt（連続したひとかたまりの部分経路を切り出して他の場所に挿入）を採用したものです。Exchangeに比べて経路長を短縮できましたが、時間はよりかかるようになりました。

評価関数には乱数を含んでいるため、同じ初期経路でも結果は毎回多少異なります。
図5に10回づつ実行した結果と平均を示します。
2-OptはExchangeに比べて38.8%ほど距離が短くなっており、Or-Optは41.3%ほど距離が短くなっているようです。
ただ、結果は初期経路によっても変わるので、あくまで参考程度ですが。

こちらは参考にさせていただいたサイトです。
https://gist.github.com/i09158knct/4239460

図1　初期経路（n=100、L=5446.6）
_or-opt_240603_003.jpg

図2　Exchangeの最終経路 (n=100、L=1469.0）
_hill_climb_exch_001.jpg

図3　2-Optの最終経路 (n=100、L=874.2）
_hill_climb_2-opt_001.jpg

図4　Or-Optの最終経路 (n=100、L=862.4）
_hill_climb_or-opt_001.jpg

図5　10回の試行および平均
Exchange
1469.04518719254
1412.41833898412
1279.00282416639
1520.65255130249
1449.75431039189
1464.9298454694
1360.0782327484
1549.68434886832
1475.43769882799
1469.04518719254
平均:1445.0

2-Opt
874.184045925844
875.385875632027
900.17119468706
882.827485785561
874.184045925844
912.672325545645
890.40674186968
874.184045925844
884.023584540145
876.118431494204
平均:884.4

Or-Opt
847.03619261262
844.664696175987
831.129567802635
864.669691437796
899.266208178344
821.012424426344
846.146583151931
858.213313885276
846.068662882723
823.514322247895
平均:848.2
ConsoleHillClimbExchange.cpp
// Hill Climb (Exchange)

#include <iostream>
using namespace std;

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

#define ITERATION 1000000 // 繰り返し回数

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

// ルートの中の二つの町の行く順番を交換
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;

	length = calc_length(route);
}

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

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

// 0より大きく1より小さな乱数の生成
double get_random()
{
	return ((double)rand() + 0.5) / ((double)RAND_MAX + 1.0);
}

// 巡回ルートのコピー
void copy_route(int route_dest[], int route_source[])
{
	for (int i = 0; i < NUM_TOWN; i++)
		route_dest[i] = route_source[i];
}

// 評価関数：Exchange（二つのポイントを交換）
double hill_climb_exchange(int route1[])
{
	int town1 = rand() % NUM_TOWN;
	int town2 = rand() % NUM_TOWN;
	swap(route1, town1, town2);
	double new_length = calc_length(route1);
	return new_length;
} 

void calc_hill_climb()
{
	int* route_new = new int[NUM_TOWN];

	for (int i = 0; i < ITERATION; i++) {
		copy_route(route_new, route);

		double length_new = hill_climb_exchange(route_new);

		if (length_new < length) {
			length = length_new;
			copy_route(route, route_new);
		}
	}

	delete []route_new;
}

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_hill_climb();

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

	return 0;
}
ConsoleHillClimb2Opt.cpp
// Hill Climb (2-Opt)

#include <iostream>
using namespace std;

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

#define ITERATION 1000000 // 繰り返し回数

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

// ルートの中の二つの町の行く順番を交換
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;

	length = calc_length(route);
}

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

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

// 0より大きく1より小さな乱数の生成
double get_random()
{
	return ((double)rand() + 0.5) / ((double)RAND_MAX + 1.0);
}

// 巡回ルートのコピー
void copy_route(int route_dest[], int route_source[])
{
	for (int i = 0; i < NUM_TOWN; i++)
		route_dest[i] = route_source[i];
}

// 評価関数：2-Opt
double hill_climb_2opt(int route1[])
{
	int i = rand() % NUM_TOWN;
	int j = rand() % (NUM_TOWN - 3) + i + 2;

	for (int k = 0; k < (j - i) / 2; k++)
		// 部分経路を逆順に並び替える
		swap(route1, (i + 1 + k) % NUM_TOWN, (j - k) % NUM_TOWN);

	double new_length = calc_length(route1);

	return new_length;
} 

void calc_hill_climb()
{
	int* route_new = new int[NUM_TOWN];

	for (int i = 0; i < ITERATION; i++) {
		copy_route(route_new, route);

		double length_new = hill_climb_2opt(route_new);

		if (length_new < length) {
			length = length_new;
			copy_route(route, route_new);
		}
	}

	delete []route_new;
}

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_hill_climb();

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

	return 0;
}
ConsoleHillClimbOrOpt.cpp
// Hill Climb (Or-Opt)

#include <iostream>
using namespace std;

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

#define ITERATION 1000000 // 繰り返し回数

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

// ルートの中の二つの町の行く順番を交換
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;

	length = calc_length(route);
}

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

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

// 0より大きく1より小さな乱数の生成
double get_random()
{
	return ((double)rand() + 0.5) / ((double)RAND_MAX + 1.0);
}

// 巡回ルートのコピー
void copy_route(int route_dest[], int route_source[])
{
	for (int i = 0; i < NUM_TOWN; i++)
		route_dest[i] = route_source[i];
}

// 評価関数：Or-Opt
// 巡回経路の中の連続した部分を一か所ランダムに選んで切り取り別の場所に挿入
double hill_climb_or_opt(int route1[])
{
	int* tmp = new int[NUM_TOWN];
	copy_route(tmp, route1);

	int entry_point = rand() % NUM_TOWN; // 切り取る位置
	int amount; // 切り取る大きさ
	int num_town = NUM_TOWN;
	do {
		amount = rand() % (num_town - 2) + 1;
	} while(get_random() > (1.0 / amount)); // 確率密度分布に従う乱数の生成

	// 切り取る位置から挿入する位置までの距離
	int distance = rand() % (NUM_TOWN - 1 - amount) + 1;

	// 切り取って空白ができる部分にデータを詰め込む
	for (int j = 0; j < distance; j++)
		route1[(entry_point + j) % NUM_TOWN]
			= tmp[(entry_point + amount + j) % NUM_TOWN];

	// 切り取ったデータ（連続した塊）の挿入
	for (int j = 0; j < amount; j++)
		route1[(entry_point + distance + j) % NUM_TOWN]
			= tmp[(entry_point + j) % NUM_TOWN];

	double new_length = calc_length(route1);

	delete []tmp;

	return new_length;
} 

void calc_hill_climb()
{
	int* route_new = new int[NUM_TOWN];

	for (int i = 0; i < ITERATION; i++) {
		copy_route(route_new, route);

		double length_new = hill_climb_or_opt(route_new);

		if (length_new < length) {
			length = length_new;
			copy_route(route, route_new);
		}
	}

	delete []route_new;
}

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_hill_climb();

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

	return 0;
}
実行結果 (2-Opt)
Seed = 1721463540
Number of town: 20

Town map
1 87.2833 22.2687
2 58.5541 45.0562
3 92.2058 2.60925
4 50.3784 16.5619
5 0.219727 20.5505
6 41.8854 92.1753
7 64.5721 29.0985
8 85.8276 28.3356
9 21.8658 50.7233
10 67.981 58.194
11 51.2024 62.4207
12 64.4257 82.2601
13 14.7766 36.4563
14 31.8481 60.0159
15 95.517 89.8895
16 71.4722 80.6274
17 97.4701 46.0083
18 57.2327 40.8813
19 24.4446 60.8063
20 68.8538 8.49915

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

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?