最大限度地减少移动的最大距离

Question

我试图找到是否有任何解决方案，我有问题。 我有X个人和Y位置来放置他们。有时可能会有更多的人比位置，但在默认情况下X == Y。 我想分配人员，使任何一个人必须移动的距离最小化。 所以，如果我不得不让人1-5和立场AE：

1 2 3 4 5 
    A B C D E 

的简单的实现我已经被分配{A2，B3，C4，D5，E1}，导致在电子商务活动远远超出其他任何人，当我更喜欢比赛是{A1，B2，C3，D4，E5}，这意味着每个人都会进一步移动，但最坏的情况要小得多。

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

这给我合理的结果，但似乎非常低效的（除去各阵元和每次诉诸）

显然这个问题不必与人打交道和距离的位置，但也可说分配资源，其中每个资源都可以执行具有某种适应性的任务，并且我想避免使用严重不适合于给定任务的工具，即使这意味着每个工具都在执行稍微不合适的任务说得通。

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

Answer 1

将大家移到中间。就是说，对于每个人来说;如果他们是第i号最左边的人，那么他们将进入第i号插槽。

证明最优的：

跳跃，有人是不利的，因为你可以只转移那些人更少量的和自己一个较小的量和移动使用的是相同的金额。
例如：A _ B _ _ C _ _ 1 2 3
必须移动至少7个时隙才能到达边界，然后将自己置于正方形上。
B必须移动至少5 ...
C必须至少移动2 ...
然后我们看到我们有1,2,3个动作需要分配，所以跳过对方仍然总是以7+ 5 + 2 + 1 + 2 + 3移动。而在右边有字符的情况下，如果其中任何一个跳过最左边的字符，则意味着左边的字符必须在插槽的右侧进行额外的移动。
因此跳跃导致相等或更多的动作，这永远不会有利。

既然跳跃收益没有什么唯一的操作是移动或停止。如果角色i移动到i后的某个位置，则他右侧的某个人必须向左跳或不能全部对齐。同样，如果字符i在插槽i之前结束，则左边的某个人将不得不跳过他向右。

那还不错