我在我的一本AI书中读过,用于模拟或游戏中寻路的流行算法(A-Star,Dijkstra)也用于解决众所周知的"15-puzzle".
任何人都可以给我一些关于如何将15-puzzle减少到节点和边缘图的指针,以便我可以应用其中一种算法？
如果我将图中的每个节点视为游戏状态,那么该树不会变得非常大吗？或者只是这样做的方式？
使用15拼图的A-Star的良好启发式是位于错误位置的正方形的数量.因为每个方格至少需要移动一次,所以不合适的方格数保证小于或等于解决谜题所需的移动次数,使其成为A-Star的合适启发式方法.
一个快速的谷歌搜索出现了一些文章,详细介绍了这一点:一个是关于并行组合搜索,另一个是关于外部存储器图搜索
关于算法问题的一般经验法则:有人可能在你之前做过,并发表了他们的发现.
京公网安备 11010802040832号 | 京ICP备19059560号-6 