algorithm - 由 2 名玩家遍历棋盘上随机网格的最佳解决方案

Question

考虑一个无限大的二维板。我们在棋盘上的 P1 和 P2 点有两名玩家。他们需要遍历棋盘上的一系列方框 G1, G2, G3 .... Gn。

一开始只有 G1 是已知的。 G2 到 Gn 的坐标只有在它前面的框已经遍历后才知道。玩家可以在单位时间内在棋盘上的 8 个可能方向之一上一次移动一个。我们需要找到使用两个玩家遍历所有所需框的最短时间。

显而易见的解决方案是一种贪婪的方法，即靠近需要遍历的盒子的玩家向它移动。然后我们为下一个 G 再次计算更近的玩家。我觉得这个问题存在更好的解决方案，我现在无法理解。是否存在更好的解决方案？

Answer 1

我认为由于棋盘是无限的，我们应该尝试在 n 步(对于每 n 步)内尽可能多地覆盖两个玩家的区域。这样我们就可以在 n 次移动中最大化我们可以到达的字段。

所以我的策略是:

下一个盒子旁边是谁？

让它成为 P1。

让 P1 走到箱子(最短路径)，然后和另一个玩家 P2 一起朝相反的方向走。通过这种方式，我们最大化了两个玩家之间的距离，从而最小化了他们在 n 步内可以到达的区域的重叠。通过这种方式，我们可以最大限度地覆盖两个玩家在下一个盒子的 n 步内可以到达的区域。