読書感想文コンピュータ編アルゴリズム・知識工学
書名驚きの数学
巡回セールスマン問題
著者ウィリアム・J・クック
訳者松浦俊輔
発行日2013年6月6日 第1刷
発売元青土社
サイズ四六判、336頁
定価3200円+税
ISBN978-4-7917-6710-6

人工知能に関連する話、本、あるいは大学の講義などの中にしばしば登場するのが「巡回セールスマン問題」である。 この問題を解くのがいかに困難かの説明がよくされている。

しかし、そういうところで、巡回する都市数(点数)が非常に少ないところで、今のコンピュータではお手上げという残念な説明がされていることがある。 都市数が1000程度で、質の良い巡回路を求めるのは不可能になるという説明が多いのだ。

確かに、そういう話をしている先生方が若かりし頃はその程度であったかも知れない。 しかし、最近のTSPは研究も進んでいるし、コンピュータの性能も上がって、10万都市以上、さらには100万都市以上の最短巡回路を求めるレベルになっている。

たとえばカナダのワーテルロー大学のThe Traveling Salesman Problem を見れば、巡回セールスマン問題の最先端はどんな状況かが外観できる。

この本は、「巡回セールスマン問題」の起源から、最近の研究動向まで紹介がある。 さらに、それらに対する注、参考文献がしっかりしているので、それをネットでたどれば、さらにさらに奥深い世界を知ることができる。

少なくとも、授業やネット上で巡回セールスマン問題を扱う場合には、この本くらいは絶対に読んでおいて欲しい。

巡回セールスマン問題は驚くほど奥の深いものだが、それ以上にこの本は驚くほど濃い本なのだ。 消化不良を起こすことは間違いないと思われる本だが、ぜひ読んでもらいたい。 この本を読んだ人が増えれば、巡回セールスマン問題の阿呆な説明が激減すると思う。

2014年10月31日


読書感想文コンピュータ編アルゴリズム・知識工学