CodeIQ 最短経路を探そう
Mathematica C++
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
README.md
example1.png
example2.png
tsp.cc
tsp.m

README.md

CodeIQ 最短経路を探そう

例題

表のような6点が与えられたとします。

x座標 y座標
1 4 5
2 7 2
3 9 1
4 9 4
5 7 3
6 6 8

このような点を、次のように記述して出題することにします。

{{4, 5}, {7, 2}, {9, 1}, {9, 4}, {7, 3}, {6, 8}}

与えられた点を結ぶ、下図のような巡回路{1,2,3,4,5,6,1}を考えます。

巡回路1

この巡回路の経路長は次のように計算でき、約20.4193となります。

1と2の距離 + 2と3の距離 + 3と4の距離 + 4と5の距離 + 5と6の距離 + 6と1の距離
= √((7-4)^2 + (2-5)^2) + √((9-7)^2 + (1-2)^2)
+ √((9-9)^2 + (4-1)^2) + √((7-9)^2 + (3-4)^2)
+ √((6-7)^2 + (8-3)^2) + √((4-6)^2 + (5-8)^2)
= 3 + 3√2 + 2√5 + √13 + √26
≒ 20.4193

同様の計算で、{1,5,2,3,4,6,1}という巡回路(下図)の経路長が9 + √5 + 2√13 ≒ 18.4472になることがわかります。 先ほどのは約20.4193だったので、これはそれよりも短い巡回路です。 実は、与えられた点の配置では、この巡回路が最短です(その理由はここでは説明しませんが、たとえば、すべての巡回路の経路長を計算することで確認できます)。

巡回路2

経路長が最短になる巡回路は、{1,5,2,3,4,6,1}のほかにも{1,6,4,3,2,5,1}{2,3,4,6,1,5,2}などがあります(始点が6通り、回る向きが2通りだから、全部で12通り)。

経路長が最短になる巡回路が複数あるときは、下記の条件を満たすものを採用することにします。

  1. 始点が1
  2. 2番目の点の番号よりも終点の一つ前の点の番号が大きい

つまり、上記の例では、{1,5,2,3,4,6,1}が求める巡回路です。

これらの条件を満たす巡回路が複数ある場合は、そこから一つ自由に選択してください。

最短巡回路とその経路長をあわせて、{{1,5,2,3,4,6,1},18.4472}のように書くことにしましょう。

問題

上記の例題と同様にして、以下の問の最短の巡回路とその経路長を求めてください。

問1

{{6, 2}, {4, 6}, {3, 4}, {6, 7}}

問2

{{9007199254742147, 18014398509481729},
 {12756043757992973, 9682416912451847},
 {7757599369284503, 13555003989651347},
 {6644379103590211, 16459957280325781},
 {7107267045169859, 11361149298161843},
 {17193260969299, 17215263416918057},
 {374711875842439, 13679925148827797},
 {9007199254742149, 18014398509481727}}

問3

{{24450478250354407, 24162405956350007},
 {5022777106905113, 9351872806120363},
 {22646143480201399, 18046391278629037},
 {26904592918639433, 8822422244422001},
 {13510798882112671, 27021597764225159},
 {7416604674633347, 17884308649058737},
 {11322174193520947, 3885286011386431},
 {25871043906094921, 9505143934995377},
 {12509125559334347, 10427194051934741},
 {13510798882112669, 27021597764225161}}

問4

{{143440002785145229, 125304038892333277},
 {264428432131034503, 120015772829769617},
 {128790875003948837, 270669230395068511},
 {159528435868345829, 204968426098505873},
 {19849988012900029, 184555790037852601},
 {275289191011264097, 71741794408943803},
 {10351044942542977, 120950333572309643},
 {256393278357970813, 144044348649819451},
 {144115188075856001, 288230376151712791},
 {144115188075856003, 288230376151712789},
 {219455401629103741, 10320154786742321},
 {227161482167126027, 70606670735479337}}

解の記述形式は{最短巡回路,最短経路長}とします。たとえば、上述の例題の解は{{1,5,2,3,4,6,1},18.4472}でした。

最短巡回路は以下の条件に合う形で記述してください。

  1. 始点が1
  2. 2番目の点の番号よりも終点の一つ前の点の番号が大きい

経路長は近似値でかまいません。ただし、最短巡回路の代わりに準最短巡回路を解答しないように注意してください。