TSP×最近追加法

注記

この記事は2016年7月に更新されてます。過去の記事の内容にプラスしてきちんとしたものにしました。
過去の内容には誤りがありました。すみません。

最近追加法

別称で最近隣接法とか存在するけれど、自分は最近隣接法とは区別している。最近隣接法は経路を辿りつつ、現在のいる点から最も近い点を繋げるのを繰り返すのに対して、最近追加法は巡回路を更新するのを目的とした方法。はてなの検索だと "最近挿入法" などでたどり着いている人も多いね。

概要

N個の都市があり、各都市間の距離が求まっている。
そこから適当に選んだ1都市を中心に "部分巡回路" の更新を行う。
形成の部分は文章だと伝わりにくいので図を使って説明。

例えば図のような部分巡回路があった場合に

• 部分巡回路Tに含まれる任意の都市s に対して、distance(s, k) が最小となるk(Tの都市に含まれない)を選択
• 都市k, 都市s, sと元々繋がっていた都市t1, t2の4点で繋ぎ変えを行う(次図)

の手順をkが存在しなくなるまで繰り返します。

この手法で都市を追加していくことで、最後に導かれる巡回路の長さは最短路の2倍程度に収まります。

検証

MP-TESTDATA - The TSPLIB Symmetric Traveling Salesman Problem Instances
にあるデータを用いていくらか検証を行いました。

テストデータ	最適解	実行解 (Euclid)	実行時間 (ms)
st70.tsp (70都市)	675	846.325	52
pr144.tsp (144都市)	58537	74385.9	700
tsp225.tsp (225都市)	3916	5275.51	5267
lin318.tsp (318都市)	42029	56490.7	21149

検証環境

• language: C++11
• compiler: gcc version 4.9.3 (x86_64-apple-darwin14.5.0)
• compile_option: g++ -O0 -std=c++11
• machine: MacBook Pro (Retina, 13-inch、Early 2015)

まとめ

今回の実装方法だと改善の可能性は無いです。アルゴリズム自体の変更によって(2-optと組み合わせる)変化はしますが、パラメータや乱数などの調整が必要ないため、一度出した解がそのまま実解になります。都市の状態によっては偏った結果になってしまうため焼き鈍しやGAなどの方がいじり甲斐があると思います。ただ、算出結果を他アルゴリズムの初期都市としたり、分枝限定法などの下界算出に用いるのにはオーダーも低く見積もれるため向いているんではないでしょうか。

ソースコード

以下のリポジトリにTSP関連のアルゴリズムを少々使いやすいようまとめてあります。
TSPLIBの形式のみに対応したものなので抽象度は低いと思われます。

GitHub - Everysick/tsp_impl: Algorithms of traveling salesman problem.

double run(int p, vector<pair<double, int>> *near,  Graph *g)
{
	int n = g->dim;

	bool use[n];
	memset(use, false, sizeof(use));

	int nearest_node = near[p][0].second;

	vector<int> tsp;
	tsp.push_back(p);
	tsp.push_back(nearest_node);

	use[p] = use[nearest_node] = true;

	vector<pair<int, int>> joint(n);
	joint[p] = make_pair(nearest_node, nearest_node);
	joint[nearest_node] = make_pair(p, p);

	double ret = g->dist[p][nearest_node] * 2;
	while(tsp.size() != n){
		int best_from, best_to = -1;
		double best_cost = -1;

		for(int i=0; i<tsp.size(); i++){
			for(int j=0; j<near[tsp[i]].size(); j++){
				int to = near[tsp[i]][j].second;
				double cost = near[tsp[i]][j].first;

				if(use[to] == false){
					if(best_to < 0 || cost < best_cost){
						best_from = tsp[i];
						best_to = to;
						best_cost = cost;
					}
				}
			}
		}

		use[best_to] = true;
		tsp.push_back(best_to);

		int a = joint[best_from].first, b = joint[best_from].second;

		if (g->dist[best_from][a] > g->dist[best_from][b]) {
			ret -= g->dist[best_from][a];
			ret += best_cost;
			ret += g->dist[a][best_to];

			joint[best_to] = make_pair(a, best_from);
			joint[best_from].first = best_to;

			if (joint[a].first == best_from) {
				joint[a].first = best_to;
			} else {
				joint[a].second = best_to;
			}
		} else {
			ret -= g->dist[best_from][b];
			ret += best_cost;
			ret += g->dist[b][best_to];

			joint[best_to] = make_pair(b, best_from);
			joint[best_from].second = best_to;

			if (joint[b].first == best_from) {
				joint[b].first = best_to;
			} else {
				joint[b].second = best_to;
			}
		}
	}

	return ret;
}

double min_path_select_solve(Graph *g) {
	int n = g->dim;

	vector<pair<double, int>> near[n];

	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(i == j) continue;
			near[i].push_back(make_pair(g->dist[i][j], j));
		}
		sort(near[i].begin(), near[i].end());
	}

	pair<double, int> shortest = make_pair(run(0, near, g), 0);
	for(int i=1;i<n;i++){
		double res = run(i, near, g);

		if(res < shortest.first){
			shortest = make_pair(res, i);
		}
	}

	return shortest.first;
}