盲目搜索PPT课件.ppt

1、盲目搜索 第一节 搜索 条件反射记忆 搜索：一种问题求解技术 可以转化为状态空间的搜索问题 各种智力游戏问题 F=0-9 T=0-9 W=0-9 O=0-9 U=0-9 R=0-9 F-1 R-0 O-5 T-2 U-1 U-3 W-5,W-1,W-65 5 5 5 = 24+-/ *树 与 图关于图的例子状态空间图问题求解模式问题求解模式 问题的形式化：将环境状态简化为适于问题求解适于问题求解的状态的状态，用状态空间图描述问题。 初始状态 设计算子：对动作建模 目标函数：目标的形式化 路径代价函数：一条路径的代价 求解过程：在状态空间图中一条从初始结点到达目标的路径。这条路径上的所有边对应算

2、子组成的序列，就是解决问题的一个方案 关键技术：问题求解模式 什么是状态？ 城市（旅行） 积木的摆放方式（摆放积木） 事实的集合（几何定理证明） 什么是动作（算子）？（确定、离散） 移动另一个城市 move(x,y) 应用某个定理导出新的事实 什么是目标？（求解成功的条件） 到达目的地 所有的积木都在恰当的位置 导出要证明的事实图搜索 树搜索 树是有向图的特例，每个结点仅有一个父结点 可以将图搜索问题变化为树搜索问题隐式状态空间图 初始状态 图的初始结点 算子（后继函数） 对状态结点 i 使用一个算子得到新的状态结点（称为 i 的后继结点) 目标函数 关于状态（也就是图中结点）的布尔函数GO术

3、语 树 图、有向图、无向图 状态(state)、初始状态 动作、算子(operator,也称后继函数) 目标函数(goal) 、目标状态 状态空间图 搜索结点(search node)问题实例八数码问题 状态：8个棋子在33的棋盘上的任意一个摆放 初始状态：右上图 算子（后继函数）：left、right、up、down 目标函数：右下图 路径代价：1GO问题实例迷宫问题 状态：迷宫中每个方格坐标 初始状态：(0,0) 算子（后继函数） ： left, right, up, down 目标函数：(2,1) 路径代价：1问题实例旅行问题 状态：当前所在的城市 初始状态：出发城市S 算子（后继函数）

4、： 自行车、火车、飞机 目标函数：目的城市G 路径代价：花费的时间和金钱 思考： 如果要解决的问题改为在n个城市的世界中寻找一个旅行计划，要求以最少的时间游览m个城市（2mn），那么问题如何形式化？第二节 盲目搜索技术 广度优先搜索 深度优先搜索 迭代加深搜索2.1 广度优先搜索 breadth-first search，BFS A B F C D E G I演示广度优先搜索 A B F C E G H I演示广度优先搜索算法初始化open表、closed表为空，定义S为初始状态结点将S放入到open表中如果open表为空，则搜索失败，否则从open表中取出第一个结点N,将N放入到closed

5、表中。如果N是目标结点，搜索成功，返回N对N的每一个子结点 i，如果open表和closed表中都没有结点i，那么将结点i其追加到open表的最后一个元素之后标记N到i的连接（如果需要知道中间过程）goto 3开始开始把把S S放入放入OPENOPEN表表OPENOPEN表为空表？表为空表？把第一个节点把第一个节点(n)(n)从从OPENOPEN表移至表移至closedclosed表表节点节点 n n是否是否为目标节点？为目标节点？失败失败成功成功广广度优先算法框图度优先算法框图是是否否是是否否扩展扩展n n，把，把n n的每一个后继节点的每一个后继节点放入放入OPENOPEN表的末端表的末端

6、建立指向节点建立指向节点n n的指针的指针广度优先搜索N openclosed1A2A B,FA3B F,C,D,EA,B4FC,D,E,G,I A,B,F5C D,E,G,IA,B,F,C6D E,G,IA,B,F,C,D7E G,IA,B,F,C,D,E8G I,HA,B,F,C,D,E,G9IHA,B,F,C,D,E,G,I演示广度优先搜索N openclosed1A2A B,FA3B F,C,E,GA,B4FC,E,G,H,I A,B,F5C E,G,H,I,D A,B,F,C6E G,H,I,DA,B,F,C,E7G H,I,DA,B,F,C,E,G8H I,DA,B,F,C,E,G

7、,H9IDA,B,F,C,E,G,H,I演示1238456712384123845674123856712 384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345八数码难题的广度优先搜索树八数码难题的广度优先搜索树13456123845671238456712384567123845671 23845672324252627126782212384567123845671 238456712 384567123845671238456712384567141516171

8、819202112384567广度优先搜索算法初始化open表、closed表为空，定义S为初始状态结点将S放入到open表中如果open表为空，则搜索失败，否则从open表中取出第一个结点N，将N放入到closed表中如果N是目标结点，搜索成功，返回N对N的每一个，那么将结点i追加到open表的最后一个元素之后标记N到i的连接（如果需要知道中间过程）goto 3问题 如何寻找子节点i? Open表中存放的数据是什么？ Closed表中存放的数据是什么？ 为什么要检查Open表和Closed表中是否有节点i存在? 算法的返回值应该是什么？关键的数据结构 Open表 用队列实现 队列：线性表，具

9、有先进先出特征 每次从open表头部取出第一个元素 添加元素到Open表的尾部 Closed表 查找元素 插入元素 图的表示算法分析 分支因子 b 目标结点的最小深度d 由广度优先搜索扩展产生的结点数： 如果不使用Closed表，那么搜索过程中需要存储的结点数目为 O ( b d )11.112bbbbbNddbf算法分析 b=10, 10,000结点/秒, 1000字节/结点深度结点数时间内存211000.11秒1M4111，00011秒106M610719分钟10G810931小时1T(T=KG)101011129天101T12101335年10P(P=KT)1410153523年1KP2

10、.2深度优先搜索（depth-first search） 初始节点：A 目标节点：I 搜索序列：A B C D E F G H I演示深度优先搜索 初始节点：A 目标节点：I 搜索序列：A B C D G E F H I演示深度优先搜索算法初始化open表、closed表为空，定义S为初始状态结点将S 放入open表中如果open表为空，则搜索失败，否则从open表中取出第一个结点N，将N放入closed表中如果N是目标结点，搜索成功，返回N对N的每一个子结点 i，如果open表和closed表中都没有结点i，那么将结点i其插入到open表的第一个元素之前标记N到i的连接（如果需要知道中间过程

11、）goto 3开始开始把把S S放入放入OpenOpen表表OpenOpen表为空表？表为空表？把第一个节点把第一个节点(n)(n)从从OpenOpen表移至表移至ClosedClosed表表n n是否是否为目标节点？为目标节点？失败失败成功成功深深度优先算法框图度优先算法框图是是否否是是否否扩展扩展n n，把，把n n的每一个后继节点的每一个后继节点i i放入放入OPENOPEN表的第一个元素之前表的第一个元素之前建立指向节点建立指向节点n n的指针的指针关键的数据结构 Open表用堆栈实现 堆栈：线性表，具有后进先出特征 每次从open表取出第一个元素，Pop 添加元素到Open表的头部，

12、Push Closed表 查找元素 插入元素深度优先搜索N Open表 Closed表1A2A B,FA3B C,D,E,FA,B4C D,E,FA,B,C5D E,FA,B,C,D6E FA,B,C,D,E7FG,IA,B,C,D,E,F8G H,IA,B,C,D,E,F,G9H IA,B,C,D,E,F,G,H10 IA,B,C,D,E,F,G,H,I演示深度优先搜索N open表 closed表1A2A B,FA3B C,E,G,F A,B4C D,E,G,F A,B,C5D E,G,FA,B,C,D6E G,FA,B,C,D,E7G FA,B,C,D,E,G8FH,IA,B,C,D,E

13、,G,F9H IA,B,C,D,E,G,F,H10 IA,B,C,D,E,G,F,G,I演示算法补充 限制搜索深度 有限图上通常可以找到解 无限图上，可能无法找到解。 当搜索深度超过指定的深度时，则停止扩展节点算法分析 分支因子 b 目标结点的最小深度d 最好情况下，扩展结点d 若限制搜索深度为d最坏情况下，扩展结点 O(bd) 如果在搜索过程中不使用closed表，那么深度优先搜索存储结点数目是搜索深度的线性函数 不能保证搜索到的路径最短演示2.3 迭代加深 结合广度优先和深度优先的优点 广度优先 保证找到最短路径 在不使用closed表的情况下，存储空间O ( b d )，随深度的增长而指

14、数增长 深度优先 在不使用closed表的情况下，存储空间O ( bd) ，随深度的增长而线性增长 不能保证找到最短路径迭代加深搜索算法 令d = 1 执行最大搜索深度 d 的深度优先搜索 如果找到目标结点，那么结束搜索，否则d=d+1, goto 2迭代加深搜索过程复杂度分析 分支因子 b 目标结点的最小深度d 由广度优先搜索扩展产生的结点数： 一个完全的深度优先搜索搜索到第j层扩展的结点数：11.112bbbbbNddbf111bbNjjdf复杂度分析 对深度为d的目标112)1()11(11 1)(11112100010bdbdbbdbbbbbbbbbNNdddjdjjdjjdjdfid

15、j复杂度分析 当d足够大的时候，有如下关系： 如果b =10, 那么迭代加深比广度优先搜索多扩展大约11的结点1bbNNbfid作业一依据下列不同的搜索策略，列出对应的右图中节点访问序列。所有情况下都是最左分支优先访问深度优先广度优先a) 迭代加深（每次迭代深度加1）作业二 55页，习题1.1 阅读41页的传教士与野人问题描述 给出状态表示的格式 描述开始状态 描述目标状态 定义算子，描述每个算子对状态的操作 思考题：将华容道或者推箱子智力游戏问题形式化，以便应用搜索技术求解问题。作业三（选作） 给定3升和4升的水壶各一个，分别记为3和4。开始时3和4都是空的。两个壶都可以用水龙头T灌水，也可

16、以把水从两个壶中倒到排水沟D中，还可以把水从一个壶中倒入另一个壶中。要求找到一个方法让4中水刚好是两升。 形式化这个问题 设计状态的表示方式 给出问题的初始状态 给出问题的目标函数或者目标状态 定义算子，描述每个算子对状态图的操作 画出状态空间图 画出所有不同的状态节点，并且用状态标记每个节点 用合适的算子标记出每一条弧，每个节点至少要画出一条 标记出一条解决问题的路径BACK51写在最后写在最后成功的基础在于好的学习习惯成功的基础在于好的学习习惯The foundation of success lies in good habits谢谢大家荣幸这一路，与你同行ItS An Honor To Walk With You All The Way讲师：XXXXXX XX年XX月XX日