第3章囹搜索与问题求解 第3章圜搜索与问题求解 31状态图搜索 3.2状态图搜索问题求解 3.3与或图搜索 34与或图搜索问题求解 3.5博弈树搜索 习题三 BACK
第 3 章 图搜索与问题求解 第 3 章 图搜索与问题求解 3.1 状态图搜索 3.2 状态图搜索问题求解 3.3 与或图搜索 3.4 与或图搜索问题求解 3.5 博弈树搜索 习题三
第3章囹搜索与问题求解 31状态图搜索 3.1.1状态图 例3.1走迷宫是人们熟悉的一种游戏,如图3-1就是一个 迷宫。如果我们把该迷宫的每一个格子以及入口和出口都作为 节点,把通道作为边,则该迷宫可以由一个有向图表示(如图3 2所示)。那么,走迷宫其实就是从该有向图的初始节点(入口) 出发,寻找目标节点(出口)的问题,或者是寻找通向目标节点(出 口)的路径的问题
第 3 章 图搜索与问题求解 3.1 状 态 图 搜 索 3.1.1 状态图 例3.1 走迷宫是人们熟悉的一种游戏, 如图3－1就是一个 迷宫。如果我们把该迷宫的每一个格子以及入口和出口都作为 节点, 把通道作为边, 则该迷宫可以由一个有向图表示(如图3- 2所示)。 那么, 走迷宫其实就是从该有向图的初始节点(入口) 出发, 寻找目标节点(出口)的问题, 或者是寻找通向目标节点(出 口)的路径的问题
第3章囹搜索与问题求解 S1tnS2es s3 So S4 S5 S6 要数大 数大 受电 s S8 SsS, 图3-1迷宫图
第 3 章 图搜索与问题求解 图 3-1 迷宫图
第3章囹搜索与问题求解 要eS1 S2—S3 So=- S4=S5== S6 要5学|5学 S7S8—Sg g 图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 所示), 给出数码的移动序列。该问题称为八数码难题或重排九 宫问题。 可以看出,图中的一条边(即相邻两个节点的连线)就对应一 次数码移动,反之, 一次数码移动也就对应着图中的一条边。而 数码移动是按数码的移动规则进行的。所以, 图中的一条边也 就代表一个移动规则或者移动规则的一次执行。于是,这个八数 码问题也就是要在该有向图中寻找目标节点, 或找一条从初始节 点到目标节点的路径问题