在棋盘上，两个玩家遍历随机网格的最佳解决方案

Question

5

考虑一个无限的2D版面。我们有两个玩家，分别在板上的点P1和P2上。他们需要穿过一系列的盒子G1，G2，G3.... Gn。

开始时只知道G1的坐标。只有在走过它前面的箱子后，才能了解G2到Gn的位置。玩家们可以以单位时间沿着板的8个可能方向之一单独移动。我们需要找出使用这两个玩家穿越所有所需的箱子的最小时间。

显而易见的解决方案是贪婪方法，即更接近需要穿越的箱子的玩家向其移动。然后我们再为下一个G计算更接近的玩家。我感觉有一个更好的解决方案存在于此问题中，但我现在无法理解。是否存在更好的解决方案？

- Sohaib

如果G1的位置未知，那么贪心算法如何运作？此外，如果已经访问了某个位置，并且该位置正好是其中一个盒子的位置，这是否也会被计算在内？ - Pham Trung

当然，在开始时就知道G1。现在你需要再次访问。可以将其视为一款贪吃蛇游戏，玩家需要收集随机出现的食物。 - Sohaib

你没有明确说明，所以我要问一下。当 P1 到达 G1 时，P1 和 P2 都知道 G2 的位置了吗？ - Jim Mischel

1

更准确地说，在无限离散参数空间上，您无法定义一个均匀分布。 - Niklas B.

@lex82，我在问题中已经提到了，“玩家们一次只能移动一个”。 - Sohaib

显示剩余4条评论

3个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- MrSmith42 · Answer 1

我认为由于棋盘是无限的，我们应该尽可能地在n步内覆盖两个玩家所能到达的尽可能多的区域（对于每个n）。这样我们就可以最大化我们在n步内可以到达的领域。

因此，我的策略是：

谁靠近下一个方格？

让这个人成为P1。

让P1走向方格（最短路径），并与另一个玩家P2朝着完全相反的方向前进。这样我们就最大化了两个玩家之间的距离，从而最小化了它们在n步内可以到达的区域的重叠。这样我们就可以最大化两个玩家在下一个方格中可以到达的区域的覆盖范围。

- lex82 · Answer 2

选择最接近下一个方格的玩家是您能找到的最佳启发式。

解释：每当出现新目标时，只有两个选项：将玩家1或玩家2移动到目标位置，代价是距离字段。我们还更喜欢玩家相距较远的情况，而不是靠得很近。最极端的情况是两个玩家在同一领域中，这与只有一个玩家一样好。由于游戏场地是无限的，因此相距较远总是更好的选择。

如果这是正确的，那么您应该问自己：我真的应该选择距离目标更远的玩家，并最终处于玩家比我选择另一个玩家更接近的情况吗？

当然不是。在无限的场地上，选择最近的玩家有助于减少当前成本并改善下一个目标的情况（玩家相距较远）。

- Amit · Answer 3

由于问题是非确定性的，解决方案必须是启发式的。

每一轮的“价格”是在该轮中所采取的步数。这可以是PrN1或PrN2，分别表示玩家1或玩家2在第N轮中所采取的步数。

每一轮的“得分”可以被看作是某种排列（两个玩家的位置）在移动后成为对于接下来的回合有利的排列的概率。

你需要使用一个评估函数来考虑价格和得分来做出决策。

问题在于，唯一有用的评分函数是一种与玩家之间距离的函数（距离越大，接下来的回合就越接近），而这恰好与最低价格相吻合。任何使玩家尽可能远离彼此的选择都是最便宜的选择。

所有这些意味着最好的算法就是移动最近的玩家，这也是你最初的直觉。

如果棋盘不是无限的，你可以创建一个更好的评分函数，考虑到下一个格子的概率，这将给留下玩家在棋盘边缘的排列带来更低的分数。