第3章图搜索与问题求解 .ppt
《第3章图搜索与问题求解 .ppt》由会员分享,可在线阅读,更多相关《第3章图搜索与问题求解 .ppt(168页珍藏版)》请在文库网上搜索。
1、 第 3 章 搜索 求解 图 与问题第 3 章 搜索 求解 图 与问题3.1 状态图搜索 3.2 状态图搜索问题求解 3.3 与或图搜索 3.4 与或图搜索问题求解 3.5 博弈树搜索 习题三 第 3 章 搜索 求解 图 与问题3.1 状 态 图 搜 索 3.1.1 状态图例3.1 走迷宫是人们熟悉的一种游戏, 如图31就是一个迷宫。如果我们把该迷宫的每一个格子以及入口和出口都作为节点, 把通道作为边, 则该迷宫可以由一个有向图表示(如图3-2所示)。 那么, 走迷宫其实就是从该有向图的初始节点(入口)出发, 寻找目标节点(出口)的问题, 或者是寻找通向目标节点(出口)的路径的问题。 第 3
2、章 搜索 求解 图 与问题图 3-1 迷宫图 第 3 章 搜索 求解 图 与问题图 3-2 迷宫的有向图表示 第 3 章 搜索 求解 图 与问题例 3.2 在一个33的方格棋盘上放置着1, 2, 3, 4, 5, 6, 7, 8八个数码, 每个数码占一格, 且有一个空格。 这些数码可在棋盘上移动, 其移动规则是:与空格相邻的数码方可移入空格。现在的问题是:对于指定的初始棋局和目标棋局(如图3-3所示), 给出数码的移动序列。该问题称为八数码 题或 宫问题。 可以 出,图 的一 边( 相邻 个节点的 )就对一 数码移动, , 一 数码移动 就对 着图 的一 边。 数码移动是 数码的移动规则 的。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 搜索 问题 求解