第3章图搜索与问题求解 第3章图搜索与问题求解 3.1状态图搜索 3.2状态图搜索问题求解 3.3与或图搜索 3.4与或图搜索问题求解 3.5博弈树搜索 习题三 BACK
第 3 章 图搜索与问题求解 第 3 章 图搜索与问题求解 3.1 状态图搜索 3.2 状态图搜索问题求解 3.3 与或图搜索 3.4 与或图搜索问题求解 3.5 博弈树搜索 习题三
第3章图搜索与问题求解 3.1状态图搜索 3.1.1状态图 例3.1走迷宫是人们熟悉的一种游戏，如图3一1就是一个 迷宫。如果我们把该迷宫的每一个格子以及入口和出口都作为 节点，把通道作为边，则该迷宫可以由一个有向图表示（如图3 2所示)。那么，走迷宫其实就是从该有向图的初始节点（入口） 出发，寻找目标节点（出口）的问题，或者是寻找通向目标节点（出 口)的路径的问题
第 3 章 图搜索与问题求解 3.1 状 态 图 搜 索 3.1.1 状态图 例3.1 走迷宫是人们熟悉的一种游戏, 如图3－1就是一个 迷宫。如果我们把该迷宫的每一个格子以及入口和出口都作为 节点, 把通道作为边, 则该迷宫可以由一个有向图表示(如图3- 2所示)。 那么, 走迷宫其实就是从该有向图的初始节点(入口) 出发, 寻找目标节点(出口)的问题, 或者是寻找通向目标节点(出 口)的路径的问题
第3章图搜索与问题求解 西安电 淡 西安地 S S2 S3 上十十 发大学 发班 So S4 Ss S6 戴 汤终地 T Sg 西安电 图3-1迷宫图
第 3 章 图搜索与问题求解 图 3-1 迷宫图
第3章图搜索与问题求解 品安电子科 S1-S2一S3 学成版烈 品安电子科餐学店发轻 西安心子形发大受成救双 S。S4S5S6 爱成版应 西安电子科发 西安电子将成大学成版阳 S7S8Sg—Sg 图3-2迷宫的有向图表示
第 3 章 图搜索与问题求解 图 3-2 迷宫的有向图表示
第3章图搜索与问题求解 例3.2在一个3×3的方格棋盘上放置着1,2,3,4,5,6， 7,8八个数码，每个数码占一格，且有一个空格。这些数码可 在棋盘上移动，其移动规则是：与空格相邻的数码方可移入空 格。现在的问题是：对于指定的初始棋局和目标棋局（如图3-3 所示)，给出数码的移动序列。该问题称为八数码难题或重排九 宫问题 。 可以看出，图中的一条边（即相邻两个节点的连线）就对应 次数码移动，反之，一次数码移动也就对应着图中的一条边。而 数码移动是按数码的移动规则进行的。所以，图中的一条边也 就代表一个移动规则或者移动规则的一次执行。于是，这个八数 码问题也就是要在该有向图中寻找目标节点，或找一条从初始节 点到目标节点的路径问题
第 3 章 图搜索与问题求解 例 3.2 在一个3×3的方格棋盘上放置着1, 2, 3, 4, 5, 6, 7, 8八个数码, 每个数码占一格, 且有一个空格。 这些数码可 在棋盘上移动, 其移动规则是：与空格相邻的数码方可移入空 格。现在的问题是：对于指定的初始棋局和目标棋局(如图3-3 所示), 给出数码的移动序列。该问题称为八数码难题或重排九 宫问题。 可以看出,图中的一条边(即相邻两个节点的连线)就对应一 次数码移动,反之, 一次数码移动也就对应着图中的一条边。而 数码移动是按数码的移动规则进行的。所以, 图中的一条边也 就代表一个移动规则或者移动规则的一次执行。于是,这个八数 码问题也就是要在该有向图中寻找目标节点, 或找一条从初始节 点到目标节点的路径问题
第3章图搜索与问题求解 西关 2 8 3 8 3 1电 学4 2 大版4 7 6 5 7 6 5 西爽 初始棋局 目标棋局 图3-3八数码问题示例
第 3 章 图搜索与问题求解 图 3-3 八数码问题示例
第3章图搜索与问题求解 3.1.2状态图搜索 1.搜索方式 用计算机来实现状态图的搜索，有两种最基本的方式： 树式搜索和线式搜索。 所谓树式搜索，形象地讲就是以“画树”的方式进行搜索。 即从树根（初始节点）出发，一笔一笔地描出一棵树来。准确地 讲，树式搜索就是在搜索过程中记录所经过的所有节点和边。 所以，树式搜索所记录的轨迹始终是一棵“树”，这棵树也就 是搜索过程中厅产生的搜索树
第 3 章 图搜索与问题求解 3.1.2 状态图搜索 1. 用计算机来实现状态图的搜索, 有两种最基本的方式： 树式搜索和线式搜索。 所谓树式搜索, 形象地讲就是以“画树”的方式进行搜索。 即从树根(初始节点)出发, 一笔一笔地描出一棵树来。准确地 讲, 树式搜索就是在搜索过程中记录所经过的所有节点和边。 所以, 树式搜索所记录的轨迹始终是一棵“树” , 这棵树也就 是搜索过程中所产生的搜索树
第3章图搜索与问题求解 所谓线式搜索，形象地讲就是以“画线”的方式进行搜索。 准确地讲，线式搜索在搜索过程中只记录那些当前认为是处在 所找路径上的节点和边。所以，线式搜索所记录的轨迹始终是 一条“线”（折线）
第 3 章 图搜索与问题求解 所谓线式搜索, 形象地讲就是以“画线”的方式进行搜索。 准确地讲, 线式搜索在搜索过程中只记录那些当前认为是处在 所找路径上的节点和边。所以,线式搜索所记录的轨迹始终是 一条“线”(折线)
第3章图搜索与问题求解 线式搜索的基本方式又可分为不回溯的和可回溯的两种 不回溯的线式搜索就是每到一个“叉路口”仅沿一条路继续前 进，即对每一个节点始终都仅生成一个子节点（如果有子节点 的话)。生成一个节点的子节点也称对该节点进行扩展。这样， 如果扩展到某一个节点，该节点恰好就是目标节点，则搜索成 功；如果直到不能再扩展时，还未找到目标节点，则搜索失败。 可回溯的线式搜索也是对每一个节点都仅扩展一条边，但当不 能再扩展时，则退回一个节点，然后再扩展另一条边（如果有 的话)。这样，要么最终找到了目标节点，搜索成功；要么一 直回溯到初始节点也未找到目标节点，则搜索失败
第 3 章 图搜索与问题求解 线式搜索的基本方式又可分为不回溯的和可回溯的两种。 不回溯的线式搜索就是每到一个“叉路口”仅沿一条路继续前 进, 即对每一个节点始终都仅生成一个子节点(如果有子节点 的话)。 生成一个节点的子节点也称对该节点进行扩展。这样, 如果扩展到某一个节点, 该节点恰好就是目标节点,则搜索成 功；如果直到不能再扩展时, 还未找到目标节点,则搜索失败。 可回溯的线式搜索也是对每一个节点都仅扩展一条边,但当不 能再扩展时, 则退回一个节点, 然后再扩展另一条边(如果有 的话)。 这样, 要么最终找到了目标节点, 搜索成功；要么一 直回溯到初始节点也未找到目标节点, 则搜索失败
第3章图搜索与问题求解 由上所述可以看出，树式搜索成功后，还需再从搜索树中 找出所求路径，而线式搜索只要搜索成功，则“搜索线”就是 所找的路径，即问题的解。 那么，又怎样从搜索树中找出所求路径呢？这只需在扩 展节点时记住节点间的父子关系即可。这样，当搜索成功时， 从目标节点反向沿搜索树按所作标记追溯回去一直到初始节点 便得到一条从初始节点到目标节点的路径，即问题的一个解
第 3 章 图搜索与问题求解 由上所述可以看出, 树式搜索成功后, 还需再从搜索树中 找出所求路径, 而线式搜索只要搜索成功, 则“搜索线”就是 所找的路径, 即问题的解。 那么, 又怎样从搜索树中找出所求路径呢？ 这只需在扩 展节点时记住节点间的父子关系即可。 这样, 当搜索成功时, 从目标节点反向沿搜索树按所作标记追溯回去一直到初始节点, 便得到一条从初始节点到目标节点的路径, 即问题的一个解