昨日読了。
辞書。
辞書なので、パッと読んで、知らないこと・後からよく調べたいことをメモ。
- Hamilton閉路。すべての頂点を１回ずつ通る閉路。Hamilton閉路の距離最小のものが、巡回セールスマン問題の最適解である。
- Steiner木。頂点の部分集合（ターミナル）をつなぐ最小距離の木を求める。ターミナル以外の頂点は使っても使わなくてもよい。NP困難。
- クリーク。頂点の部分集合で、完全グラフを構成するもの。最大クリーク問題と、最大安定集合問題（安定集合は頂点間の接続が全く無い）は同値。
- 全対全の最短路問題においては、Floyd-Warshallよりも、Dijkstraを全点で実施する方が速い。前処理を行うことで高速に求めるアルゴリズムがいくつかある。Highway Hierarchy、Dial法など。
- タブーサーチ。以前の近傍はしばらく利用しない。集中化（よい近傍のまわりを重点的に探索）と多様化（まだ調べていないあたりを探索）を組み込んだタブーサーチは、応用が広い。最大クリーク問題やグラフ彩色問題に適用できる。
