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

:..(1)熟悉盲目搜索—有界深度优先算法;(2)通过实验实际操作有界深度优先算法的运行,深入理解其内涵;(3)掌握有界深度优先算法,并会在其他问题中运用。(1)(1)熟悉盲目搜索—有界深度优先算法;(2)通过实验实际操作有界深度优先算法的运行,深入理解其内涵;(3)掌握有界深度优先算法,并会在其他问题中运用。(1)问题描述八数码问题也称为九宫问题。在3×3的棋盘,摆有八个棋子,每个棋子上标有1至8的某一数字,不同棋子上标的数字不相同。棋盘上还有一个空格(以数字0来表示),与空格相邻的棋子可以移到空格中。要求解决的问题是:给出一个初始状态和一个目标状态,找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。(2)有界深度优先算法原理它是从根节点开始,首先扩展最新产生的节点,即沿着搜索树的深度发展下去,一直到没有后继结点处时再返回,换一条路径走下去。就是在搜索树的每一层始终先只扩展一个子节点,不断地向纵深前进直到不能再前进(到达叶子节点或受到深度限制)时,才从当前节点返回到上一