驚きの数学 巡回セールスマン問題　ウィリアム・J・クック　青土社　★★★☆☆

巡回セールスマン問題といえば、P vs NP問題（もしくはP≠NP予想）の文脈で語られることがほとんどだろう（P vs NP問題についての解説はコチラ）。しかし本書は、巡回セールスマン問題そのものの数理について扱っている点が新しい。
確かに、巡回セールスマン問題は解くのが難しい。しかし、特定の問題に対しては、都市の数 N がそれほど大きくなければ最適解を得ることができるし、N が大きくても、最適解に近い解を得ることはできる。本書では、そのためのテクニック─線形計画法や切除平面法─について解説してある。なるほど、巡回セールスマン問題を線形計画法の問題に落とし込むというアイディアは面白く、なにかに応用できそうだ。

一般論としては、巡回セールスマン問題についてわかっていることはあまりない。
知られている最良のアルゴリズムの計算時間は N²・2^N（ヘルド=カープの方法）で、驚くべきことに、この記録は1962年以降破られていない。
また、現在のところ、（メトリックな巡回セールスマン問題に対する）多項式時間のアルゴリズムで得られる解は、（最悪のケースでも）最適解の1.5倍を超えない（クリストフィードのアルゴリズム）ということしかわかっていない（脚注）。この結果は1976年に得られたものだ。
一方、P≠NPであるとすると、多項式時間のアルゴリズムで得られる解は最適解の1.0045倍以内にはなれないことが証明されている。つまり、（P≠NPの場合）真の値は1.0045と1.5の間のどこかにある、ということしかわかっていない。

最適巡回路を用いたアートや、ヒトや他の動物が最適解にどれほど近い解を直感で得られるかという心理学の話題も面白かった。オールカラーで、図がたくさん載っているのも楽しい。
しかし、本書はかなり専門書に近い割には説明が厳密でなく、わかりにくい。翻訳も直訳調で、読みにくいのが残念。（21/05/31読了 21/06/02更新）

注．2021年5月11日に、1.5倍をほんのわずかだけ更新する、1.5 - 10^-36倍のアルゴリズムが発表された（Karlin et al., 2021）。これだけやってこれしか更新されないとは驚きだが、これが呼び水となって、今後少しずつ改善されていくかもしれない。（21/06/06追記）