0

私が抱えている問題の解決策があるかどうかを見つけようとしています。私は X 人と Y のポジションを配置しています。ポジションよりも人数が多い場合もありますが、デフォルトのケースでは X==Y です。一人が移動しなければならない距離が最小になるように人を配置したい。したがって、人が 1 ～ 5 で位置が AE の場合:

1  2  3  4  5
   A  B  C  D  E

私がすでに持っていた些細な実装では、{A2, B3, C4, D5, E1} を割り当てていました。その結果、E は他の誰よりもはるかに遠くまで移動しました。 、つまり、他のすべての人はもう少し先に進みますが、最悪の場合ははるかに小さくなります。

私は現在、距離（昇順）でソートされた各位置を含む、各人の配列を作成しています。次に、最高の位置までの距離が最も長いプレーヤーが最初になるように、すべての人の配列を逆に並べ替えます。私は彼をポジションに割り当て、次にそのポジションを他の各プレイヤーのリストから削除し、逆の並べ替えを繰り返し、すべてのポジションが満たされるまで繰り返します。

これにより妥当な結果が得られますが、非常に非効率的です (各配列から要素を削除し、毎回再ソートする)。

明らかに、問題は人や位置までの距離に対処する必要はありませんが、各リソースが特定のフィットネスでタスクを実行できるようにリソースを割り当てることと言えます。すべてのツールが少し不適切なタスクを実行していることを意味する場合でも、それが理にかなっている場合。

ここでミラーリングしている古典的な最適化の問題があると思われますが、どれがどれかはわかりません。

4

1 に答える 1

1

全員を中央に移動します。つまり、一人一人のためです。もし彼らがi左から '番目の人なら、i' 番目のスロットに入ります。

最適性の証明:

誰かを飛び越えることは有利ではありません。なぜなら、それらの人々をより少ない量でシフトし、自分自身をより少ない量でシフトすることができ、使用される動きの量は同じだからです。
例: A _ B _ _ C _ _ 1 2 3
A は、境界に到達するために少なくとも 7 スロット移動する必要があります。
B は少なくとも 5 回移動する
必要があります ... C は少なくとも 2 回移動する必要があります ...
次に、1、2、3 回の移動が残っていることがわかります。 2+3手。また、右側にキャラクターがいる場合、それらのいずれかが左端のキャラクターを飛び越えた場合、左側のキャラクターはスロットの右側に移動するために追加の移動を行う必要があることを意味します。
したがって、ジャンプは同じかそれ以上の数の移動につながり、決して有利ではありません。

ジャンプしても何も得られないので、操作は移動または停止だけです。キャラクターiが の後にスロットに移動するiと、右側の誰かが左に飛び越えなければならなくなり、全員が整列できなくなります。同様に、キャラクターiが slot の前で終わった場合i、左側の誰かが右側に向かって彼を飛び越える必要があります。

それはそれほど悪くはありませんでした

于 2011-06-17T02:36:19.170 に答える