2

ポイントのある地図があります:

複数のノードと、それぞれの横にある緑と赤の数字でマップします

各ポイントの横にある緑色の数字はそのポイントのIDであり、赤色の数字はそのポイントのボーナスです。ポイント#1で開始および終了し、少なくともx(この場合は15)ボーナスポイントを獲得する最速のサイクルを見つける必要があります。私は都市を数回使うことができます。ただし、ボーナスポイントは1回しか獲得できません。近似アルゴリズムを使用してこれを行う必要がありますが、どこから始めればよいのかよくわかりません。

出力は次のようになります。

(1,3,5,2,1) (11.813 length)

以前と同じマップで、予想される出力ルートがオレンジ色で強調表示されています

4

1 に答える 1

0

それはNPの問題ではありませんか?もしそうなら、すべての可能性をテストせずに最速のものを見つけることはできません。それはかなり時間がかかります。

問題は、トラベリングセールスマンのIMHOに似ています。これまでのところ、この問題の最もよく知られている解決策は、AntColonySolutionです。このソリューションは、常に可能な限り最良のソリューションを見つけることを保証するものではありませんが、許容可能な時間内に少なくともかなり良いソリューションを見つけることができます。

なんらかの方法でボーナスポイントを考慮に入れることで、問題に対処するためにAntColonySolutionを変更することも可能かもしれないと思います。おそらくあなたが聞きたいと思った答えではありませんが、私が現時点で提供しなければならない最高の答えです。

于 2013-01-20T01:11:07.633 に答える