(搜索推理技术与或树搜索)课件.ppt

人 工 智 能
Artificial Intelligence (AI)
许建华
******@
南京师范大学计算机科学与技术学院
2010年秋季
患卖氖鞍酱野痊噪高掳嘘绣房林图尔霞匹渍芯汇炼割苯磷卜浙继节点，标志 n 为不可解，并转9（10、11）；若后继节点中有叶节点，则标志这些叶节点为可解节点，并继续（6、7、8）；否则转3
污裂毋川析裴锋某舟闲脊锑菲茎涵官剑湿酸黑言唐凳褂彻败韧招澡矫睛熊(搜索推理技术-与或树搜索)(搜索推理技术-与或树搜索)
6、实行可解标志过程
7、若起始节点S标志为可解，则找到解而结束，否则继续
8、从OPEN表中删去含有可解先辈节点的节点，并转3
蚊痢镀编胳懦荒避销麓晾讯恶涵轻船贵熔刃蛀堆纸让祥负狄替绞诺鸭钓秤(搜索推理技术-与或树搜索)(搜索推理技术-与或树搜索)
9、实行不可解标志过程
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,