第3章图搜索与问题求解

《第3章图搜索与问题求解》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第3章图搜索与问题求解3.1状态图搜索3.2状态图搜索问题求解3.3与或图搜索3.4与或图搜索问题求解3.5博弈树搜索习题三3.1状态图搜索3.1.1状态图例3.1走迷宫是人们熟悉的一种游戏,如图3－1就是一个迷宫。如果我们把该迷宫的每一个格子以及入口和出口都作为节点,把通道作为边,则该迷宫可以由一个有向图表示(如图3-2所示)。那么,走迷宫其实就是从该有向图的初始节点(入口)出发,寻找目标节点(出口)的问题,或者是寻找通向目标节点(出口)的路径的问题。图3-1迷宫图图3-2迷宫的有向图表示例3.2在一个3×3的方格棋盘上放置着1,2,

2、3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格。这些数码可在棋盘上移动,其移动规则是：与空格相邻的数码方可移入空格。现在的问题是：对于指定的初始棋局和目标棋局(如图3-3所示),给出数码的移动序列。该问题称为八数码难题或重排九宫问题。可以看出,图中的一条边(即相邻两个节点的连线)就对应一次数码移动,反之,一次数码移动也就对应着图中的一条边。而数码移动是按数码的移动规则进行的。所以,图中的一条边也就代表一个移动规则或者移动规则的一次执行。于是,这个八数码问题也就是要在该有向图中寻找目标节点,或找一条从初始节点到目标节点的路

3、径问题。图3-3八数码问题示例3.1.2状态图搜索1.搜索方式用计算机来实现状态图的搜索,有两种最基本的方式：树式搜索和线式搜索。所谓树式搜索,形象地讲就是以“画树”的方式进行搜索。即从树根(初始节点)出发,一笔一笔地描出一棵树来。准确地讲,树式搜索就是在搜索过程中记录所经过的所有节点和边。所以,树式搜索所记录的轨迹始终是一棵“树”,这棵树也就是搜索过程中所产生的搜索树。所谓线式搜索,形象地讲就是以“画线”的方式进行搜索。准确地讲,线式搜索在搜索过程中只记录那些当前认为是处在所找路径上的节点和边。所以,线式搜索所记录的轨迹始终是一条

4、“线”(折线)。线式搜索的基本方式又可分为不回溯的和可回溯的两种。不回溯的线式搜索就是每到一个“叉路口”仅沿一条路继续前进,即对每一个节点始终都仅生成一个子节点(如果有子节点的话)。生成一个节点的子节点也称对该节点进行扩展。这样,如果扩展到某一个节点,该节点恰好就是目标节点,则搜索成功；如果直到不能再扩展时,还未找到目标节点,则搜索失败。可回溯的线式搜索也是对每一个节点都仅扩展一条边,但当不能再扩展时,则退回一个节点,然后再扩展另一条边(如果有的话)。这样,要么最终找到了目标节点,搜索成功；要么一直回溯到初始节点也未找到目标节点,则搜

5、索失败。由上所述可以看出,树式搜索成功后,还需再从搜索树中找出所求路径,而线式搜索只要搜索成功,则“搜索线”就是所找的路径,即问题的解。那么,又怎样从搜索树中找出所求路径呢？这只需在扩展节点时记住节点间的父子关系即可。这样,当搜索成功时,从目标节点反向沿搜索树按所作标记追溯回去一直到初始节点,便得到一条从初始节点到目标节点的路径,即问题的一个解。2.搜索策略由于搜索具有探索性,所以要提高搜索效率(尽快地找到目标节点),或要找最佳路径(最佳解)就必须注意搜索策略。对于状态图搜索,已经提出了许多策略,它们大体可分为盲目搜索和启发式(he

6、uristic)搜索两大类。通俗地讲,盲目搜索就是无“向导”的搜索,启发式搜索就是有“向导”的搜索。那么,树式盲目搜索就是穷举式搜索,即从初始节点出发,沿连接边逐一考察各个节点(看是否为目标节点),或者反向进行；而线式盲目搜索,对于不回溯的就是随机碰撞式搜索,对于回溯的则也是穷举式的搜索。启发式搜索则是利用“启发性信息”引导的搜索。所谓“启发性信息”就是与问题有关的有利于尽快找到问题解的信息或知识。例如：“欲速则不达”、“知已知彼,百战不殆”、“学如逆水行舟不进则退”等格言,就是指导人们行为的启发性信息。常识告诉我们,如果有向导引路,

7、则就会少走弯路而事半功倍。所以,启发式搜索往往会提高搜索效率,而且可能找到问题的最优解。根据启发性信息的内容和使用方式的不同,启发式搜索又可分为许多不同的策略,如全局择优、局部择优、最佳图搜索等等。按搜索范围的扩展顺序的不同,搜索又可分为广度优先和深度优先两种类型。对于树式搜索,既可深度优先进行,也可广度优先进行。对于线式搜索则总是深度优先进行。3.搜索算法由于搜索的目的是为了寻找初始节点到目标节点的路径,所以在搜索过程中就得随时记录搜索轨迹。为此,我们用一个称为CLOSED表的动态数据结构来专门记录考查过的节点。显然,对于树式搜索

8、来说,CLOSED表中存储的正是一棵不断成长的搜索树；而对于线式搜索来说,CLOSED表中存储的是一条不断伸长的折线,它可能本身就是所求的路径(如果能找到目标节点的话)。另一方面,对于树式搜索来说,还得不