algorithm - 为高峰时段游戏生成随机拼图板

Question

如果您不熟悉它，该游戏由一系列大小不一的汽车组成，水平或垂直设置在具有单个出口的 NxM 网格上。只要另一辆车没有挡住它，每辆车都可以按照它设定的方向前进/后退。你永远不能改变汽车的方向。有一辆专用车，通常是红色的。它设置在出口所在的同一行，游戏的目标是找到一系列动作（一个动作 - 将汽车向后或向前移动 N 步），这将使红色汽车驶出迷宫.

我一直在思考如何为这个问题生成实例，根据解决棋盘的最小数量生成难度级别。

对算法或策略有任何想法吗？

提前致谢！

Answer 1

考虑到汽车的位置，问题中给出的电路板最多具有4*4*4*5*5*3*5 = 24.000可能的配置。

对于当今的计算机而言，具有 24.000 个节点的图并不是很大。所以一种可能的方法是

• 构建所有位置的图（节点是位置，边是移动），
• 找到所有节点的获胜步数（例如使用Dijkstra）和
• 选择距离目标较远的节点。

Answer 2

一种可能的方法是反向创建它。

1. 生成一个随机棋盘，其中红色汽车处于获胜位置。
2. 构建所有可到达位置的图表。
3. 选择与每个获胜位置距离最大的位置。

可到达位置的数量并不大（可能总是低于 100k），因此（2）和（3）是可行的。

如何通过本地搜索创建更难的实例

上述方法可能不会产生硬实例，因为大多数随机实例不会引起汽车的复杂联锁行为。

您可以进行一些本地搜索，这需要

1. 一种从现有板生成其他板的方法
2. 评估/适应功能

(2) 很简单，可能使用最长解的长度，见上。虽然这是相当昂贵的。

(1) 需要一些思考。可能的修改是：

• 在某处添加汽车
• 移除一辆车（我认为这总是会让董事会更容易）

这两个足以到达所有可能的板。但是可以添加其他方式，因为移除会使板更容易。这里有一些想法：

• 垂直于行驶方向移动汽车
• 在同一车道内交换汽车(aaa..bb.) -> (bb..aaa.)

由于大的分支因素，爬山/最陡上升可能很糟糕。可以尝试对一组可能的相邻板进行二次抽样，即，根本不看，而只看几个随机的板。

Answer 3

我知道这很古老，但我最近不得不处理一个类似的问题，所以也许这会有所帮助。

1. 通过从终端状态（即反向）应用随机运算符来构造实例将无法正常工作。这是由于状态空间的对称性。平均而言，您最终会处于与最终状态太接近的状态。

2. 相反，更好的方法是生成初始状态（通过在网格上放置随机汽车），然后尝试使用一些有界启发式搜索算法（例如IDA*或branch and bound ）来解决它。如果一个实例在边界下无法解决，则丢弃它。

3. 尽量避免A*。如果你有你的定义你的意思是一个“硬”实例（我发现 16 步非常困难）你可以使用A*和一个修剪规则来防止节点x用g(x)+h(x)扩展>T（T是您的阈值（例如，16））。

4. 启发式函数- 由于您在解决它时不必是最优的，您可以使用任何简单的不可接受的启发式，例如目标障碍物的数量。或者，如果您需要更强的启发式函数，您可以通过为生成的谜题生成整个获胜状态集，然后使用从当前状态到任何最终状态的最小距离来实现曼哈顿距离函数。