资源描述：
《(搜索推理技术3-与或树搜索)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、人工智能ArtificialIntelligence(AI)许建华xujianhua@njnu.edu.cn南京师范大学计算机科学与技术学院2010年秋季第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表的第一个节点（记作n），并送到CLOSE
4、D表与或树宽度优先搜索算法：4、扩展节点n，生成其全部后继节点，送OPEN表末端，并设置指向n的指针说明：此时可能出现三种情况节点n无后继节点节点n有后继节点、并有叶节点节点n有后继节点、但无叶节点5、若n无后继节点，标志n为不可解，并转9（10、11）；若后继节点中有叶节点，则标志这些叶节点为可解节点，并继续（6、7、8）；否则转36、实行可解标志过程7、若起始节点S标志为可解，则找到解而结束，否则继续8、从OPEN表中删去含有可解先辈节点的节点，并转39、实行不可解标志过程10、若起始节点S标志为不可解，则失败而结束，否则继续11、从OPEN表中删去含有不可解先辈节点的节点12、转
5、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、扩展节
6、点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
7、、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，生成后继节
