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

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

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

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

      親コメント
      • Re:をいをい (スコア:3, おもしろおかしい)

        by flutist (16098) on 2010年10月26日 21時06分 (#1847924)

        働きバチはみんな女の子だから、サラリーマンじゃない!ってことで、このあたり

        > ハチが運べる蜜の量だったり、花の蜜が溜まるまでの時間であったり

        をちょっと詳しく知る必要が…

        親コメント
      • Re:をいをい (スコア:2, 興味深い)

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

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

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

        親コメント
      • 単純な巡回サラリーマン

        巣に住む嫁という名の女王蜂のために働く働き蜂ということですねわかります。
        まあ実際には働き蜂はOLらしいですけど。

        親コメント
      • by Anonymous Coward
        いや、セールスマンだから

ソースを見ろ -- ある4桁UID

処理中...