Iterative Deepening Depth First Search求解8 puzzle时部分状态找不到目标态

现象复现 #

• 程序运行结果不稳定
  • 初始态1,2,5 / 0,3,4 / 6,7,8可正常找到目标解
  • 初始态1,2,5 / 6,3,4 / 0,7,8无法返回解

逐段代码bug定位 #

• 外层迭代循环逻辑错误
  原实现的循环条件for (int j = 0; j <= increasingDepth; j++)绑定了会动态自增的increasingDepth变量，循环执行逻辑完全不受预期控制：第一次循环时increasingDepth=0，循环结束后手动自增increasingDepth为1，下次循环j=1满足1<=1，但传入深度受限搜索函数的深度值已经和当前循环层级完全错位，循环本身也没有按照设计从0到最大深度逐次迭代的逻辑运行。
• 深度计数逻辑完全失效
  原实现使用函数内的局部变量nodeLevel全局累加来标记当前节点的层级，完全没有关联节点自身的实际搜索深度。栈结构同时存储不同层级的节点时，nodeLevel的累加值完全不能代表当前弹出节点的真实深度，导致深度限制形同虚设。
  原代码中nodeLevel < increasingDepth的分支与else分支逻辑几乎完全重复，属于无意义的冗余代码。更关键的是，代码在DepthLimitedSearch末尾对传入的increasingDepth参数执行自增操作，因为C#值类型为传值调用，这个修改完全不会影响外层的深度设置，属于完全无效的冗余代码。
• 超限深度的节点违规扩展
  当节点计数达到限制深度时，原代码仍会调用ExpandNode()生成所有子节点并压入栈中，直接让实际搜索深度超过设定的限制值；同时因为深度计数错位，部分本该搜索到的深层路径被提前截断，最终导致部分场景下找不到解。
• 重复状态判断效率极低
  每次判断栈内是否有重复状态时，都会调用OpenList.ToList()将栈内全部元素转为List再遍历匹配，8-puzzle搜索分支较多时，重复判断的耗时会被急剧放大，甚至被误判为“程序无法完成搜索”。

修正方向 #

• 外层迭代逻辑改为：从深度0开始逐次递增限制值，每次将当前限制值传入深度受限搜索函数，找到解就直接返回，未找到则将限制深度+1，直到达到预设的最大允许深度
• 给Node类新增depth字段，子节点生成时自动继承父节点深度+1，判断节点时直接使用节点自身的深度值和当前限制深度对比，不再依赖全局计数变量
• 达到限制深度的节点直接跳过扩展步骤，不再生成下层子节点
• 使用哈希表存储已访问的状态字符串，替代原本遍历List查重复的逻辑，大幅提升状态判断效率

内容的提问来源于stack exchange，提问作者G3n1t0