8数码问题求解时FIFO队列改LIFO后DFS运行异常原因问询

你遇到的问题本质是DFS（深度优先搜索）的特性和你代码的子节点入栈顺序共同导致的，并不是真的无限循环：

1. 栈是后进先出结构，你当前的moves定义里，0在初始位置（索引7）时，生成子节点的顺序依次是：交换0和索引4的元素、交换0和索引8的元素（这一步直接到目标）、交换0和索引6的元素。三个子节点会按这个顺序依次加入栈，栈顶最终是第三个子节点，DFS会优先探索这个节点的深层分支，不会立刻处理位于栈中层的目标节点。
2. 8数码的可达状态总数有18万左右，你没有给DFS设置深度限制，搜索会一路往最深的分支走，要等这条分支所有状态都探索完毕，才会回退到上层处理其他节点，整个过程耗时极长，肉眼看起来就像卡住了。

而BFS是先进先出的队列结构，会按顺序先处理第二个子节点，自然很快就能找到目标。

解决方法 #

• 临时调整可以把生成子节点的顺序反过来，让目标节点最后被加入栈，这样栈顶就是目标节点，立刻就能匹配到。
• 通用的解决方案是使用迭代加深DFS（IDDFS）：每次限制搜索的最大深度，从1开始逐步递增深度上限，直到找到目标，既保留了DFS空间占用小的优势，又能保证找到最短路径，还不会无限制往深层分支钻。

内容的提问来源于stack exchange，提问作者Dominos-roadster