《人工智能》搜索技术课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《《人工智能》搜索技术课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 搜索 技术 课件
- 资源描述:
-
1、第四章 搜索技术n状态空间法n问题归约法n博弈树搜索n局部搜索How to find the best path in game ?迷宫问题s-s s s s s s-s-s-ss-s-s-s s s s s s s s-s-s-s-s S0Sg搜索的挑战组合爆炸n魔方问题n博弈问题n皇后问题n行商问题n排课问题(调度问题)n背包问题 数码问题1238456712384567(目标状态)(初始状态)八数码难题(8-puzzle problem)426183574.1 状态图概念n状态图的概念 状态图(状态空间图)实际上是一类问题的抽象表示。n许多智力问题(八数码问题、梵塔问题、旅行商问题、八皇
2、后问题、农夫过河问题等)。n 实际问题(如路径规划、定理证明、演绎推理、机器人行动规划等)都可以归结为在某一状态图中寻找目标或路径的问题。农夫过河问题n 有一个农夫带一条狼、一只羊和一棵白菜过河。如果没有农夫看管,则狼要吃羊,羊要吃白菜。但是船很小,只够农夫带一样东西过河。问农夫该如何解此难题? 农夫过河问题状态空间法表示n以向量(人,狼,羊,菜)表示状态,其中每个变元可取0或1,取0表示在左岸(出发点),取1表示在右岸n初态是:(0,0,0,0)n终态是:(1,1,1,1)n非法中间状态有: (0,0,1,1),(0,1,1,0),(0,1,1,1), (1,1,0,0),(1,0,0,1)
3、,(1,0,0,0)。 (1,0,0,1)(0,0,0,0)(1,0,1,0)(1,1,0,0)(0,0,1,0)(1,1,1,0)(1,0,1,1)(0,1,1,0)(0,0,1,1)(人,狼,羊,菜)(人,狼,羊,菜)(0,0,0,1)(1,1,0,1)(0,1,0,1) (1,1,1,1)4.2 状态空间法n问题的状态空间表示(状态图表示) 状态空间的三元组(S, O, G)表示. S:初始状态集合; O: 操作集合; G:目标状态集合n状态空间的搜索策略(状态图搜索)广度优先搜索, 深度优先搜索, 启发式搜索状态空间表示的概念n例如下棋、迷宫及各种游戏。OriginalStateMid
4、dleStateGoalState三数码难题123123123312312312初始棋局目标棋局1238456712384123845674123856712 384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345八数码难题的宽度优先搜索树13456123845671238456712384567123845671 238456723242526271236782212384567123845671 238456712 3845671238456712384567123
5、84567141516171819202112384567状态图搜索n图搜索是指在状态图中寻找目标或路径的搜索。n所谓搜索,顾名思义,就是从初始节点出发,沿着与之相连的边试探地前进,寻找目标节点的过程(也可以反向进行)。问题状态图搜索解解是由初始状态到目标状态的路径状态图搜索相关问题n状态选择n解的性质:存在、分布、质量n搜索策略图搜索策略 n图搜索控制策略一种在状态图中寻找路径的方法。图中每个节点对应一个状态,每条连线对应一个操作符。n图搜索涉及两个主要数据结构:open表 closed表OPEN 表n OPEN表是一种动态数据结构,专门登记当前待考查(待访问)的节点,也叫未扩展节点表 。节
6、点节点父节点编号父节点编号OPEN表表open表中,每个节点信息还包括指向父节点的返回指针(即父节点地址)CLOSED 表表n Closed表是一种动态数据结构,记录访问过的节点,也叫已扩展节点表 ,其初始为空表。 编号编号节点节点父节点编号父节点编号CLOSED表表开始开始把把S放入放入OPEN表表OPEN表为空表?表为空表?把第一个节点把第一个节点(n)从从OPEN表移至表移至CLOSED表表n为目标节点吗?为目标节点吗?把把n的后继节点放入的后继节点放入OPEN表的表的末端,提供返回节点末端,提供返回节点n的指针的指针修改指针方向修改指针方向重排重排OPEN表表失败失败成功成功 图搜索过
7、程框图图搜索过程框图是是是是否否否否搜索策略即搜索策略即体现在这里体现在这里按搜索轨迹分类n图式搜索图式搜索:搜索过程中,搜索路径允许形成回路。n树式搜索树式搜索:搜索过程中,搜索路径不允许形成回路。n线式搜索线式搜索:扩展节点每次只扩展一个节点。SGSG搜索树的概念 n一个可以搜索出某个可行解的问题,如“农夫、白菜、羊、狼”和“八数码难题”等,虽然从表面上看上去和“树”这种结构无关,但是整个搜索过程中的可能试探点所行成的搜索空间总可以对应到一颗搜索树上去。n将各类形式上不同的搜索问题抽象并统一成为搜索树的形式,为算法的设计与分析带来巨大的方便。 22178634582736451827163
8、452282763451238276345114687634512787345126152163458782345817631645827931458276171621786345381635472108354276181654273813542761821786345481356247128456217381546273138136274521202178365452178634511119(1,0,0,1)(0,0,0,0)(1,0,1,0)(1,1,0,0)(0,0,1,0)(1,1,1,0)(1,0,1,1)(0,1,1,0)(0,0,1,1)(人,狼,羊,菜)(人,狼,羊,菜)(0,
9、0,0,1)(1,1,0,1)(0,1,0,1) (1,1,1,1)n由于搜索具有探索性,所以要提高搜索效率(尽快地找到目标节点),或要找最佳路径(最佳解)就必须注意搜索策略。n对于状态图搜索,已经提出了许多策略,它们大体可分为盲目搜索(bland search)和启发式搜索(heuristic search)两大类。n盲目搜索是无向导搜索。n启发式搜索是有向导搜索,即利用启发信息(函数)引导去寻找问题解。搜索策略分类搜索策略分类盲目搜索n盲目搜索又叫做无信息搜索,一般只适用于求解比较简单的问题。n种类:宽度优先搜索深度优先搜索等代价搜索图搜索策略宽度优先深度优先启发式搜索一种在图中寻找路径的
10、方法。宽度优先搜索策略n优先搜索状态空间中离初始状态近的节点(状态n特点:具有完备性, 占用空间n搜索算法n 数据结构:OPEN表 : 先进先出队列先进先出队列,存放待扩展的节点. 节点(状态) 父节点编号(返回指针)CLOSED表 : 存放已被扩展过的节点.编号 节点 父节点编号开始开始把把S放入放入OPEN表表OPEN表为空表?表为空表?把第一个节点把第一个节点(n)从从OPEN表移至表移至CLOSED表表是否有后继节点是否有后继节点为目标节点?为目标节点?扩展扩展n,把,把n的后继节点放入的后继节点放入OPEN表的表的末端末端,提供返回节点,提供返回节点n的指针的指针失败失败成功成功 宽
11、度优先算法框图宽度优先算法框图是是否否是是否否v 算法否否宽度优先搜索算法nStep1: 把初始节点S0放入OPEN表中;nStep2: 若OPEN表为空,则搜索失败,退出.nStep3: 移出OPEN表中第一个节点N放入CLOSED表 中, 并标以顺序号n;nStep4: 若目标节点Sg=N, 则搜索成功,结束.nStep5: 若N不可扩展, 则转Step2;nStep6: 扩展N, 将生成的一组子节点配上指向N的指针后, 放入放入OPEN表尾部表尾部, 转 Step2;n 例子例子八数码难题(八数码难题(8-puzzle problem) 1238456712384567(目标状态)(初始
12、状态)规定:将牌移入空格的顺序为:从空格左边开始顺时针旋转。不许斜向移动,也不返回先辈节点。从图可见,要扩展26个节点,共生成26个节点之后才求得解(目标节点)。1238456712384123845674123856712 384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345图 八数码难题的宽度优先搜索树13456123845671238456712384567123845671 238456723242526271236782212384567123845671
13、238456712 384567123845671238456712384567141516171819202112384567宽度优先搜索宽度优先搜索(新的节点被插入到栈OPEN的后部12345OPEN= (1)CLOSED=( )6789101112131415宽度优先搜索宽度优先搜索(新的节点被插入到栈OPEN的后部12345OPEN= (2,3)CLOSED=(1 )6789101112131415宽度优先搜索宽度优先搜索(新的节点被插入到栈OPEN的后部12345OPEN= (3,4,5)CLOSED=(1,2 )6789101112131415宽度优先搜索宽度优先搜索(新的节点被插
14、入到栈OPEN的后部12345OPEN= (4,5,10,11)CLOSED=(1,2,3 )6789101112131415宽度优先搜索宽度优先搜索(新的节点被插入到栈OPEN的后部12345OPEN= (5,10,11,6,7)CLOSED=(1,2,3,4 )6789101112131415宽度优先搜索宽度优先搜索(新的节点被插入到栈OPEN的后部12345OPEN= (10,11,6,7,8,9)CLOSED=(1,2,3,4,5 )6789101112131415宽度优先搜索宽度优先搜索(新的节点被插入到栈OPEN的后部12345OPEN= (11,6,7,8,9,12,13)CLO
15、SED=(1,2,3,4,5,10 )6789101112131415深度优先搜索策略n新节点优先扩展, 直到达到一定的深度限制.若找不到目标或无法在扩展时,回溯到另一节点继续扩展.n特点: 需要深度限制, 需要回溯控制, 省空间n探索算法: n数据结构: OPEN表 : 后进先出队列后进先出队列,存放待扩展的节点. CLOSED表 : 存放已被扩展过的节点.n除扩展后的子节点应放入到OPEN表的首部以外,与宽度优先算法一样.深度优先算法框图深度优先算法框图v 算法开始开始把把S放入放入OPEN表表OPEN表为空表?表为空表?把第一个节点把第一个节点(n)从从OPEN表移至表移至CLOSED表
16、表是否有后继节点是否有后继节点为目标节点?为目标节点?扩展扩展n,把,把n的后继节点放入的后继节点放入OPEN表的表的前端前端,提供返回节点,提供返回节点n的指针的指针失败失败成功成功是是否否是是否否深度优先搜索算法nStep1: 把初始节点S0放入OPEN表中;nStep2: 若OPEN表为空,则搜索失败,退出.nStep3: 移出OPEN中第一个节点N放入CLOSED表 中, 并标以顺序号n;nStep4: 若目标节点Sg=N, 则搜索成功,结束.nStep5: 若N不可扩展, 则转Step2;nStep6: 扩展N, 将生成的一组子节点配上指向N的指针后, 放入放入OPEN表首部表首部,
17、 转 Step2;深度优先搜索深度优先搜索(新的节点被插入到栈OPEN的前部12345OPEN= (1)CLOSED=( )6789101112131415新的节点被插入到栈OPEN的前部12345OPEN = (2, 3)CLOSED=( 1 )6789101112131415 新的节点被插入到栈OPEN的前部12345OPEN = (4, 5, 3)CLOSED=( 1,2 )6789101112131415新的节点被插入到栈OPEN的前部12345CLOSED=( 1,2,4 )67OPEN = (6,7, 5, 3)89101112131415新的节点被插入到栈OPEN的前部12345
18、67891011CLOSED=( 1,2,4,6 )OPEN = (7, 5, 3)12131415新的节点被插入到栈OPEN的前部1234567891011CLOSED=( 1,2,4,6,7 )OPEN = (5, 3)12131415新的节点被插入到栈OPEN的前部1234567891011CLOSED=( 1,2,4, 5,6,7 )OPEN = (8,9,3)12131415新的节点被插入到栈OPEN的前部1234567891011CLOSED=( 1,2,4,5, 6,7 ,8)OPEN = (9, 3)12131415新的节点被插入到栈OPEN的前部123456789121011
19、131415CLOSED=( 1,2,4, 5,6,7, 8,9)OPEN = (3)新的节点被插入到栈OPEN的前部123456789121011131415CLOSED=( 1,2,4, 5,6,7,8,9,3)OPEN = (10,11)新的节点被插入到栈OPEN的前部1234567891011CLOSED=( 1,2,4, 5,6,7,8,9,3,10)12131415OPEN = (12,13,11)代价树搜索代价树:搜索树中每条连接弧线上的有关代价,表示时间、距离等花费。代价树搜索(等代价搜索) :是宽度优先搜索的一种推广,不是沿着等长度路径断层进行扩展,而是沿着等代价路径断层进行
20、扩展。 *若所有连接弧线具有相等代价,则简化为宽度优先搜索算法。算法使用符号n c(i,j):把从节点把从节点i i到其后继节点到其后继节点j j的连接弧线代价记为的连接弧线代价记为c(i,j)c(i,j)n g(i):把从起始节点把从起始节点S S到任一节点到任一节点i i的路径代价记为的路径代价记为g(i).g(i).n 在搜索树在搜索树(非循环路径)(非循环路径)上,假设上,假设g(i)g(i)是从起始节点是从起始节点S S到节点到节点i i的最少路径上的代价。的最少路径上的代价。n 等代价搜索方法以等代价搜索方法以g(i)g(i)的递增顺序扩展其节点。的递增顺序扩展其节点。开始把S放入
21、OPEN表OPEN表为空表?把具有最小g(i)值的节点i从OPEN表移至CLOSED表是否有后继节点为目标节点?失败成功等代价搜索算法框图等代价搜索算法框图是是否否是是否否令令g(s)=0S S是否目标节点是否目标节点?是是成功否否开始把S放入OPEN表OPEN表为空表?把具有最小g(i)值的节点i从OPEN表移至CLOSED表是否有后继节点为目标节点?失败成功是是是是否否令令g(s)=0S S是否目标节点是否目标节点?是是成功开始把S放入OPEN表OPEN表为空表?把具有最小g(i)值的节点i从OPEN表移至CLOSED表是否有后继节点为目标节点?失败成功是是是是否否令令g(s)=0S S是
22、否目标节点是否目标节点?是是成功扩展扩展i i,计算其后继节点,计算其后继节点j j的的g(j)g(j),并,并把后继节点放入把后继节点放入OPENOPEN表表开始把把S S放入放入OPENOPEN表表OPEN表为空表?把具有最小g(i)值的节点i从OPEN表移至CLOSED表是否有后继节点是否有后继节点为目标节点?为目标节点?失败成功是是是是否否令令g(s)=0S S是否目标节点是否目标节点?是是成功等代价搜索算法n(1) 把起始节点放到未扩展节点表把起始节点放到未扩展节点表OPEN中。如果此起始节点为一中。如果此起始节点为一目标节点,则求得一个解;否则令目标节点,则求得一个解;否则令g(S
23、)=0。n(2) 如果如果OPEN是个空表,则没有解而失败退出。是个空表,则没有解而失败退出。n(3) 从从OPEN 表中选择一个节点表中选择一个节点i,使其,使其g(i)为最小。如果有几个节)为最小。如果有几个节点都合格,那么就要选择一个目标节点作为节点点都合格,那么就要选择一个目标节点作为节点 i(要是有目标节点的(要是有目标节点的话);否则,就从中选一个作为节点话);否则,就从中选一个作为节点i。把节点。把节点i从从OPEN表移至扩展节点表移至扩展节点表表CLOSED中。中。n(4) 如果节点如果节点i为目标节点,则求得一个解。为目标节点,则求得一个解。n(5) 扩展节点扩展节点i。如果
24、没有后继节点,则转向第(。如果没有后继节点,则转向第(2)步。)步。n(6) 对于节点对于节点i的每个后继节点的每个后继节点j,计算,计算g(j)=g(i)+c(i,j),),并并把所有后继节点把所有后继节点j放进放进OPEN表。提供回到节点表。提供回到节点i的指针。的指针。n(7) 转向第(转向第(2)步。)步。沿着等长度沿着等长度路径断层进行扩展路径断层进行扩展等代价路径等代价路径断层进行扩展断层进行扩展比较宽度优先搜索与等代价搜索比较宽度优先搜索与等代价搜索搜索树(非循环路径)等代价搜索算法等代价搜索算法 在每一步, 选择具有最低累计权值的点进行扩展启发式搜索n盲目搜索的问题: “组合爆
25、炸”n利用问题的某些控制信息(如解的特征)来引导搜索.这种控制信息称为搜索的启发信息启发信息.n利用启发式信息定义节点的启发函数启发函数 h(n)n特点: 深度优先, 效率高, 无回溯, 但不能保证得到最佳解 。n探索算法:n全局择优搜索(最好优先搜索), 局部择优搜索n数据结构:OPEN表 、 CLOSED表 启发信息启发信息n启发式搜索就是利用启发性信息进行制导的搜索。n启发性信息就是有利于尽快找到问题之解的信息。n按其用途划分,启发性信息一般可分为以下三类: (1)用于扩展节点的选择,即用于决定应先扩展哪一个节点,以免盲目扩展。 (2)用于生成节点的选择,即用于决定应生成哪些后续节点,以
展开阅读全文