或树搜索2盲目搜索.ppt

与或树盲目搜索一般搜索过程广度优先搜索深度优先搜索边扩展节点边确定初始节点是否可解。一旦能够确定初始节点的可解性,则搜索停止,并根据返回指针从搜索树中得到一个解树。?一般搜索过程??;(生成若干子节点);;,转步2;反复对其中的可解节点进行标记和不可解节点进行标记。–如果初始节点被标记为可解节点,则搜索成功,结束。–如果初始节点S0被标记为不可解节点,则搜索失败,退出。?广度优先搜索把初始节点S0放入OPEN表;移出为OPEN表的第一个节点放入CLOSED表,并冠以序号N;若节点N可扩展,则做下列工作:(1)扩展N,将其子节点配上指向父节点的指针后放入OPEN表的尾部;(2)考察这些子节点中是否有终止节点。若有,则标记它们为可解节点,并将它们放入CLOSED表,由它们的可解返回推断其先辈节点的可解性,并对其中的可解节点进行标记。如果初始节点也被标记为可解节点,则搜索成功,结束。如果初始节点不能被标记为可解节点,则删去OPEN表中那些具有可解先辈的节点(因为其先辈节点已经可解,故已无再考察节点的必要);(3)转步2;若N不可扩展,则做下列工作:(1)标记N为不可解节点,(2)然后由它的不可解返回推断其先辈节点的不可解性,并对其中的不可解节点进行标记。如果初始节点S0也被标记为不可解节点,则搜索失败,退出。如果初始节点不能被标记为不可解节点,删去OPEN表中那些具有不可解先辈的节点(因为其先辈节点已不可解,故已无再考察这些节点的必要),(3)转步2;例1:设有与或树如图,其中1号节点为初始节点,t1,t2,t3,t4均为终止节点,A和B是不可解的端节点。)扩展节点1,得到2 和3号节点,依次放到OPEN 表尾部;2和3为非终止节点,接着扩展2号节点;(略述建立指针,以下同)2)扩展2号节点,得到4号和t1节点。t1为终止节点,则为可解节点,判断其先辈节点的可解性(先辈节点的可解性未知);3)扩展3号节点,得5和B节点,两者为非终止节点,继续扩展4号节点;4)4号扩展后得到A和t2。t2为终止节点,标记为可解节点,这时其先辈节点4和2也为可解节点,因4节点可解,故在OPEN表中删去A;5)扩展5号节点,得到t3和t4。由于t3和t4都为终止节点,故可推断出5,3都为可解节点。故初始节点1为可解节点。搜索成功,结束。132B5t1t4t3t2A 41325t1t4t3t2 4?深度优先搜索把初始节点S0放入OPEN表;移出为OPEN表的第一个节点放入CLOSED表,并冠以序号N;若节点N可扩展,则做下列工作:(1)扩展N,将其子节点配上指向父节点的指针后放入OPEN表的首部;(2)考察它些子节点中是否有终止节点。若有,则标记它们为可解节点,并将它们也放入CLOSED表,然后由它们的可解返回推断其先辈节点的可解性,并对其中的可解节点进行标记。如果初始节点也被标记为可解节点,则搜索成功,结束。如果初始节点不能被标记为可解节点,删去OPEN表中那些具有可解先辈的节点(因为其先辈节点已经可解,故已无再考察节点的必要), (3)转步2;若N不可扩展,则做下列工作:(1)标记N为不可解节点,(2)然后由它的不可解返回推断其先辈节点的可解性,并对其中的不可解节点进行标记。如果初始节点S0也被标记为不可解节点,则搜索失败,退出。如果初始节点不能被标记为不可解节点,删去OPEN表中那些具有不可解先辈的节点(因为其先辈节点已不可解,故已无再考察这些节点的必要),(3)转步2;如果>=深度界限,则转向步4(1)深度+1例2:设有与或树如图,其中1号节点为初始节点,t1,t2,t3,t4均为终止节点,A和B是不可解的端节点。)扩展节点1,得到2 和3号节点,依次放到OPEN 表首部;2和3为非终止节点,接着扩展2号节点;2)扩展2号节点,得到4号和t1节点。t1为终止节点,则为可解节点,判断其先辈节点的可解性(先辈节点的可解性未知);3)扩展4号节点,4号扩展后得到A和t2。t2为终止节点,标记为可解节点,这时其先辈节点4和2也为可解节点,因4节点可解,故在OPEN表中删去A;4)扩展3号节点,得5和B节点,两者为非终止节点;5)扩展5号节点,得到t3和t4。由于t3和t4都为终止节点,故可推断出5,3都为可解节点。故初始节点1为可解节点。搜索成功,结束。132B5t1t4t3t2A 41325t1t4t3t2 4小结?与或树–把待解的原问题作为初始与或树节点,把由原问题经一系列分解或变换而得到的可解的简单问题作为目标节点。–解树是由可解