有界深度优先搜索算法的实现.doc

(1)熟悉盲目搜索—有界深度优先算法;
(2)通过实验实际操作有界深度优先算法的运行,深入理解其内涵;
(3)掌握有界深度优先算法,并会在其他问题中运用。

(1)问题描述
八数码问题也称为九宫问题。在3×3的棋盘,摆有八个棋子,每个棋子上标有1至8的某一数字,不同棋子上标的数字不相同。棋盘上还有一个空格(以数字0来表示),与空格相邻的棋子可以移到空格中。要求解决的问题是:给出一个初始状态和一个目标状态,找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。
(2)有界深度优先算法原理
它是从根节点开始,首先扩展最新产生的节点,即沿着搜索树的深度发展下去,一直到没有后继结点处时再返回,换一条路径走下去。就是在搜索树的每一层始终先只扩展一个子节点,不断地向纵深前进直到不能再前进(到达叶子节点或受到深度限制)时,才从当前节点返回到上一级节点,沿另一方向又继续前进。这种方法的搜索树是从树根开始一枝一枝逐渐形成的。
由于一个有解的问题树可能含有无穷分枝,深度优先搜索如果误入无穷分枝(即深度无限),则不可能找到目标节点。为了避免这种情况的出现,在实施这一方法时,定出一个深度界限,在搜索达到这一深度界限而且尚未找到目标时,即返回重找,所以,深度优先搜索策略是不完备的。另外,应用此策略得到的解不一定是最佳解(最短路径)。

1、 熟悉了解有界深度优先算法;
2、对课堂上讲解的八数码难题的例题(深度界限设为5),编程求解。

(1)设置深度界限,假设为5;
(2)判断初始节点是否为目标节点,若初始节点是目标节点则搜索过程结束;若不是则转到第2步;
(3)由初始节点向第1层扩展,得到节点2,判断节点2是否为目标节点;若是则搜索过程结束;若不是,则将节点2向第2层扩展,得到节点3;
(4)判断节点3是否为目标节点,若是则搜索过程结束;若不是则将节点3向第3层扩展,得到节点4;
(5)判断节点4是否为目标节点,若是则搜索过程结束;若不是则将节点4向第4层扩展,得到节点5;
(6)判断节点5是否为目标节点,若是则搜索过程结束;若不是则结束此轮搜索,返回到第2层,将节点3向第3层扩展得到节点6;
(7)判断节点6是否为目标节点,若是则搜索过程结束;若不是则将节点6向第4层扩展,得到节点7;
(8)判断节点7是否为目标节点,若是则结束搜索过程;若不是则将节点6向第4层扩展得到节点8;
(9)依次类推,直到得到目标节点为止;
(10)搜索过程见附图2所示。