我已经做了一个谜题，玩家滑动到目标 - 规则相当简单：
-
一次只能移动一个滑块
-
对象是将滑块移动到目标节点 - 您只需要填充目标节点，不一定将所有滑块块放入目标节点 .
-
如果滑块在冰上滑动，它将继续沿该方向移动，直到它停止或移动为止
-
如果滑块遇到固体（混凝土，另一个块），它会停止并可以再次移动（显然不会移动到混凝土中）
-
如果滑块滑到木头上，它会停在木头上并可以移动
-
如果滑块滑动到目标节点，则无法再移动它
-
块可以通过某些块移动，例如，箭头块在该方向上推动块
-
有一些开关块可以启用"doors"，可以移动到这些开关块以打开和关闭这些"doors"
-
有些按钮块的操作方式与开关类似，只是它们必须有一个块才能激活"doors"
-
当门关闭时，它们就像混凝土一样 . 当门打开时，它们就像冰一样 .
我认为这是规则所涵盖的 . 以下是一些截图：
在这里玩家必须移动块，以便他们必须互相击打以解决难题 .
其中的难题是近乎解决的状态 . 注意块是如何击中另一个块并停止的
这是另一个包含推块功能的谜题：
如果我们向右滑动右上方的块，会发生以下情况：
如您所见，当块碰到箭头块时，块已移动到左侧，并停在木块顶部 .
我想编写一个解决这些难题的AI解决方案 - 我认为这将是某种深度优先搜索，但我不知道从哪里开始 . 实现这一目标的任何指针都将是一件好事！
1 回答
您的问题是状态空间搜索问题的经典实例 . 可以根据特定实例的特征使用不同的算法 .
无论您的特定实例如何，您都需要定义四个组件：
初始状态，在您的问题中初始配置
一个函数，它返回从空间的任何状态可到达的所有可能状态，在您的问题中，可达状态是可以通过移动滑块获得的拼图的所有可能配置 . 当访问其可到达状态时，状态被扩展 .
目标测试，一个确定给定状态是否为目标状态的函数，在您的问题中，您将检查是否所有目标块都已填充，
一个成本函数，它提供从一个状态传递到另一个状态的成本，允许您的算法选择要执行的最佳操作 . 在您的情况下，我认为您可以为每个操作使用常量值1，并搜索要执行的最小操作数以达到其中一个目标状态 .
由于可以根据这四个组件定义问题，因此可以使用以下算法之一解决问题：
Breadth-first search（BFS）：我们首先测试初始状态是否为目标状态（显然不是非平凡问题），然后我们扩展初始状态，测试每个可达状态，如果不是，则扩展每个状态，等等等级...可以使用队列来实现 .
Depth-fisrt search（DFS）：从初始状态开始，测试目标，然后扩展邻居状态，测试目标，扩展状态，等等，直到状态空间的最深层 . 这可以用堆栈实现 .
要评估哪种算法最合适，我们可以考虑以下因素：
完整性：是否保证算法在存在时找到解决方案？
最优性：算法能找到最优解吗？
时间复杂度：需要多长时间？
空间复杂性：它需要多少内存？
如果我们考虑BFS策略，我们可以看到它是完整的，因为它系统地按层次探索状态空间，只有当状态的深度增加时成本函数没有减少时才是最优的（这是我们的情况，因为所有的行动有不变的成本） . 现在它出现了坏消息：假设每个节点的扩展最多可以提供http://latex.codecogs.com/png.download?b状态，并且第一个解决方案是深度
，那么您将需要存储和扩展最多
状态 .
在DFS的情况下，我们必须考虑当一个不同的选择可能导致某处附近的解决方案时，它可能会在路径中停留很长时间（可能是无限的） . 因此，当状态空间是无限的时，该算法既不完整也不优化 . 如果我们将
视为状态空间的最大深度，我们将得到最多
的空间复杂度，而时间复杂度仍为指数：
.
所以，我们能做些什么？我们可以混合使用这两种策略并使用Iterative Deepening depth first search . 在此搜索中，我们将迭代地运行DFS，限制从0开始到最大深度级别的最大深度 . 这种方法具有搜索策略的优点：
空间复杂度，其中
是第一个最优解的深度，时间
（我们不能做得更好），它是完整的（它会找到一个解决方案，因为它迭代地探索所有因为BFS是最优的，所以它是最优的（假设成本函数不随路径长度减小） .
参考：Artificial intelligence: a modern approach
注意：显然存在其他不明确的策略，但正如书中所述，IDDFS是不知情的搜索问题的理想选择，其中您没有关于搜索空间的其他信息 . 有关其他类型的搜索策略，例如知情搜索，请参阅本书，了解目标状态与当前状态的距离 .