0

我正在尝试查找是否有任何解决方案可以解决我遇到的问题。我有 X 个人和 Y 个职位来放置他们。有时人可能比职位多，但在默认情况下 X==Y。我想分配人员，使任何人必须移动的距离最小化。因此，如果我有 1-5 个人和 AE 职位：

1  2  3  4  5
   A  B  C  D  E

我已经有的简单实现是分配 {A2, B3, C4, D5, E1}，这导致 E 比其他任何人都走得更远，而我更喜欢匹配是 {A1, B2, C3, D4, E5} ，这意味着其他人都走得更远，但最坏的情况要小得多。

我目前正在为每个人创建一个数组，包含每个位置，按距离（升序）排序。然后我对所有人的数组进行反向排序，使得距离最佳位置最远的玩家排在第一位。我将他分配到一个位置，然后从其他玩家的列表中删除该位置，然后反向排序并重复，直到所有位置都被填满。

这给了我合理的结果，但似乎效率很低（从每个数组中删除元素并每次都使用）

显然这个问题不必处理人员和位置距离，而是可以说是分配资源，其中每个资源都可以执行具有一定适应性的任务，并且我想避免使用非常不适合的工具一个给定的任务，即使这意味着每个工具都在做一个稍微不合适的任务，如果这有意义的话。

我怀疑我在这里反映了一些经典的优化问题，但我不知道是哪一个。

4

1 回答 1

1

Move everyone to the middle. That is, for each person; if they are the i'th leftmost person then they go in the i'th slot.

Proof of optimality:

Jumping over someone isn't advantageous because you could just shift those people a lesser amount and yourself a lesser amount and the amount of moves used is the same.
ex: A _ B _ _ C _ _ 1 2 3
A must move at least 7 slots to get to the boundary, then position himself on a square.
B must move at least 5 ...
C must move at least 2 ...
Then we see we have 1,2,3 moves left to allocate, so jumping over each other still always resolves in 7+5+2+1+2+3 moves. And in the case where there are characters to the right, if any of those jump over leftmost characters then that means a left character has to make additional moves to be on the right side of the slots.
Therefore jumping leads to a equal or greater number of moves, it is never advantageous.

Now since jumping gains nothing the only operations are to move or stop. If character i moves to a slot after i, then someone to the right of him will have to jump over leftwards or they can't all be aligned. Likewise if character i ends up before slot i, someone to the left will have to jump over him towards the right.

That wasn't so bad

于 2011-06-17T02:36:19.170 回答