文档库

最新最全的文档下载
当前位置:文档库 > 有界深度优先搜索算法的实现

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

实验报告有界深度优先搜索算法的实现

一.实验目的

(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所示。

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

五.程序

六.实验结果和分析

通过这次实验和以前做过的分析,在宽度优先搜索过程中,扩展到第

26个节点时找到了目标节点;而在深度优先搜索过程中,扩展到第18个节点时得到了目标节点。

在宽度优先搜索过程中,需要遍历目标节点所在层之前每层的所有节点,即需要遍历所有的分支。而深度优先搜索过程中,则不需要遍历这么多的节点。所以,在“八”数码难题的求解过程中,深度优先搜索的效率明显比宽度优先搜索的效率要高。

一般情况下,深度优先适合深度大的树,不适合广度大的树,广度优先则正好相反。所谓深度大的树就是指起始节点到目标节点的中间节点多的树(可以理解成问题有很多中间解,这些解都可以认为是部分正确的,但要得到完全正确的结果——目标节点,就必须先依次求出这些中间解)。所谓广度大的树就是指起始节点到目标节点的可能节点很多的树(可以理解成问题有很多可能解,这些解要么正确,要么错误。要得到完全正确的结果——目标节点,就必须依次判断这些可能解是否正确)。多数情况下,深度优先搜索的效率要高于宽度优先搜索。但某些时候,对于这两种搜索策略的优劣(或效率)还需要针对不同的问题进行具体分析比较。

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

5、关于坚持的名言,

你既然期望辉煌伟大的一生,那么就应该从今天起,以毫不动摇的决心和坚定不移的信念,凭自己的智慧和毅力,去创造你和人类的快乐。——佚名

6、最可怕的敌人,就是没有坚强的信念。——罗曼·罗兰

7、只要持续地努力,不懈地奋斗,就没有征服不了的东西。——塞内加

8、无论是美女的歌声,还是鬓狗的狂吠,无论是鳄鱼的眼泪,还是恶狼的嚎叫,都不会使我动摇。——恰普曼

9、书不记,熟读可记;义不精,细思可精;惟有志不立,直是无着力处。——朱熹

10、既然我已经踏上这条道路,那么,任何东西都不应妨碍我沿着这条路走下去。——康德

11、坚强的信念能赢得强者的心,并使他们变得更坚强。——白哲特

12、三军可夺帅也,匹夫不可夺志也。——佚名

13、立志不坚,终不济事。——朱熹

14、富贵不能淫,贫贱不能移,威武不能屈。——孟子

15、关于坚持的名言,意志目标不在自然中存在,而在生命中蕴藏。——武者小路实笃

关于坚持不懈的50条励志名人名言

16、意志若是屈从,不论程度如何,它都帮助了暴力。——但丁

17、只要有坚强的意志力,就自然而然地会有能耐、机灵和知识。——陀思妥耶夫斯基

18、功崇惟志,业广惟勤。——佚名

19、能够岿然不动,坚持正见,度过难关的人是不多的。——雨果

20、立志用功如种树然,方其根芽,犹未有干;及其有干,尚未有枝;枝而后叶,叶而后花。——王守仁

21、谁有历经千辛万苦的意志,谁就能达到任何目的。——米南德

22、不作什么决定的意志不是现实的意志;无性格的人从来不做出决定。——黑格尔

23、执着追求并从中得到最大快乐的人,才是成功者。——梭罗

24、有了坚定的意志,就等于给双脚添了一对翅膀。——乔·贝利

25、有百折不挠的信念的所支持的人的意志,比那些似乎是无敌的物质力量有更强大的威力。——爱因斯坦

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

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

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

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

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

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

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