「粘菌が組み合せ最適化問題を解く」記事へのコメント

プラトーの問題

[superfox (31908)]

確かマーティンガードナーの本で読んだと思うんだけど、
プラトーの問題 [osaka-kyoiku.ac.jp]の話を
知ったときは愕然としたな。

何しろちょっと点数を増やすだけでコンピュータにはお手上げなのに
石鹸膜が解いちゃうんだから。

Re:プラトーの問題

[s02222 (20350)]

>何しろちょっと点数を増やすだけでコンピュータにはお手上げなのに
>石鹸膜が解いちゃうんだから。

コンピュータで手に負えないのは、数学的にそれ以上良い解が無いと証明できる最適解を求めたい場合です。 その石鹸膜で求めた解は、それが最も良い解だという保証がないハズです。 点の数を増やすと、かなり良い線いってるけど完璧ではない状態、みたいなのも出てきます多分 (もっと極端なところでは、乱暴に扱ってシャボンが割れちゃった、みたいな事態も起こりえますし)。

粘菌にせよシャボン膜にせよ、複雑な仕組みを使ってるわけでもないのにすごく良い解がいとも簡単に求まる、というのがミソで、 逆にその求まり方をコンピュータで再現しようとするネタもあります。

Re:プラトーの問題

[superfox (31908)]

> その石鹸膜で求めた解は、それが最も良い解だという保証がない

そうです。でも、最適かどうかの判定は楽 [wikipedia.org]なので、その簡単な方法を何度か繰り返せば良いよ、という話だったような。

「参考になる」モデついてるけど

[superfox (31908)]

門外漢なので全く自信はないので参考にはしない方が良いです。
その法則に従っているからといって
組合わせが「最適」とは限らないかもだし。