先日CodeIQで、巡回セールスパースン問題を出題しました。
Mathematicaには、指定した点をすべて通る最短の巡回路を求める関数 FindShortestTour
があるので、これを使えば簡単なはずでしたが、実はそこにはトラップがあったかもしれません。
追記:問題は3つありますが、Mathematica 10.4.1, 11.2で未解決なのは3番目のみです。
問題1(10.0.2 for Windowsで解決)
Mathematica 10.0.1 for Windowsでは、{{6, 2}, {4, 6}, {3, 4}, {6, 7}}
という4点を通る最短巡回路を求められませんでした。
@yabuki (More info: http://t.co/HBUub0ForI) #wolframlang pic.twitter.com/mxTwMsc0Nk
— Tweet-a-Program (@wolframtap) 2014, 11月 20
問題2(10.0 for Linux ARM (32-bit) (August 4, 2014)で解決)
10.0 for Linux ARM (32-bit) (January 29, 2014)の FindShortestTour
は、仕様がマニュアルと違っていました。
pts = {{1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 1}, {2, 3}, {2, 5}, {3, 1}, {3, 2}, {3, 4}, {3, 5}, {4, 1}, {4, 3}, {4, 5}, {5, 1}, {5, 2}, {5, 3}, {5, 4}}; FindShortestTour[%]
マニュアルによれば、巡回路の最初と最後は同じ(この例では1)はずなのですが、ここで得られる結果は「{14 + 5 Sqrt[2], {1, 2, 7, 3, 4, 5, 8, 12, 11, 15, 19, 14, 18, 17, 16, 13, 9, 10, 6}}
」で、仕様とは違っていました。
問題3(10.4.1, 11.2, 11.3 for Windowsで未解決)
1分待っても結果が返ってこない場合があります(Core i7-4930K)。(Wolfram/Alphaでは計算できたこともある)
FindShortestTour[{{0, 0}, {1, 0}, {0, 1}, {1, 1}, {0, 536870913}}]
浮動小数点で近似値だけでも・・・と思っても、やはりダメな場合があります(カーネルが落ちます)。
FindShortestTour[{{1., 0}, {0, 1}, {6421482390570520, 4284269602932036}, {239817909316376, 7744567430237013}, {2528914430818969, 5966759469595075}}]
マニュアルでは見つけられませんでしたが、「Method -> "IntegerLinearProgramming"
」を付けておくとうまくいくと、サポートから教えてもらいましたが、計算はできても結果が正しくない場合があります。(この例でオプションを外すとカーネルが落ちます。)
cities = { {12581820340729273, 10017935966728831}, {12754218452664193, 14539145895971681}, {14822745302277607, 14565274414261943}, {11873373307008371, 9781014188323403}, {16116822349097741, 15873203518310113}, {12701673778654019, 11291535066125623}, {9392560345300883, 14963106019249771}, {11529795864075473, 17759422650313613}, {9007199254742147, 18014398509483463}, {9007199254742149, 18014398509483461}}; FindShortestTour[cities, Method -> "IntegerLinearProgramming"]
一部のバージョンでは、巡回路{1, 4, 7, 9, 10, 8, 5, 3, 2, 6, 1}
が得られますが、正解は{1, 4, 7, 10, 9, 8, 5, 3, 2, 6, 1}
です。
何も気にせず使えるようになるにはまだ時間がかかりそうです。