以最少的移动将 n 个对象分配到 n 个不同位置的算法

Question

有 n 个房间和 n 个物体。在该过程结束时，每个房间中应该只有 1 个对象。最初，每个房间可以有从 0 到 n 的随机数量的对象，但所有房间中所有对象的总和为 n。什么是移动这些物体的算法，使得每个房间只有 1 个物体，移动最少，假设将一个物体从一个房间移动到顺时针相邻的房间算作 1 次移动，并且不可能有其他移动。

例子:
n = 5
初始情况:
房间 1 = 5
房间 2: 0
房间 3: 0
房间 4: 0
房间 5: 0
解:1+2+3+4 = 10

Answer 1

我只是就如何解决这个问题给出一个想法。

首先让我们建立一个优先级队列。队列将根据最近的距离排序。

首先，您需要找到具有额外对象的节点，这意味着它具有不止 1 个对象。让我们称之为 filledRooms。

现在找到空房间，这意味着这些房间有 0 个对象。称它为 emptyRooms。

而其他房间(只有 1 个物体的房间)不受影响，这些房间不包括在计算中。

现在构建优先级队列，根据与房间的距离排序。就这样吧，

filledRooms -- emptyRooms -- 距离

你的例子很简单，举个例子吧

房间号 1->2->3->4->5
房间对象 2->0->0->3->0

因此，填充的房间是 1 和 4。1到2的距离是1，1到3的距离是2，4到5的距离是1，4到2的距离是2，4到3的距离是2让我们解决这个问题，

1 2 1
4 5 1
1 3 2
4 2 2
4 3 3

现在让我们填充房间，直到我们用完房间对象(意味着只剩下 1 个对象)。

所以将 1 个对象从 1 移动到 2。(我们已经用完 1)
将 1 个物体从 1 移动到 3(不能那样做，我们已经用完了房间 1)
将 1 个对象从 4 移动到 2
将 1 个对象从 4 移动到 3

把成本加起来。这是您的最佳答案。如果允许顺时针和逆时针两种运动，这也将起作用。