はじめに
もう10月です。10月は旧暦で「神無月」と言いますが、由来は八百万の神が出雲大社に出かけているので神様がいなくなることからこのように言われています。ちなみに出雲地方では10月は「神在月」と言います。
本題
COVID-19の影響で外出が難しい日々が続いています。そういえば私は旅行が好きだという事を忘れていました(忘れる事では無い)
いつか世界遺産を全部巡りたいなーと思いながら今日に至るわけですが、試しに日本の世界遺産をすべて巡るにはどういうルートが良いか知りたくなりました。
先日、巡回セールスマン問題の新しいアルゴリズムが提案されていました。
有効性のほどはさておき、新しいアルゴリズムが出てくるのは何となくわくわくするものです。
というわけで巡回セールスマン問題を解くように世界遺産を巡る旅に出たいと思います。
巡回セールスマン問題とは
私が説明するよりも遥かに詳しいwikipediaさんを参照してください。
世界遺産の一覧と場所
世界遺産と言っても「姫路城」のような場所が特定できるものから、「明治日本の産業革命遺産」のように色んな場所に分散しているものがあります。
という事で下記のGoogle Places APIに世界遺産名称を入れて緯度経度を決めました。
| 世界遺産名称 | 緯度経度 | GoogleMapへのリンク |
|---|---|---|
| 法隆寺地域の仏教建造物 | 34.6140766,135.7356826 | GoogleMap |
| 姫路城 | 34.839449,134.6939047 | GoogleMap |
| 屋久島 | 30.3445936,130.5127142 | GoogleMap |
| 白神山地 | 40.4568626,140.1645095 | GoogleMap |
| 古都京都の文化財 | ||
| 白川郷・五箇山の合掌造り集落 | 36.2577967,136.9061975 | GoogleMap |
| 原爆ドーム | 34.395483,132.453592 | GoogleMap |
| 厳島神社 | 34.2959885,132.3198262 | GoogleMap |
| 古都奈良の文化財 | 34.6889918,135.8398589 | GoogleMap |
| 日光の社寺 | 36.75535,139.5973058 | GoogleMap |
| 琉球王国のグスク及び関連遺産群 | ||
| 紀伊山地の霊場と参詣道 | ||
| 知床 | 44.1996561,145.2396745 | GoogleMap |
| 石見銀山遺跡とその文化的景観 | 35.105142,132.438759 | GoogleMap |
| 小笠原諸島 | 26.9641919,142.1063337 | GoogleMap |
| 平泉 | 38.9866085,141.1137868 | GoogleMap |
| 富士山 | 35.3606255,138.7273634 | GoogleMap |
| 富岡製糸場と絹産業遺産群 | 36.255121,138.8874275 | GoogleMap |
| 明治日本の産業革命遺産 | 32.7640423,129.8629041 | GoogleMap |
| 国立西洋美術館本館 | 35.7158676,139.7761806 | GoogleMap |
| 「神宿る島」宗像・沖ノ島と関連遺産群 | ||
| 長崎と天草地方の潜伏キリシタン関連遺産 | 32.7433902,129.8706662 | GoogleMap |
| 百舌鳥・古市古墳群 | 34.5472489,135.4964928 | GoogleMap |
※古都京都の文化財、琉球王国のグスク及び関連遺産群、紀伊山地の霊場と参詣道、「神宿る島」宗像・沖ノ島と関連遺産群の4つはAPIは結果が返ってきませんでした。
※※小笠原諸島は海の上でした。
使い物になりませんでしたが一応ソースコードを。
<?php $heritage_list = [ "法隆寺地域の仏教建造物", "姫路城", "屋久島", "白神山地", "古都京都の文化財", "白川郷・五箇山の合掌造り集落", "原爆ドーム", "厳島神社", "古都奈良の文化財", "日光の社寺", "琉球王国のグスク及び関連遺産群", "紀伊山地の霊場と参詣道", "知床", "石見銀山遺跡とその文化的景観", "小笠原諸島", "平泉", "富士山", "富岡製糸場と絹産業遺産群", "明治日本の産業革命遺産", "国立西洋美術館本館", "「神宿る島」宗像・沖ノ島と関連遺産群", "長崎と天草地方の潜伏キリシタン関連遺産", "百舌鳥・古市古墳群", ]; $apikey = "Your API key"; foreach ($heritage_list as $heritage_name) { $url = "https://maps.googleapis.com/maps/api/place/findplacefromtext/json?input=" . $heritage_name . "&inputtype=textquery&fields=geometry&key=" . $apikey; $handler = curl_init(); curl_setopt($handler, CURLOPT_URL, $url); curl_setopt($handler, CURLOPT_HTTPGET, true); curl_setopt($handler, CURLOPT_RETURNTRANSFER, true); curl_setopt($handler, CURLOPT_HEADER, true); $response = curl_exec($handler); $header_size = curl_getinfo($handler, CURLINFO_HEADER_SIZE); $body = substr($response, $header_size); $location = json_decode($body,true)["candidates"][0]["geometry"]["location"]; echo $heritage_name . " " . $location["lat"] . " " . $location["lng"] . "\n"; }
というわけで以下のように場所を調整しました
| 世界遺産名称 | 緯度経度 | GoogleMapへのリンク |
|---|---|---|
| 法隆寺 | 34.6140766,135.7356826 | GoogleMap |
| 姫路城 | 34.839449,134.6939047 | GoogleMap |
| 屋久島世界遺産センター | 30.3087865,130.6316354 | GoogleMap |
| 白神山地ビジターセンター | 40.5787865,140.2986528 | GoogleMap |
| 元離宮二条城 | 35.0142299,135.748218 | GoogleMap |
| 白川郷観光協会 | 36.2619973,136.9068822 | GoogleMap |
| 原爆ドーム | 34.395483,132.453592 | GoogleMap |
| 厳島神社 | 34.2959885,132.3198262 | GoogleMap |
| 東大寺 | 34.6889851,135.8398158 | GoogleMap |
| 日光東照宮 | 36.7578036,139.5993576 | GoogleMap |
| 首里城 | 26.2183181,127.7153514 | GoogleMap |
| 熊野本宮大社 | 33.8405706,135.7734753 | GoogleMap |
| 知床自然センター | 44.0915368,145.0229217 | GoogleMap |
| 石見銀山 | 35.105142,132.438759 | GoogleMap |
| 小笠原世界遺産センター | 27.0939,142.1910567 | GoogleMap |
| 中尊寺金色堂 | 39.0013596,141.0998908 | GoogleMap |
| 富士山総合指導センター | 35.3365541,138.7338886 | GoogleMap |
| 富岡製糸場 | 36.255121,138.8874275 | GoogleMap |
| 旧集成館反射炉跡 | 31.6179619,130.5769884 | GoogleMap |
| 国立西洋美術館本館 | 35.7158676,139.7761806 | GoogleMap |
| 中津宮 | 33.8973186,130.4318567 | GoogleMap |
| 大浦天主堂 | 32.7341535,129.8701372 | GoogleMap |
| 百舌鳥古墳群 | 34.5472489,135.4964928 | GoogleMap |
※なお、開始地点は会社の住所とします。
コスト
時間なのか距離なのか、はたまた金額なのか何をコストとして解を求めるかですが、とりあえず単純な距離でいいかな。
どうやって距離を計算しようかなと色々考えたのですが、めんどくさいので直線距離とする事にします。計算にはヒュベニの距離計算式を用いました。
<?php function distance($lat1, $lng1, $lat2, $lng2) { // ラジアンに変換 $rad_lat1 = deg2rad($lat1); $rad_lng1 = deg2rad($lng1); $rad_lat2 = deg2rad($lat2); $rad_lng2 = deg2rad($lng2); // 平均緯度 $p = ($rad_lat1 + $rad_lat2) / 2.0; // 緯度差 $dp = $rad_lat1 - $rad_lat2; // 経度差 $dr = $rad_lng1 - $rad_lng2; // 子午線曲率半径 $m = 6334834 / sqrt((1 - 0.006674 * sin($p) * sin($p))^3); // 卯酉線曲率半径 $n = 6377397 / sqrt(1 - 0.006674 * sin($p) * sin($p)); // 距離計算 $d = sqrt(($m*$dp)*($m*$dp)+($n * cos($p) * $dr) * ($n * cos($p) * $dr)); return $d; }
データ
データは2次元配列で、
$data[0][1] = 1000; $data[0][2] = 1100; $data[0][3] = 1200; ～～～中略～～～ $data[1][2] = 1300; $data[1][3] = 1400; $data[1][4] = 1500; ～～～後略～～～
といった感じのデータで予め計算しておきjsonで保存しておきます。
A→BもB→Aも同じ距離としています。
では始めます。
最近傍法(Nearest Neighbor法)
現在の地点から一番近い場所を選んで行く方法です。いわゆる貪欲法と呼ばれるもので単純です。
<?php $heritage_data = json_decode(file_get_contents("heritage_data.json"), true); $distance_data = json_decode(file_get_contents("distance_data.json"), true); // 結果格納用配列 $result = []; // 最初の場所 $current_idx = 0; // 最初の地点は会社の住所 $current = array_pick($heritage_data, $current_idx); // 最初の地点を保存しておく $start = $current; // 最初の場所を結果に入れる array_push($result, $current); while (true) { // 全部終わったら終了 if (!$heritage_data) break; // 一番近い場所を探す $current_idx = search_nearest_spot($distance_data, $current_idx, $heritage_data); $current = array_pick($heritage_data, $current_idx); array_push($result, $current); } // 最初の地点を最後に入れる array_push($result, $start); // 一番近い場所を探す function search_nearest_spot($distance_data, $current_idx, $heritage_data) { $min_distance = INF; $min_idx = -1; foreach ($heritage_data as $idx => $data) { if ($current_idx > $idx) { $distance = $distance_data[$idx][$current_idx]; } else { $distance = $distance_data[$current_idx][$idx]; } if ($min_distance > $distance) { $min_distance = $distance; $min_idx = $idx; } } return $min_idx; } // 配列の任意のキーを取り出して削除する function array_pick(&$array, $idx) { $d = $array[$idx]; unset($array[$idx]); return $d; }
会社 国立西洋美術館本館 日光東照宮 富岡製糸場 富士山総合指導センター 白川郷観光協会 元離宮二条城 東大寺 法隆寺 百舌鳥古墳群 熊野本宮大社 姫路城 石見銀山 原爆ドーム 厳島神社 中津宮 大浦天主堂 旧集成館反射炉跡 屋久島世界遺産センター 首里城 小笠原世界遺産センター 中尊寺金色堂 白神山地ビジターセンター 知床自然センター 会社 総コスト: 5319296.9714737
ふむ。首里城から小笠原諸島、小笠原諸島から中尊寺、最後の知床から戻ってくるあたりが厳しいルートになりましたね。
Random Insertion法
未訪問の場所を一つ選んで現在の巡回ルートの中で一番距離の短い場所に挿入して巡回ルートを更新していく方法です。
未訪問の場所の選び方をRandomにするのがRandom Insertion法です。
function ri($distance_data, $heritage_data) {
$result = [];
$count = count($result);
// 最初の場所
$current_idx = 0;
// 最初の地点は会社の住所
$current = array_pick($heritage_data, $current_idx);
// 最初の地点を保存しておく
$start = $current;
// 最初の場所を結果に入れる
array_push($result, $current);
while (true) {
// 未訪問の都市が無くなったら終了
if (count($heritage_data) == 0) break;
// ランダムに一つ選択
$key = array_rand($heritage_data);
$insert_position = search_position($heritage_data[$key]["idx"], $result, $distance_data);
array_splice($result, $insert_position, 0, [$heritage_data[$key]]);
unset($heritage_data[$key]);
}
// 最初の地点を最後に入れる
array_push($result, $start);
return $result;
}
function search_position($spot, $result, $distance_data) {
// 現在の完成しているルートの数
$count = count($result);
// 完成しているルートの最後からの距離を最小としておく
$min_distance = get_distance($distance_data, $result[$count-1]["idx"], $spot);
$position = $count;
for ($i = 1; $i < $count; $i++) {
$new_dist = get_distance($distance_data, $result[$i-1]["idx"], $spot) + get_distance($distance_data, $result[$i]["idx"], $spot) - get_distance($distance_data, $result[$i-1]["idx"], $result[$i]["idx"]);
if ($new_dist < $min_distance) {
$min_distance = $new_dist;
$position = $i;
}
}
return $position;
}
function get_distance($distance_data, $i, $j) {
if ($i > $j) {
return $distance_data[$j][$i];
} else {
return $distance_data[$i][$j];
}
}
会社 国立西洋美術館本館 日光東照宮 中尊寺金色堂 知床自然センター 白神山地ビジターセンター 富岡製糸場 富士山総合指導センター 白川郷観光協会 元離宮二条城 東大寺 法隆寺 熊野本宮大社 百舌鳥古墳群 姫路城 石見銀山 原爆ドーム 厳島神社 中津宮 大浦天主堂 旧集成館反射炉跡 屋久島世界遺産センター 首里城 小笠原世界遺産センター 会社 総コスト: 5200741.949292
あんまり変わっていませんね。
2-opt法
ある巡回路に対して、適当な2つの辺を入れ替えた際のコストを計算し、そのコストが小さくなる場合は入れ替える。それを入れ替えが無くなるまで繰り返します。
辺を3つにする3-opt法、4つにする4-opt法などがあります。
2-opt法は最初に巡回路を決めておく必要があるので、前述の最近傍法で求めたものを初期の巡回路としています。
// 2-opt法
function opt2($result, $distance_data, $heritage_data) {
$count = count($result);
while (true) {
$t = 0;
for ($i = 0; $i < ($count-2); $i++) {
$ii = $i + 1;
for ($j = $i + 2; $j < ($count-1); $j++) {
if ($j == ($count - 1)) {
$jj = 0;
} else {
$jj = $j + 1;
}
if ($i != 0 || $j != 0) {
$dist1 = get_distance($distance_data, $result[$i]["idx"], $result[$ii]["idx"]);
$dist2 = get_distance($distance_data, $result[$j]["idx"], $result[$jj]["idx"]);
$dist3 = get_distance($distance_data, $result[$i]["idx"], $result[$j]["idx"]);
$dist4 = get_distance($distance_data, $result[$ii]["idx"], $result[$jj]["idx"]);
if (($dist1+$dist2) > ($dist3+$dist4)) {
$reversed_route = array_reverse(array_slice($result, $ii, $j - $i));
array_splice($result,$ii, $j - $i, $reversed_route);
$t = 1;
}
}
}
}
if ($t == 0) break;
}
return $result;
}
会社 国立西洋美術館本館 小笠原世界遺産センター 首里城 屋久島世界遺産センター 旧集成館反射炉跡 大浦天主堂 中津宮 厳島神社 原爆ドーム 石見銀山 姫路城 百舌鳥古墳群 熊野本宮大社 法隆寺 東大寺 元離宮二条城 白川郷観光協会 富士山総合指導センター 富岡製糸場 日光東照宮 白神山地ビジターセンター 知床自然センター 中尊寺金色堂 会社 総コスト: 5197746.2476218
交差も無くなりましたしなんとなく改善した気がします。小笠原諸島から首里城は遠いなー。そもそも小笠原諸島が遠いんですが。
他にも
貪欲法、動的計画法、遺伝的アルゴリズム、Simulated Annealingなどなどバリエーションは豊富でアルゴリズムの勉強にもよく用いられています。
最後に
世界遺産を巡るルートを巡回セールスマン問題としていくつかの方法で解いてみました。
数がそれほどでもないですし結構場所がばらけている事からこれといって結果に差はありませんでした。
夏休みのスタンプラリーなんかをこうやって解いてみると面白いかもしれません。
