资源描述：
《《与或图搜索问题》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章与或图搜索问题目标目标初始节点sabcEvaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.1基本思想当一问题较复杂时，可通过分解或变换，将其转化为一系列较简单的子问题，然后通过对这些子问题的求解来实现对原问题的求解。分解如果一个问题P可以归约为一组子问题P1,P2,…,Pn，并且只有当所有子问题Pi都有解时原问题P才有解，任何一个子问题Pi无解都会导致原问题P无解，则称此种归约为问题的分解。即分解所得到的子问题的“与”与原问题P等
2、价。等价变换如果一个问题P可以归约为一组子问题P1,P2,…,Pn，并且子问题Pi中只要有一个有解则原问题P就有解，只有当所有子问题Pi都无解时原问题P才无解，称此种归约为问题的等价变换，简称变换。即变换所得到的子问题的“或”与原问题P等价。2.1问题归约法Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.2PP1P2P3与树P1P2P3或树PPP1P2P3P12P12P31P32P33与/或树(1)与树分解(2)或树等价变换(3)与
3、/或树2.1问题归约法2.问题的与/或树表示Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.3(4)端节点与终止节点在与/或树中，没有子节点的节点称为端节点；本原问题所对应的节点称为终止节点。可见，终止节点一定是端节点，但端节点却不一定是终止节点。(5)可解节点与不可解节点在与/或树中，满足以下三个条件之一的节点为可解节点：①任何终止节点都是可解节点。②对“或”节点，当其子节点中至少有一个为可解节点时，则该或节点就是可解节点。③对“
4、与”节点，只有当其子节点全部为可解节点时，该与节点才是可解节点。同样，可用类似的方法定义不可解节点：①不为终止节点的端节点是不可解节点。②对“或”节点，若其全部子节点都为不可解节点，则该或节点是不可解节点。③对“与”节点，只要其子节点中有一个为不可解节点，则该与节点是不可解节点。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.4Pttt解树(6)解树由可解节点构成，并且由这些可解节点可以推出初始节点（它对应着原始问题）为可解节点的子
5、树为解树。在解树中一定包含初始节点。例如，右图给出的与或树中，用红线表示的子树是一个解树。在该图中，节点P为原始问题节点，用t标出的节点是终止节点。根据可解节点的定义，很容易推出原始问题P为可解节点。问题归约求解过程就实际上就是生成解树，即证明原始节点是可解节点的过程。这一过程涉及到搜索的问题，对于与/或树的搜索将在后面详细讨论。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.5例4.4三阶梵塔问题。要求把1号钢针上的3个金片全部移
6、到3号钢针上，如下图所示。解：这个问题也可用状态空间法来解，不过本例主要用它来说明如何用归约法来解决问题。为了能够解决这一问题，首先需要定义该问题的形式化表示方法。设用三元组(i,j,k)表示问题在任一时刻的状态，用“→”表示状态的转换。上述三元组中i代表金片C所在的钢针号j代表金片B所在的钢针号k代表金片A所在的钢针号1231232.1问题归约法2.问题的与/或树表示Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.6利用问题归约方
7、法，原问题可分解为以下三个子问题：(1)把金片A及B移到2号钢针上的双金片移动问题。即(1,1,1)→(1,2,2)(2)把金片C移到3号钢针上的单金片移动问题。即(1,2,2)→(3,2,2)(3)把金片A及B移到3号钢针的双金片移动问题。即(3,2,2)→((3,3,3)其中，子问题(1)和(3)都是一个二阶梵塔问题，它们都还可以再继续进行分解；子问题(2)是本原问题，它已不需要再分解。三阶梵塔问题的分解过程可用如下图与/或树来表示(1,1,1)→(3
