人工智能经典试题及答案(15)

人工智能经典 试题及答案

2、3、4，并且每个圆盘都可以独立的绕轴做逆时针转动，每次转动90°，其初始状态S0和目标状态Sg如图4-31所示，请用广度优先搜索和深度优先搜索，求出从S0到Sg的路径。

初始状态S0 目标状态Sg

图 4-31 圆盘问题

解：设用qA，qB和qC分别表示把A盘，B盘和C盘绕轴逆时针转动90º，这些操作（算符）的排列顺序是qA，qB，qC。

应用广度优先搜索，可得到如下搜索树。在该搜索树中，重复出现的状态不再划出，节点旁边的标识Si，i=0,1,2,…，为按节点被扩展的顺序给出的该节点的状态标识。

由该图可以看出，从初始状态S0到目标状态Sg的路径是 S0→2→5→13(Sg)