人工智能 第3章(确定性推理3-与或树搜索).ppt

上传人:小飞机 文档编号:5194158 上传时间:2023-06-13 格式:PPT 页数:57 大小:959.50KB
返回 下载 相关 举报
人工智能 第3章(确定性推理3-与或树搜索).ppt_第1页
第1页 / 共57页
人工智能 第3章(确定性推理3-与或树搜索).ppt_第2页
第2页 / 共57页
人工智能 第3章(确定性推理3-与或树搜索).ppt_第3页
第3页 / 共57页
人工智能 第3章(确定性推理3-与或树搜索).ppt_第4页
第4页 / 共57页
人工智能 第3章(确定性推理3-与或树搜索).ppt_第5页
第5页 / 共57页
点击查看更多>>
资源描述

《人工智能 第3章(确定性推理3-与或树搜索).ppt》由会员分享,可在线阅读,更多相关《人工智能 第3章(确定性推理3-与或树搜索).ppt(57页珍藏版)》请在三一办公上搜索。

1、人 工 智 能Artificial Intelligence(AI),许建华南京师范大学计算机科学与技术学院2011年秋季,第3章 确定性推理,3.1 图的搜索策略3.2 盲目搜索3.3 启发式搜索3.4 与或树搜索(补充)3.5 博弈树搜索(补充)3.6 消解原理,3.4 与或树搜索(补充),问题归约法原始问题中间问题 本原问题集 操作符,与或图起始节点中间节点终叶节点生成“与”、“或”后继节点的有向弧,1、终叶节点是可解的(因为它们与本原问题相关联的)2、如果某一个非终叶节点含有“或”后继节点,那么,只要有一个后继节点是可解的,这一个非终叶节点就是可解的3、如果某一个非终叶节点含有“与”后

2、继节点,那么,只要所有后继节点是可解的,这一个非终叶节点才是可解的,可解节点的定义是(递归地):,1、没有后裔的非终叶节点是不可解节点2、如果某一个非终叶节点含有“或”后继节点,那么,只要当所有的后继节点都不可解时,这一个非终叶节点才是不可解的3、如果某一个非终叶节点含有“与”后继节点,那么,只要有一个后继节点是不可解的,这一个非终叶节点就是不可解的,不可解节点的定义(递归地)是:,根据可解与不可解节点的递归定义,用递归的方式作用于某一个与或图,以标出所有的可解节点与不可解节点,可解标志过程与不可解标志过程:,若初始节点被标志为可解节点,算法成功结束(有解)若起始节点被标志为不可解节点,则搜索

3、失败结束(无解),算法结束的条件:,与或图的解图:由最少的可解节点所构成的子图,这些节点能够使问题的起始节点是可解的,与或树:除了起始节点,每一个节点只有一个父节点与或图:除了起始节点,每一个节点允许有多个父节点两者的关系:与或树是与或图的特例,约定:当一个节点生成后继节点时,它们是搜索过程中没有产生过的节点,并且以后也不会再生成它们。(每一个节点只允许生成一次),3.4.1 宽度优先搜索,两个基本符号:OPEN表:存放待扩展的节点,此时是队列CLOSED表:存放已扩展的节点,1、起始节点 S 送 OPEN 表2、若 S 为叶节点,则成功结束,否则,继续3、取出 OPEN 表的第一个节点(记作

4、 n),并送 到CLOSED 表,与或树宽度优先搜索算法:,4、扩展节点 n,生成其全部后继节点,送OPEN表末端,并设置指向 n 的指针,说明:此时可能出现三种情况节点 n 无后继节点节点 n 有后继节点、并有叶节点节点 n 有后继节点、但无叶节点,5、若 n 无后继节点,标志 n 为不可解,并转9(10、11);若后继节点中有叶节点,则标志这些叶节点为可解节点,并继续(6、7、8);否则转3,6、实行可解标志过程7、若起始节点S标志为可解,则找到解而结束,否则继续8、从OPEN表中删去含有可解先辈节点的节点,并转3,9、实行不可解标志过程10、若起始节点S标志为不可解,则失败而结束,否则继

5、续11、从OPEN表中删去含有不可解先辈节点的节点12、转3,例,说明:先扩展出来的节点画在左边,算法的运行过程,初始化:节点 1 送OPEN表,且不为叶节点,OPEN=1 CLOSED=,3、从OPEN表中取出节点1,并送到CLOSED表4、扩展节点1,生成后继节点2、3,并送到OPEN表的末端5、无叶节点,转到3步,OPEN=2,3 CLOSED=1,第一大循环(算法的3、4、5步):,3、从OPEN表中取出节点2,并送到CLOSED表4、扩展节点2,生成后继节点4、5,并送到OPEN表的末端5、无叶节点,转到3步,OPEN=3,4,5 CLOSED=1,2,第二大循环(3、4、5步):,

6、3、从OPEN表中取出节点3,并送到CLOSED表4、扩展节点3,生成后继节点6、7,并送到OPEN表的末端5、无叶节点,转到3步,OPEN=4,5,6,7 CLOSED=1,2,3,第三大循环(3、4、5步):,3、从OPEN表中取出节点4,并送到CLOSED表4、扩展节点4,生成后继节点8、9,并送到OPEN表的末端5、无叶节点,转到3步,OPEN=5,6,7,8,9 CLOSED=1,2,3,4,第四大循环(3、4、5步):,3、从OPEN表中取出节点5,并送到CLOSED表4、扩展节点5,生成后继节点B、C,并送到OPEN表的末端5、无叶节点,转到3步,OPEN=6,7,8,9,B,C

7、 CLOSED=1,2,3,4,5,第五大循环(3、4、5步):,3、从OPEN表中取出节点6,并送到CLOSED表4、扩展节点6,生成后继节点t1、10,并送到OPEN表的末端5、有叶节点6、实现可解过程(无法判断节点6是否可解)7、无法判断起始节点是否可解8、OPEN表中无节点可以删除(转到3),第六大循环(3、4、5、6、7、8步):,OPEN=7,8,9,B,C,t1,10 CLOSED=1,2,3,4,5,6,3、从OPEN表中取出节点7,并送到CLOSED表4、扩展节点7,生成后继节点11、12,并送到OPEN表的末端5、无叶节点,转到3步,OPEN=8,9,B,C,t1,10,1

8、1,12 CLOSED=1,2,3,4,5,6,7,第七大循环(3、4、5步):,3、从OPEN表中取出节点8,并送到CLOSED表4、扩展节点8,生成后继节点A,并送到OPEN表的末端5、无叶节点,转到3步,OPEN=9,B,C,t1,10,11,12,ACLOSED=1,2,3,4,5,6,7,8,第八大循环(3、4、5步):,3、从OPEN表中取出节点9,并送到CLOSED表4、扩展节点9,生成后继节点 t2、t3,并送到OPEN表的末端5、有叶节点6、实现可解标志过程(可以判断节点9、4、2可解)7、无判断起始节点1可解8、从OPEN中删除含有可解先辈节点的节点,第九大循环(3、4、5

9、、6、7、8步):,OPEN=B,C,t1,10,11,12,A,t2,t3 CLOSED=1,2,3,4,5,6,7,8,9,OPEN=t1,10,11,12,t2,t3CLOSED=1,2,3,4,5,6,7,8,9,说明:对于OPEN表中的叶节点直接移到CLOSED表,不作任何处理,删除,X,X,X,3、从OPEN表中取出节点10,并送到CLOSED表4、扩展节点10,生成后继节点 t4、13,并送到OPEN表的末端5、有叶节点6、实现可解标志过程(可以判断节点10、6、3可解)7、可以判断起始节点1可解。算法结束,第十大循环(3、4、5、6、7步):,OPEN=11,12,A,t2,t

10、3,t4,13 CLOSED=1,2,3,4,5,6,7,8,9,t1,10,搜索过程演示,1,2,3,4,5,7,6,8,9,B,C,t1,10,11,12,A,t2,t3,t4,13,“与或树”的深度:1、规定起始节点深度为02、其它节点深度等于其父节点的深度加1,解的性质:如果有解,宽度优先搜索能够保证求得一棵解树,它的最深的叶节点具有最小深度,3.4.2 深度优先搜索,在与或树的深度优先搜索中,同样要设置一个深度界限对于等于深度界限的节点,不再扩展,并将其标志为不可解节点,并在搜索过程中实行不可解标志过程,1、起始节点S送OPEN表2、若S为叶节点,则成功结束,否则继续3、取出OPEN

11、表第一个节点(记作n),送到CLOSED表,与或树深度优先搜索算法:,4、若节点 n 的深度等于深度界限,则将 n 标志为不可解节点,并转10;否则继续5、扩展节点 n,生成全部后继节点,置于 OPEN表前面,并设置指向 n 的指针,6、(分三种情况)如果 n 无后继节点,则标志为不可解节点,并转l0,否则继续若有后继节点为叶节点,则将这些叶节点标志为可解节点,并继续;否则转3,7、实行可解标志过程8、若起始节点为可解节点,则算法成功结束;否则,继续下一步9、从OPEN表中删除含有可解先辈节点的节点,并转3,10、实行不可解标志过程11、若起始节点为不可解,则失败结束,否则,继续下一步12、从

12、OPEN表中删去含有不可解先辈节点的节点13、转3,1、第4步要判断从OPEN表取出来的节点的深度。如果等于深度界限,认定它为不可解节点2、第5步将扩展出来的节点放到OPEN的前端,即OPEN是堆栈,与宽度优先算法相比,深度优先算法的特殊之处:,注意由于深度限制,深度优先搜索算法有可能找不到解,例:,注:后生成的节点画在左边,1,6,2,A,3,5,4,B,t,t,C,7,t,8,t,t,深度界限为4,课堂练习:用宽度和深度优先搜索算法找出解树,提示:对于宽度优先搜索,先生成的节点画在左;对于深度优先搜索,后生成的节点画在左,说明:先扩展的节点画在左边,1,2,3,4,5,6,7,t1,t2,t3,与或树的宽度优先搜索,说明:后扩展的节点画在左边,1,2,3,5,4,X,X,t5,t6,深度界限为4,与或树的深度优先搜索,例:某一个问题可能的解决方案可以表示成下列一棵与或树,请用宽度和深度优先搜索算法找出各自的解决方案?,可解,不可解,与或树宽度优先搜索过程(左先右后),X,X,X,X,与或树深度优先搜索过程(左先右后),X,X,X,X,其他搜索算法:与或树的代价优先搜索(和代价最小,最大代价最小)与或图的启发搜索算法AO*,要掌握的算法:与或树的宽度优先搜索算法与或树的深度优先搜索算法,

展开阅读全文
相关资源
猜你喜欢
相关搜索
资源标签

当前位置:首页 > 生活休闲 > 在线阅读


备案号:宁ICP备20000045号-2

经营许可证:宁B2-20210002

宁公网安备 64010402000987号