题目

设有3个大小不等的圆盘A、B、C套在一根轴上，每个圆盘上都标有数字1、2、3、4，并且每个圆盘都可以独立地绕轴做逆时针转动，每次转动90°，初始状态[1]S0和目标状态Sg如图5．11所示，分别用宽度优先搜索法和深度优先搜索[2]法求从S0到Sg的路径。 2-|||-2-|||-BA 2 B. 3-|||-3{3(3 1)11 23 2 1|4-|||-4 1-|||-4 4-|||-4 3-|||-初始状态S0 目标状态S8-|||-图5.11 圆盘问题

设有3个大小不等的圆盘A、B、C套在一根轴上，每个圆盘上都标有数字1、2、3、4，并且每个圆盘都可以独立地绕轴做逆时针转动，每次转动90°，初始状态[1]S0和目标状态Sg如图5．11所示，分别用宽度优先搜索法和深度优先搜索[2]法求从S0到Sg的路径。



题目解答

答案

设rA、rB、rC分别为将盘子A、B、C逆时针旋转90°的操作在运用这些操作符时的顺序为rA、rB、rC。 应用宽度优先搜索的搜索树如图5．18所示。从图中可以看出从初始状态S0到目标状态Sg的路径是：S0→2→5→11→22(Sg)应用深度优先搜索的搜索树如图5．19所示。这里要指出的是我们在应用深度优先搜索算法时稍微作了一些改进即不是只对当前节点判断其是否为目标节点而是对当前节点的扩展节点进行判断如果扩展节点中含有目标节点则搜索停止求解成功。这有利于提高求解效率。 从图中可以看出从初始状态S0到目标状态Sg的路径是： S0→2→3→4→Sg
设rA、rB、rC分别为将盘子A、B、C逆时针旋转90°的操作,在运用这些操作符时的顺序为,rA、rB、rC。应用宽度优先搜索的搜索树如图5．18所示。从图中可以看出,从初始状态S0到目标状态Sg的路径是：S0→2→5→11→22(Sg)应用深度优先搜索的搜索树如图5．19所示。这里要指出的是,我们在应用深度优先搜索算法时,稍微作了一些改进,即不是只对当前节点判断其是否为目标节点,而是对当前节点的扩展节点进行判断,如果扩展节点中含有目标节点,则搜索停止,求解成功。这有利于提高求解效率。从图中可以看出,从初始状态S0到目标状态Sg的路径是：S0→2→3→4→Sg

解析

考查要点：本题主要考查宽度优先搜索（BFS）和深度优先搜索（DFS）在状态空间中的应用，以及两种算法在路径搜索中的区别。

解题核心思路：

  1. 状态表示：每个状态由圆盘A、B、C的当前旋转位置共同决定。
  2. 操作符定义：每次操作可选择逆时针旋转A、B、C中的一个圆盘90°，操作顺序固定为r_A → r_B → r_C。
  3. 搜索策略：
    • BFS：逐层扩展所有可能状态，保证找到最短路径。
    • DFS：优先深入某条路径，通过改进（提前判断子节点是否为目标）提高效率。

破题关键点：

  • 状态空间构建：明确每个操作对状态的改变。
  • 算法特性应用：BFS适合找最短路径，DFS通过改进减少冗余判断。

状态空间与操作符

  • 状态：由圆盘A、B、C的数字排列组合表示。
  • 操作符：r_A（旋转A）、r_B（旋转B）、r_C（旋转C），每次操作仅改变对应圆盘的位置。

宽度优先搜索（BFS）

  1. 初始化：队列中加入初始状态S0。
  2. 扩展节点：依次对队列中的每个状态应用r_A、r_B、r_C，生成子节点。
  3. 判断目标：若子节点为Sg，则终止；否则将新状态加入队列。
  4. 路径记录：通过状态编号追踪路径，最终路径为 S0 → 2 → 5 → 11 → 22(Sg)。

深度优先搜索（DFS）

  1. 初始化：堆栈中加入初始状态S0。
  2. 扩展节点：优先扩展当前路径的最深节点，应用r_A、r_B、r_C生成子节点。
  3. 改进判断：提前检查子节点是否为目标，若命中则终止。
  4. 路径记录：最终路径为 S0 → 2 → 3 → 4 → Sg。