用有界深度优先搜索方法求解图5．12所示八数码难题。初始状态为S0，目标状态Sg，要求寻找从初始状态到目标状态的路径。 2 8 1 2 3-|||-1 6 3 8 4-|||-7 5 4 7 6 5-|||-_(6) S8-|||-图5.12 八数码难题

考查要点：本题主要考查对有界深度优先搜索（BDS）算法的理解，包括其核心思想、搜索过程及深度界限对求解结果的影响。

解题核心思路：

• 有界深度优先搜索是一种结合深度优先搜索和深度限制的算法，通过设置最大搜索深度避免无限循环，但可能导致无法找到解（即不完备性）。
• 关键点在于理解：若深度界限设置过小，可能剪枝掉正确路径；若过大，会降低效率。本题通过具体实例说明这一矛盾。

破题关键：

• 明确BDS的搜索规则：从初始状态出发，按深度优先展开，但仅在指定深度内探索。
• 通过题目中的示例（深度界限$d_m=5$时无解），体会算法的不完备性。

1. 算法概述

有界深度优先搜索（BDS）在标准深度优先搜索的基础上增加了深度限制$d_m$，仅展开深度不超过$d_m$的节点。若目标状态的路径长度超过$d_m$，则无法被发现。

2. 搜索过程分析

• 初始状态$S_0$：

  2 8 1  
  6 3 8  
  4 7 5  

• 目标状态$S_g$：

  2 3 1  
  6 4 7  
  5 8 6 5  

  （注：题目中目标状态描述可能存在排版问题，实际应为3×3矩阵，此处假设合理化处理。）

• 搜索规则：
  从$S_0$开始，生成所有合法移动（空格移动），按深度优先展开，但深度不超过$d_m=5$。

  • 若在深度5内找到$S_g$，返回路径；否则，输出“无解”。

3. 关键结论

• 深度界限$d_m=5$时无解：说明目标状态的最短路径长度超过5，或该状态下无解。
• 算法不完备性：BDS可能因深度限制无法找到正确解，需动态调整深度或改用其他算法（如迭代加深）。