アカウント名:
パスワード:
単純な巡回サラリーマン問題ではないとか?3次元的な花の配置であったり、ハチが運べる蜜の量だったり、花の蜜が溜まるまでの時間であったり…
普通の巡回セールスマン問題は、都市間移動の「重み」の付け方に制約はありません。さすがにゼロとか負の重みはな無かったと思いますが。 「3次元的な花の配置」での距離だと「三角不等式を満たす重み」ということで、制約のある(やや易しい)巡回セールスマン問題になります。どっちにしても厳密解をもとめるのはNP困難です。ただ三角不等式を満たす巡回セールスマン問題は多項式時間近似アルゴリズムが多くあるそうです。
運べる蜜の量の制約条件を足すと、難しくなりますね。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
海軍に入るくらいなら海賊になった方がいい -- Steven Paul Jobs
をいをい (スコア:3, 興味深い)
Re: (スコア:0)
単純な巡回サラリーマン問題ではないとか?
3次元的な花の配置であったり、ハチが運べる蜜の量だったり、花の蜜が溜まるまでの時間であったり…
Re:をいをい (スコア:2, 興味深い)
普通の巡回セールスマン問題は、都市間移動の「重み」の付け方に制約はありません。さすがにゼロとか負の重みはな無かったと思いますが。 「3次元的な花の配置」での距離だと「三角不等式を満たす重み」ということで、制約のある(やや易しい)巡回セールスマン問題になります。どっちにしても厳密解をもとめるのはNP困難です。ただ三角不等式を満たす巡回セールスマン問題は多項式時間近似アルゴリズムが多くあるそうです。
運べる蜜の量の制約条件を足すと、難しくなりますね。