考虑一个无限的2D板。我们有两名球员在板上的P1点和P2点。他们需要遍历板G1、G2、G3上的一系列方框。。。。Gn.
在开始时，只有G1是已知的。只有在遍历了G2到Gn之前的框之后，才知道G2至Gn的坐标。玩家可以在单位时间内在棋盘上8个可能的方向中的一个方向上一次移动一个。我们需要找到使用两个玩家遍历所有必需框的最短时间。
显而易见的解决方案是贪婪的方法，即离需要穿越的盒子更近的玩家向它移动。然后我们再次计算下一个G的距离更近的球员。我觉得这个问题有更好的解决方案，我现在无法理解。是否存在更好的解决方案？
我认为，由于棋盘是无限的，我们应该尽可能多地覆盖两名玩家在n次移动中的区域（每n次）。通过这种方式，我们可以在n次移动中最大化我们可以到达的大量字段。
所以我的策略是：
下一个盒子旁边是谁？
设为P1。
让P1走到箱子（最短路径），然后和另一个玩家P2在直接相反的方向上走。通过这种方式，我们最大化了两个玩家之间的距离，从而最大限度地减少了他们在n步中可以到达的区域的重叠。通过这种方式，我们最大限度地覆盖了两名球员在下一个箱子的n步中可以到达的区域。
选择离下一个盒子最近的玩家是你能找到的最好的启发式方法。
解释：每当出现新目标时，只有两个选项：将球员1或球员2移动到目标处，代价是场地中的距离。我们也更喜欢球员相距很远的情况，而不是靠得很近。最极端的情况是两个球员都在同一个球场上，这就像只有一个球员一样好。既然比赛场地是无限的，相距遥远总是更好的。
如果这是正确的，那么你应该问问自己：我真的应该选择离球门更远的球员，并且最终会导致球员之间的距离比我带走另一名球员时更近吗？
当然不是。在一个无限的领域中，选择最接近的球员有助于两者，最大限度地减少当前成本，并改善下一个目标的情况（球员相距很远）。
由于问题是非确定性的，因此解决方案必须是启发式的。
每个回合的"价格"是指该回合的移动次数。这可以是PrN1或PrN2，分别表示玩家1或玩家2在N轮中的移动次数。
每个回合的"得分"可以被认为是动作后的某个安排（两名球员的位置）对其余回合来说是一个好安排的概率。
您可能希望使用一个同时考虑价格和分数的评估函数来做出决策。
问题是，唯一有用的得分函数是玩家之间距离的函数（距离越大，离下一个回合越近的机会就越大），这与最低价格完全同步。任何让球员尽可能远离的选择都必然是最便宜的选择。
如果这一切意味着最好的算法只是移动最接近的玩家，这是你的第一本能。
如果棋盘不是是无限的，你可以创建一个更好的得分函数，该函数考虑下一个框的概率，这会给那些让玩家处于棋盘边缘的安排带来更低的分数。