最大限度地減少移動的最大距離

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之前結束，則左邊的某個人將不得不跳過他向右。

那還不錯