javascript - 给定一台可以一次移动无限球的机器，以最少的移动次数将球从一组桶移动到另一组的算法

Question

我的一个 friend 提出了一个问题，你有 n 个桶(a、b、c、...、n)，每个桶都占你总球的一定百分比。然后，您会得到问题结束时每个桶应该有多少球的细目分类。您还获得了一台机器，它可以在一次移动中将无限个球从一个桶移动到另一个桶(例如 10 个球从桶 A 到桶 C)。您会使用什么算法来确保您始终拥有尽可能少的移动次数？

我被这个难住了。看起来它可以使用欧几里得算法的扩展来解决，但我完全不确定我将如何解决这个问题。我测试了尝试将 2 个最大/完美问题桶相互匹配的明显答案，但这不起作用。任何指示都会有所帮助。

Answer 1

在具有启发式函数的可能移动图上使用 A*:与目标桶不同的桶数除以二。即b/2其中 b是数量错误的桶数。

A* 通常被认为是游戏中类似路由单元的寻路算法，但它适用于任何图表，您可以找到一种永远不会高估到目标节点距离的启发式算法。最重要的是，配备这种启发式算法的 A* 总能找到最短路径。借用博弈论，我们可以想到一个图，节点由链接连接，其中每个节点是球在桶中的可能分布，每个链接代表机器可以做出的合法移动。您的起始节点是球的起始分布。你的目标节点是球的目标分布。

利用这张图，我们可以应用呼吸优先搜索，并等待我们碰巧访问目标节点。这将为我们提供从开始分布到目标分布的最短移动集，因为它是呼吸优先搜索。 (在这种情况下，这或多或少等同于 Dijkstra 算法，因为每一步的成本(长度)与 1 步相同)

但是，我们可以做得更好。 A* 使用启发式搜索图形。具体来说，它类似于呼吸优先搜索，除了接下来访问最接近起始节点的未访问节点，A* 接下来访问最小化 g(n) + h(n) 的未访问节点。其中 g(n)是未访问节点的长度，n , 到起始节点和 h(n)是与未访问节点的距离的启发式算法，n , 到目标。这意味着当我们首先检查通往目标的明显路径时，我们通过“远离”目标来花费更少的计算时间来寻找最佳路径。数学证明，如果您能找到可接受的启发式算法，A* 将为您提供从起始节点到目标节点的最佳路径，这意味着启发式算法永远不会高估到目标的距离。例如，在视频游戏中，两点之间的可步行路径的长度始终大于或等于飞翔距离。尽管我们的图不是表示物理空间的图，但我们仍然可以找到可接受的启发式。

一次移动最多只能使 2 个桶拥有正确数量的球，因为一次移动最多只能影响两个桶。因此，举例来说，如果我们数一下我们的桶，发现有 4 个桶里的球是错误的，那么我们就知道至少需要 2 次移动。很有可能更多，但不能少于 2。

让我们的启发式成为“球数错误的桶数除以 2”。

我们的启发式不会高估获得所需球数所需的移动次数，因为即使是您配对快乐配对的最佳移动方式也可能发生在您仅配合我们的启发式的每一步移动中。我们的启发式算法经常低估移动，但这没关系，计算只会花费更长的时间，但不会得到错误的结果，移动的结果计划仍然是尽可能短的。因此，我们的启发式是可以接受的，这意味着它永远不会高估移动次数。

因此，具有“球数错误的桶数除以 2”的启发式 A* 总能找到达到分布的最短步数。

也许可以找到更好的启发式，如果是这样，那么搜索会进行得更快。这只是我想到的第一个启发式方法。