第二章 与或图搜索问题

《第二章 与或图搜索问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1第二章与或图搜索问题目标目标初始节点sabc2第二章与或图搜索问题与或树是用于表示问题及其求解过程的又一种形式化方法。对于一个复杂问题，直接求解往往比较困难，因此通过下述方法进行简化：分解：把一个复杂问题简化为若干简单的子问题，重复此过程，直到不需要再分解或者不能再分解为止。若每个子问题都可求解，则原问题可求解。因此下图称为“与”树。PP3P2P13第二章与或图搜索问题等价变换：对于一个复杂问题，除了可用“分解”方法进行求解外，还可利用同构或同态的等价变换，把它变换为若干个较为容易求解的新问题。若新问题中有一个

2、可求解，则就得到了原问题的解。因此下图称为“或”树PP3P2P14第二章与或图搜索问题与或树PP3P2P1P12P11P32P33P3152.1基本概念本原问题：不能再分解或变换，而且可以直接求解的子问题。端节点与终止节点：没有子节点的节点称为端节点；本原问题所对应的节点称为终止节点。显然，终止节点一定是端节点，但端节点不一定是终止节点。可解节点：满足下列条件之一者，称为可解节点：1.它是一个终止节点；2.它是一个“或”节点，且其子节点中至少有一个是可解节点；3.它是一个“与”节点，且其子节点中全部都是可解节点。

3、62.1基本概念不可解节点：关于可解节点的三个条件全部不满足的节点称为不可解节点。解树：由可解节点构成，并且由这些节点可推出初始节点（它对应于原始问题）为可解节点的子树称为解树。7解树PtttPttt8与或树的广度优先搜索1.把初始节点S0放入OPEN表。2.把OPEN表中的第一个节点（记为节点n)取出放入CLOSED表。3.如果节点n可扩展，则作下列工作：3.1扩展节点n，将其子节点放入OPEN表的尾部，并为每个子节点配置指向父节点的指针，以备标识过程使用。3.2考察这些子节点中有否终止节点。若有，则标识这些终

4、止节点为可解节点，并应用可解标识过程对其父节点、祖父节点等先辈节点中的可解节点进行标识。如果初始节点S0也被标识为可解节点，就得到了解树，搜索成果，退出搜索过程；如果不能确定S0为可解节点，则从OPEN表中删去具有可解先辈的节点。3.3转第2步。9与或树的广度优先搜索（续）4.如果节点n不可扩展，则作下列工作。4.1.标识节点n为不可解节点。4.2.应用不可解标识过程对节点n的先辈节点中不可解的节点进行标识，如果初始节点S0也被标识为不可解节点，则搜索失败，表明原问题无解，退出搜索过程；如果不能确定S0为不可解节

5、点，则从OPEN表中删去具有不可解先辈的节点。4.3转第2步。10与或树的广度优先搜索：示例2134t1ABt2t4t3511与或树的广度优先搜索：示例(1).首先扩展1号节点，得到2号节点和3号节点，由于这两个子节点均不是终止节点，所以接着扩展2号节点。此时OPEN表中只剩下3号节点。(2).扩展2号节点后，得到4号节点和t1节点。此时OPEN表中的节点有：3，4,t1。由于t1是终止节点，则标识它为可解节点，并应用可解标识过程，对其先辈节点中的可解节点进行标识。在此例中，因为t1的父节点是一个“与”节点，因此

6、仅有t1可解尚不能确定2号节点是否为可解节点。所以继续搜索。下一步扩展的节点是3号节点。12示例(续)扩展3号节点得到5号节点与B节点，两者都不是终止节点，所以接着扩展4号节点。扩展4号节点后得到节点A和t2。由于t2是终止节点，所以标识它为可解节点，并用可解标识过程标识出4、2均为可解节点，但1号节点目前还不能确定它是否是可解节点。此时5号节点是OPEN标中的第一个待考察的节点，所以下一步扩展5号节点。扩展5号节点，得到t3、t4，由于t3、t4均为终止节点，所以被标识为可解节点，通过应用可解标识过程可得到5、

7、3、1号节点均为可解节点。13与或树的有界深度优先搜索1.把初始节点S0放入OPEN表。2.把OPEN表中的第一个节点（记为节点n)取出放入CLOSED表。3.如果节点n的深度大于等于深度界限，则转第5步的5.1步。4.如果节点n可扩展，则作下列工作：4.1扩展节点n，将其子节点放入OPEN表的首部，并为每个子节点配置指向父节点的指针，以备标识过程使用。4.2考察这些子节点中有否终止节点。若有，则标识这些终止节点为可解节点，并应用可解标识过程对其父节点、祖父节点等先辈节点中的可解节点进行标识。如果初始节点S0也被

8、标识为可解节点，就得到了解树，搜索成果，退出搜索过程；如果不能确定S0为可解节点，则从OPEN表中删去具有可解先辈的节点。4.3转第2步。14与或树的有界深度优先搜索（续）5.如果节点n不可扩展，则作下列工作。5.1.标识节点n为不可解节点。5.2.应用不可解标识过程对节点n的先辈节点中不可解的节点进行标识，如果初始节点S0也被标识为不可解节点，则搜索失败，表明原问题无解