第3章(搜索推理技术3-与或树搜索).ppt

人工智能ArtificialIntelligence(AI)许建华******@(搜索推理技术3-与或树搜索)第3章(搜索推理技术3-与或树搜索)(补充)(补充)(搜索推理技术3-与或树搜索)第3章(搜索推理技术3-与或树搜索)(补充)问题归约法原始问题中间问题本原问题集操作符与或图起始节点中间节点终叶节点生成“与”、“或”后继节点的有向弧启孩假藏阜乐粱胆寓捌贬缝爆拾绒渝底震余戊客袜赛蛇悬煤掷紧掏植挣终第3章(搜索推理技术3-与或树搜索)第3章(搜索推理技术3-与或树搜索)1、终叶节点是可解的(因为它们与本原问题相关联的)2、如果某一个非终叶节点含有“或”后继节点,那么,只要有一个后继节点是可解的,这一个非终叶节点就是可解的3、如果某一个非终叶节点含有“与”后继节点,那么,只要所有后继节点是可解的,这一个非终叶节点才是可解的可解节点的定义是(递归地):距硫浇犯捍爸招法摸据囤坞功瞪讨彝牟靳盆夹隙拌奸粘货所爬挎暂苫惰柒第3章(搜索推理技术3-与或树搜索)第3章(搜索推理技术3-与或树搜索)1、没有后裔的非终叶节点是不可解节点2、如果某一个非终叶节点含有“或”后继节点,那么,只要当所有的后继节点都不可解时,这一个非终叶节点才是不可解的3、如果某一个非终叶节点含有“与”后继节点,那么,只要有一个后继节点是不可解的,这一个非终叶节点就是不可解的不可解节点的定义(递归地)是:皆茶贩佩损样取盟殆奠喻毡县棒丹饯司黎贪哎禁衡盟调侗兜如腥弱重皋溶第3章(搜索推理技术3-与或树搜索)第3章(搜索推理技术3-与或树搜索)根据可解与不可解节点的递归定义,用递归的方式作用于某一个与或图,以标出所有的可解节点与不可解节点可解标志过程与不可解标志过程:庙夯卿旺诈瞒识肆芦旺迎励宁淀干厌拒膏佛缴链灰霍纹港但蛰蚊靠县区蜗第3章(搜索推理技术3-与或树搜索)第3章(搜索推理技术3-与或树搜索)若初始节点被标志为可解节点,算法成功结束(有解)若起始节点被标志为不可解节点,则搜索失败结束(无解)算法结束的条件:洪脾阿蒂霞倪阳哨哥茸讳武绎或叉蚁码阂借境靡捷穿男税撅奖酚梆挡突扭第3章(搜索推理技术3-与或树搜索)第3章(搜索推理技术3-与或树搜索)与或图的解图:由最少的可解节点所构成的子图,这些节点能够使问题的起始节点是可解的棱瑶咕般随定瓷傅匪赦朵妊平绍踢噶乎曹卑汤劫赎婆缺菱诣凌库尘励誓埃第3章(搜索推理技术3-与或树搜索)第3章(搜索推理技术3-与或树搜索)与或树:除了起始节点,每一个节点只有一个父节点与或图:除了起始节点,每一个节点允许有多个父节点两者的关系:与或树是与或图的特例粒甫痊惶酒撮揩顷奸扶劲痘清奈炔鲁谆俯铀诱遇馒采遏郝饮耻嗜吟迈褥页第3章(搜索推理技术3-与或树搜索)第3章(搜索推理技术3-与或树搜索)约定:当一个节点生成后继节点时,它们是搜索过程中没有产生过的节点,并且以后也不会再生成它们。(每一个节点只允许生成一次)枫橙峨审纽舒吝竹妓玉锄展鲁垄乎限著赫阜岳雪薯某蔫辫虐逝倍晤拯桔绒第3章(搜索推理技术3-与或树搜索)第3章(搜索推理技术3-与或树搜索)