PPT《第3章图搜索与问题求解》

第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, 3, 4, 5, 6, 7, 8八个数码, 每个数码占一格, 且有一个空格. 这些数码可在棋盘上移动, 其移动规则是:与空格相邻的数码方可移入空格.现在的问题是:对于指定的初始棋局和目标棋局(如图3-3所示), 给出数码的移动序列.该问题称为八数码难题或重排九宫问题. 可以看出,图中的一条边(即相邻两个节点的连线)就对应一次数码移动,反之, 一次数码移动也就对应着图中的一条边.而数码移动是按数码的移动规则进行的.所以, 图中的一条边也就代表一个移动规则或者移动规则的一次执行.于是,这个八数码问题也就是要在该有向图中寻找目标节点, 或找一条从初始节点到目标节点的路径问题. 图3-3 八数码问题示例 3.1.2 状态图搜索 1. 搜索方式 用计算机来实现状态图的搜索, 有两种最基本的方式: 树式搜索和线式搜索. 所谓树式搜索, 形象地讲就是以 画树 的方式进行搜索. 即从树根(初始节点)出发, 一笔一笔地描出一棵树来.准确地讲, 树式搜索就是在搜索过程中记录所经过的所有节点和边. 所以, 树式搜索所记录的轨迹始终是一棵 树 , 这棵树也就是搜索过程中所产生的搜索树. 所谓线式搜索, 形象地讲就是以 画线 的方式进行搜索. 准确地讲, 线式搜索在搜索过程中只记录那些当前认为是处在所找路径上的节点和边.所以,线式搜索所记录的轨迹始终是一条 线 (折线). 线式搜索的基本方式又可分为不回溯的和可回溯的两种. 不回溯的线式搜索就是每到一个 叉路口 仅沿一条路继续前进, 即对每一个节点始终都仅生成一个子节点(如果有子节点的话). 生成一个节点的子节点也称对该节点进行扩展.这样,如果扩展到某一个节点, 该节点恰好就是目标节点,则搜索成功;

如果直到不能再扩展时, 还未找到目标节点,则搜索失败.可回溯的线式搜索也是对每一个节点都仅扩展一条边,但当不能再扩展时, 则退回一个节点, 然后再扩展另一条边(如果有的话). 这样, 要么最终找到了目标节点, 搜索成功;

要么一直回溯到初始节点也未找到目标节点, 则搜索失败. 由上所述可以看出, 树式搜索成功后, 还需再从搜索树中找出所求路径, 而线式搜索只要搜索成功, 则 搜索线 就是所找的路径, 即问题的解. 那么, 又怎样从搜索树中找出所求路径呢? 这只需在扩展节点时记住节点间的父子关系即可. 这样, 当搜索成功时, 从目标节点反向沿搜索树按所作标记追溯回去一直到初始节点, 便得到一条从初始节点到目标节点的路径, 即问题的一个解. 2. 搜索策略 由于搜索具有探索性, 所以要提高搜索效率(尽快地找到目标节点), 或要找最佳路径(最佳解)就必须注意搜索策略. 对于状态图搜索, 已经提出了许多策略, 它们大体可分为盲目搜索和启发式(heuristic)搜索两大类. 通俗地讲, 盲目搜索就是无 向导 的搜索, 启发式搜索就是有 向导 的搜索.那么, 树式盲目搜索就是穷举式搜索, 即从初始节点出发, 沿连接边逐一考察各个节点(看是否为目标节点), 或者反向进行;