組み合わせ最適化についてのオススメ参考書

質問

工学系の学生です。
現在、組み合わせ最適化に関する参考書を探しています。
一応amazonで調べてみましたが、ここでの意見も参考にしたいと思います。

あまり深く解説されていなくても良いので、
・多くのアルゴリズムが紹介されてる
・図やグラフが載っていて理解しやすい
ようなオススメの参考書を教えてください。

よろしくお願いします。

回答No.1

ur2c · ベストアンサー

組み合わせ最適化法は種類が多いので、網羅的に勉強したのでは能率が悪くてどうにもなりません。先に問題あるいは問題の族を決めて、それに合わせて方法を絞らないと。この点については no free lunch 定理
http://ja.wikipedia.org/wiki/%E3%83%8E%E3%83%BC%E3%83%95%E3%83%AA%E3%83%BC%E3%83%A9%E3%83%B3%E3%83%81%E5%AE%9A%E7%90%86
が参考になります。

一般論を勉強するのが目的なら、
離散凸計画
http://www.orsj.or.jp/~wiki/wiki/index.php/%E9%9B%A2%E6%95%A3%E5%87%B8%E8%A7%A3%E6%9E%90
半正定値計画
http://www.orsj.or.jp/~wiki/wiki/index.php/%E5%8D%8A%E6%AD%A3%E5%AE%9A%E5%80%A4%E8%A8%88%E7%94%BB
分枝限定法
http://www.orsj.or.jp/~wiki/wiki/index.php/%E5%88%86%E6%9E%9D%E9%99%90%E5%AE%9A%E6%B3%95
など。

実用なら、特殊な構造を持った問題を高速に解きたいのか、それとも遅くて良いからどんな問題でも扱えるのがいいのか。工学系だと「遅くていいから、どんな問題でも簡単に扱える」のが望ましいことが多いです。そうすると metaheuristics
http://ja.wikipedia.org/wiki/%E3%83%A1%E3%82%BF%E3%83%92%E3%83%A5%E3%83%BC%E3%83%AA%E3%82%B9%E3%83%86%E3%82%A3%E3%82%AF%E3%82%B9
になります。Metaheuristics には種類が既にいっぱいあって、今も新しい方法が次々と発明されてます。だから、どれがどんな意味で良いのか、なかなか判断がつきません。専門家と称する人たちだって、あんまりいろんな問題や方法について実戦経験があるようには見えません。

Metaheuristics はほとんどが自然現象の analogy なので、自分に理解しやすいものを使い込むのが、技を磨くという意味では良いと思っています。つまり

> あまり深く解説されていなくても良いので、多くのアルゴリズムが紹介されてる

という本は、読むだけ時間の損だという意見です。この絵
http://en.wikipedia.org/wiki/File:Metaheuristics_classification.svg
くらいを眺めておけばいいんじゃないでしょうか？

お礼

URL、参考になりました。
ありがとうございます。