パスワードを忘れた? アカウント作成
この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。

ミツバチはコンピュータよりも速く巡回セールスマン問題を解ける」記事へのコメント

  • 「コンピュータでは解くのに何日もかかる」って、一体何都市のTSP問題なんだ。 数1000都市くらいなら1日で解けるらしいし。 ミツバチが廻る花が何10箇所くらいなら、コンピュータでだって,あっという間に解けると思うがなぁ。
    • by Anonymous Coward

      単純な巡回サラリーマン問題ではないとか?
      3次元的な花の配置であったり、ハチが運べる蜜の量だったり、花の蜜が溜まるまでの時間であったり…

      • Re:をいをい (スコア:2, 興味深い)

        by saitoh (10803) on 2010年10月27日 10時59分 (#1848148)
        対象が三次元だと普通の巡回セールスマン問題より難しくなるとおもっておられる感じですが。

        普通の巡回セールスマン問題は、都市間移動の「重み」の付け方に制約はありません。さすがにゼロとか負の重みはな無かったと思いますが。 「3次元的な花の配置」での距離だと「三角不等式を満たす重み」ということで、制約のある(やや易しい)巡回セールスマン問題になります。どっちにしても厳密解をもとめるのはNP困難です。ただ三角不等式を満たす巡回セールスマン問題は多項式時間近似アルゴリズムが多くあるそうです。

        運べる蜜の量の制約条件を足すと、難しくなりますね。

        親コメント

海軍に入るくらいなら海賊になった方がいい -- Steven Paul Jobs

処理中...