100の最適化問題
100の最適化問題の本を書いている途中だが，問題と解法をセットにしたweb appを作ろうかと思っている．
最近，いろいろなサイトで最適化のデモが体験できるようになってきているが，50点の巡回セールスマン問題とか地図の彩色問題とか，つまらないものがほとんどだ．
例えば，グラフ彩色問題（地図はその特殊なものでものすごく簡単だ）は，ランダムグラフでもそこそこ難しくて面白い．しかも，ランダムグラフ理論というのがあって，最適な色数の推定が「ほとんど確実に」できる．解法は，昔，メタヒューリスティクスの本で書いた種々のメタヒューリスティクスがある．
最大カット問題というのも良く比較に使われる．2000点くらいの問題を「自分で作った」別の解法と比べて，フェアな実験だと言っているビデオ（某有名大の教授のご講演）をみたが，多くの人は騙されてしまうのだろう．
巡回セールスマン問題にはCONCORDEがある．日本語の解説がこちらにある．
近似解なら１万点くらいはipadで解ける．
この記事が気に入ったらサポートをしてみませんか？