MathematicaのFindShortestTourのバグ
先日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}です。
何も気にせず使えるようになるにはまだ時間がかかりそうです。
白と黒のとびら
川添愛『白と黒のとびら: オートマトンと形式言語をめぐる冒険』（東京大学出版会, 2013）（参考文献リストあり・索引なし）
チョムスキー階層のすべてに対応するオートマトンを「扉を持った遺跡」に例えて組み込んだファンタジー。計算理論の基礎を学ぶのにはふつうの教科書の方がいいだろうが、ひと通り学んだ後なら楽しめるだろう。計算複雑性の理論など、進んだ話題を扱う続編に期待。
線形拘束オートマトン（ゼウ山の塔）への入力が、○と●という2つのボタンなのだが、塔はどうやって入力の終わりを認識しているのだろう。
ロボットは東大に入れるか
新井紀子『ロボットは東大に入れるか』（イースト・プレス, 2014）（参考文献リストなし・索引なし）
私、2010年に『コンピュータが仕事を奪う』という本を書いたんです。数学者として。でも、経済学者や教育学者、あるいはマスコミの人たちや政治家が、あまり深刻に受け止めてくれなかったんですね。すごくショックだった。近未来に必ず起こる危機なのに誰もまともに聞いてくれないなんて。これはまずいな、と思ったんです。
そこで考えたわけです。たとえば東大に入るロボットを作ると言って、それがある程度、たとえば東大に入らなくても大学に半分入るとか、それなりの大学に入るっていうことになったら、人は真面目に考えてくれるかもしれない。(p.219)
私はまともに聞いて、深刻に受け止め、そしてまずいな、と思っています。
細かいことをいくつか
アニメのCGを作るときに使われるソフトも、初音ミクに歌を歌わせるソフトも、みんな数学だけでできているのです。(p.43)
あるレベルで見ればそうですが、そのレベルで考えている人はあまりいないし・・・
将棋やチェスと違い、東大入試はルールを変えられます。たとえば東大入試が全部面接になると、このプロジェクトはチューリングテストへの合格を目指す人工知能の一般的なチャレンジと同じになります。その代表的なコンテストであるローブナー賞に合格したAIはまだありませんが、p.94の記述は、そういうAIがすでにあると誤解されるものになっています。
東大入試が変わらないとしても、1983年の日本史のように、「部外者がちゃんと採点できるのか」という問題があります。
入試問題とAIの関係については、ほかにもいろいろ考えさせられることがあります。いつかどこかでまとめましょう。
ロボットは恋人になり得るか、がより深刻です。
数学文章作法 基礎編
結城浩『数学文章作法 基礎編』（筑摩書房, 2013）（参考文献リストあり・索引あり）
『数学ガール』で独自のジャンルを打ち立てた著者による文書読本。①文章の書き方を学んだことのないすべての人向けの部分（1～3と7, 8章）と、②数式を含む文章を書く人向けの部分（4, 5章）、③教科書のようなものを書く人向けの部分（6章）からなる。
コンパクトにわかりやすく書かれているのがとてもよく、①の部分、特に最初の3章は、いわゆる理系ではない人にも勧められる。ただし、タイトルに「数学」が入っていることが、理系でない人に勧める際の大きな障害だ。最初の3章だけ読むことのコストパフォーマンスも・・・
文章読本はほかにもいろいろあるが、本書には、『数学ガール』の執筆において著者がしている工夫を垣間見るという、副読本的な楽しみ方ができるという特徴がある。例示Aすると、『数学ガール』で例示Bが少ないところは、著者にとって理解Bが難しいところの例示Cなのだと、理解Cするようになる、と理解Aした（「例示は理解の試金石」）。
細かいこと
- 形式が大切であることに異論はないが、欠けたカップで出されても、おいしいコーヒーはおいしいと思う（p.27, 181）。
- 「a, b, c, d, eは定数」などという文字の使い方がp.104で紹介されていて、こういうことまで教えるのはさすがだと思ったのだが、これはどのくらい一般的なものなのだろうか。（数学の特定の分野の話？）
参考文献でも挙げられている木下是雄『理科系の作文技術』（中央公論社, 1981）の、「式も文の一種とみてコンマやピリオドをつける（p.168）」というたてまえを、採用しないのはいいとして、紹介くらいはしてもよかったのではないだろうか。