有一些游戏。有必要以最佳方式快速找到最短的移动序列，以实现从一种游戏状态到另一种游戏状态的转换。（或一定长度的各种序列）。将需要限制可能移动的可能性的功能。例如，如果有 4 种可能的移动（左、右、上、下），那么我们可以请求一条不使用左下移动的路径。存储整个内容的最佳方式是什么以及用于搜索的算法是什么？
【思考】我想的原理是这样的……每走一步，都建立一个图，边是走，节点是给定走之后的游戏状态（即可以同时分析现有游戏并生成各种“虚拟”组合来搜索它们）。显然，行进的方向是重量。但我不记得有任何标准算法会从搜索中排除某些权重......即 您是否需要遍历图表并对排除的动作施加不雅高的权重？（这也不排除他 100% 的参与）还是更好地纠正算法，使其根据列表忽略某些权重，而图形本身被认为是未加权的？
在算法的输入端，存在游戏的某些状态，即 对于每个节点，您需要存储某种散列（因为存储所有状态非常昂贵），以便输入数据可以立即与图的必要节点相关联。然后通过搜索最短路径（A * 在这种情况下可能是最佳路径？）可以找到最短路径，并通过深度搜索（？）以一定长度的深度限制。
这一切都通过A *解决了，很奇怪。A* 旨在沿着图中的顶点之间查找路线。
取游戏的开始状态（输入顶点）并遍历所有可能的转换（图边），遍历它们，获得新的状态（顶点）。检查顶点是否与先前已知的顶点相同，并将它们合并。对于每个顶点，写下它从起始顶点的成就的最低“价格”。递归重复，每次选择“成本”最低的顶点，直到其中一个顶点成为目标游戏状态。在构建图表的过程中，遵循您的规则并检查它们允许您从哪个状态（顶点）进入另一个状态。那些。换句话说，过渡边可以是单向的。
不。方向是单向连接（边）的存在。肋骨可以是一侧的，这是正常的。
您可以散列，这将加快在大图中搜索相同状态的速度。