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

人工智能第章确定性推理与或树搜索第第3章章 确定性推理确定性推理 3.1 图的搜索策略图的搜索策略3.2 盲目搜索盲目搜索3.3 启发式搜索启发式搜索3.4 与或树搜索补充与或树搜索补充3.5 博弈树搜索补充博弈树搜索补充3.6 消解原理消解原理3.4 与或树搜索补充与或树搜索补充 问题归约法问题归约法原始问题原始问题中间问题中间问题 本原问题集本原问题集 操作符操作符与或图与或图起始节点起始节点中间节点中间节点终叶节点终叶节点生生成成“与与、“或或后后继继节点的有向弧节点的有向弧 1、终终叶叶节节点点是是可可解解的的因因为为它它们们与与本本原原问问题题相相关关联的联的2、假假如如某某一一个个非非终终叶叶节节点点含含有有“或或后后继继节节点点，则则，只只要要有有一一个个后后继继节节点点是是可可解解的的，这这一一个个非非终终叶叶节点就是可解的节点就是可解的3、假假如如某某一一个个非非终终叶叶节节点点含含有有“与与后后继继节节点点，则则，只只要要所所有有后后继继节节点点是是可可解解的的，这这一一个个非非终终叶叶节节点才是可解的点才是可解的可解节点的定义是递归地：可解节点的定义是递归地：1、没有后裔的非终叶节点是不可解节点、没有后裔的非终叶节点是不可解节点2、假假如如某某一一个个非非终终叶叶节节点点含含有有“或或后后继继节节点点，则则，只只要要当当所所有有的的后后继继节节点点都都不不可可解解时时，这这一一个个非终叶节点才是不可解的非终叶节点才是不可解的3、假假如如某某一一个个非非终终叶叶节节点点含含有有“与与后后继继节节点点，则则，只只要要有有一一个个后后继继节节点点是是不不可可解解的的，这这一一个个非非终叶节点就是不可解的终叶节点就是不可解的不可解节点的定义递归地是：不可解节点的定义递归地是：根据可解与不可解节点的递归定义，用递归的方根据可解与不可解节点的递归定义，用递归的方式作用于某一个与或图，以标出所有的可解节点式作用于某一个与或图，以标出所有的可解节点与不可解节点与不可解节点可解标志过程可解标志过程与与不可解标志过程不可解标志过程:假假设设初初始始节节点点被被标标志志为为可可解解节节点点，算算法法成功完毕有解成功完毕有解假假设设起起始始节节点点被被标标志志为为不不可可解解节节点点，则则搜索失败完毕无解搜索失败完毕无解算法完毕的条件：算法完毕的条件：与或图的解图：与或图的解图：由最少的可解节点所构成的子图，这些节由最少的可解节点所构成的子图，这些节点可以使问题的起始节点是可解的点可以使问题的起始节点是可解的与或树与或树：除了起始节点，每一个节点只有一：除了起始节点，每一个节点只有一个父节点个父节点与或图与或图：除了起始节点，每一个节点允许有除了起始节点，每一个节点允许有多个父节点多个父节点两者的关系两者的关系：与或树是与或图的特例：与或树是与或图的特例约定：当一个节点生成后继节点时，约定：当一个节点生成后继节点时，它们是搜索过程中没有产生过的节点，它们是搜索过程中没有产生过的节点，并且以后也不会再生成它们。每一并且以后也不会再生成它们。每一个节点只允许生成一次个节点只允许生成一次3.4.1 宽度优先搜索宽度优先搜索 两个根本符号：两个根本符号：OPEN表表：存存放放待待扩扩展展的的节节点点，此此时时是是队队列列CLOSED表：存放已扩展的节点表：存放已扩展的节点1、起始节点、起始节点 S 送送 OPEN 表表2、假设、假设 S 为叶节点，则成功完毕，否则，继续为叶节点，则成功完毕，否则，继续3、取取出出 OPEN 表表的的第第一一个个节节点点记记作作 n，并并送送 到到CLOSED 表表与或树宽度优先搜索算法与或树宽度优先搜索算法：4、扩扩展展节节点点 n，生生成成其其全全部部后后继继节节点点，送送OPEN表末端，并设置指向表末端，并设置指向 n 的指针的指针说明说明：此时可能出现三种情况：此时可能出现三种情况节点节点 n 无后继节点无后继节点节点节点 n 有后继节点、并有叶节点有后继节点、并有叶节点节点节点 n 有后继节点、但无叶节点有后继节点、但无叶节点5、假假设设 n 无无后后继继节节点点，标标志志 n 为为不不可可解解，并并转转910、11；假假设设后后继继节节点点中中有有叶叶节节点点，则则标标志志这这些些叶叶节节点点为为可可解解节节点点，并并继继续续6、7、8；否则转否则转36、实行可解标志过程、实行可解标志过程7、假假设设起起始始节节点点S标标志志为为可可解解，则则找找到到解解而而完完毕，否则继续毕，否则继续8、从从OPEN表表中中删删去去含含有有可可解解先先辈辈节节点点的的节节点点，并转并转39、实行不可解标志过程、实行不可解标志过程10、假假设设起起始始节节点点S标标志志为为不不可可解解，则则失失败败而而完完毕毕，否则继续否则继续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步：步：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 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,11,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、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表，不作任何处理表，不作任何处理删除删除XXX3、从、从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,t3,t4,13 CLOSED=1,2,3,4,5,6,7,8,9,t1,10 搜索过程演示搜索过程演示123457689BCt1101112At2t3t413“与或树的深度：与或树的深度：1 1、规定起始节点深度为、规定起始节点深度为0 02 2、其它节点深度等于其父节点的深度加、其它节点深度等于其父节点的深度加1 1解的性质：解的性质：假如有解，宽度优先搜索可以保证求假如有解，宽度优先搜索可以保证求得一棵解树，它的最深的叶节点具有得一棵解树，它的最深的叶节点具有最小深度最小深度3.4.2 深度优先搜索深度优先搜索 在与或树的深度优先搜索中，同样要设置一个在与或树的深度优先搜索中，同样要设置一个深深度界限度界限对于等于深度界限的节点，不再扩展，并将其标对于等于深度界限的节点，不再扩展，并将其标志为不可解节点，并在搜索过程中实行不可解标志为不可解节点，并在搜索过程中实行不可解标志过程志过程1、起始节点、起始节点S送送OPEN表表2、假设、假设S为叶节点，则成功完毕，否则继续为叶节点，则成功完毕，否则继续3、取取出出OPEN表表第第一一个个节节点点记记作作n)，送送到到CLOSED表表与或树深度优先搜索算法与或树深度优先搜索算法：4、假设节点、假设节点 n 的深度等于深度界限，则将的深度等于深度界限，则将 n 标志标志为不可解节点，并转为不可解节点，并转10；否则继续；否则继续5、扩展节点、扩展节点 n，生成全部后继节点，置于，生成全部后继节点，置于 OPEN表前面，并设置指向表前面，并设置指向 n 的指针的指针6、分三种情况、分三种情况假假如如 n 无无后后继继节节点点，则则标标志志为为不不可可解解节节点点，并并转转l0，否则继续，否则继续假假设设有有后后继继节节点点为为叶叶节节点点，则则将将这这些些叶叶节节点点标标志志为可解节点，并继续；否则转为可解节点，并继续；否则转37、实行可解标志过程、实行可解标志过程8、假假设设起起始始节节点点为为可可解解节节点点，则则算算法法成成功功完完毕毕；否则，继续下一步否则，继续下一步9、从从OPEN表表中中删删除除含含有有可可解解先先辈辈节节点点的的节节点点，并转并转310、实行不可解标志过程、实行不可解标志过程11、假假设设起起始始节节点点为为不不可可解解，则则失失败败完完毕毕，否否则则，继续下一步继续下一步12、从、从OPEN表中删去含有不可解先辈节点的节点表中删去含有不可解先辈节点的节点13、转、转31、第第4步步要要判判断断从从OPEN表表取取出出来来的的节节点点的的深深度度。假如等于深度界限，认定它为不可解节点假如等于深度界限，认定它为不可解节点2、第第5步步将将扩扩展展出出来来的的节节点点放放到到OPEN的的前前端端，即即OPEN是堆栈是堆栈与宽度优先算法相比，深度优先算法的特殊之处与宽度优先算法相比，深度优先算法的特殊之处：注意注意由于深度限制，深度优先搜索算法有可能找不由于深度限制，深度优先搜索算法有可能找不到解到解例：例：注注：后生成的节点画在左边：后生成的节点画在左边162A354BttC7t8tt深度界限为深度界限为4课堂练习课堂练习：用宽度和深度优先搜索算法找出解树：用宽度和深度优先搜索算法找出解树提提示示：对对于于宽宽度度优优先先搜搜索索，先先生生成成的的节节点点画画在在左左；对于深度优先搜索，后生成的节点画在左对于深度优先搜索，后生成的节点画在左说明说明：先扩展的节点画在左边先扩展的节点画在左边1234567t1t2t3 与或树的宽度与或树的宽度优先搜索优先搜索说明说明：后扩展的节点画在左边后扩展的节点画在左边12354XXt5t6深度界限为深度界限为4与或树的深度与或树的深度优先搜索优先搜索例例：某某一一个个问问题题可可能能的的解解决决方方案案可可以以表表示示成成以以下下一一棵棵与与或或树树，请请用用宽宽度度和和深深度度优优先先搜搜索索算算法法找找出出各各自自的的解解决决方方案案？可解可解不可解不可解与与或或树树宽宽度度优优先先搜索过程搜索过程左先右后左先右后XXXX与与或或树树深深度度优优先先搜索过程搜索过程左先右后左先右后XXXX其他搜索算法：其他搜索算法：与或树的代价优先搜索和代价最小，最大代与或树的代价优先搜索和代价最小，最大代价最小价最小 与或图的启发搜索算法与或图的启发搜索算法AO*要掌握的算法要掌握的算法：与或树的宽度优先搜索算法与或树的宽度优先搜索算法与或树的深度优先搜索算法与或树的深度优先搜索算法