rgzn_3图搜索技术中的问题归约

《rgzn_3图搜索技术中的问题归约》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、图搜索技术---问题归约(ProblemReduction)某些比较复杂的问题求解方法含有子问题的概念。应用这种方法去分析原始问题以产生一个子问题的集合。这样，对该子问题集合的某个具体子集的解答就意味着是对原始问题的一个解答。例如“猴子和香蕉”问题的例子。为了解答“猴子和香蕉”这个总问题，我们可以把它归约为下列四个子问题：49图搜索技术---问题归约(ProblemReduction)某些比较复杂的问题求解方法含有子问题的概念。应用这种方法去分析原始问题以产生一个子问题的集合。这样，对该子问题集合的某个具

2、体子集的解答就意味着是对原始问题的一个解答。例如“猴子和香蕉”问题的例子。为了解答“猴子和香蕉”这个总问题，我们可以把它归约为下列四个子问题：49子问题１：猴子从位置ａ走到位置ｂ；子问题２：猴子把箱子从位置ｂ推到位置ｃ；子问题３：猴子爬上箱顶；子问题４：猴子摘到香蕉。如果我们能够得到这四个子问题的一组解答，那么我们也就求得“猴子和香蕉”问题的一个解答。每个子问题可用任何一种可行的方法加以解答。可用上一章中的状态空间法求解，也可用归约的方法再进行分析并产生出子——子问题等等。49任何首先产生子问题然后又解决

3、子问题的解题方法，叫问题归约法。状态空间法问题归约方法节点:状态问题算符:一状态另一状态将大问题分解为一批小问题求解:在一个图(纯”或”图)中在一个”与或”图中找一找一条”解路”棵”解树”A结论A例:已知结论I,L,K成立,试证明结论A成立。 解树CBGCFEDBLKIIHLKJ49一个采用问题归约的问题表示可由下列三部分组成：1.一个初始问题描述；如对结论的A描述2.一套把问题变换为子问题的算符；3.一套本原问题描述。如I,L,K采用问题归约法生成与或图的足够部分以问题求解证明始点是可解的3.1.1

4、示例（梵塔难题）49它的一种通常的提法如下：有三个柱子（1、2和3）和三个不同尺寸的圆盘（A、B和C）。在每个圆盘的中心有个孔，所以圆盘可以堆叠在柱子上。最初，全部三个圆盘都堆在柱子1上：最大的圆盘C在底部；最小的圆盘A在顶部。要求把所有圆盘都移到柱子3上。搬动圆盘时，每次只许移一个，而且只能先搬动柱子顶部的圆盘，还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上。这个问题的初始配置和目标配置如图所示。柱123起始状态49柱123目标状态当然，这个问题可用状态空间法来求解。状态（i，j，k）描述：大片在i上；中

5、片在柱子j上；而小片在柱子k上。起始状态（1，1，1）目标状态（3，3，3）状态空间搜索图为：（1，1，1）49（1，1，3）（1，1，2）（1，2，3）（1，3，2）（1，2，1）（1，2，2）（3，2，2）：：（3，2，3）（3，2，1）：（3，1，3）（3，3，1）（3，3，2）（3，1，2）（3，1，1）（3，3，3）梵塔难题也可以由简单的问题归约方法来求解。梵塔问题的一种传统提法是64个圆盘，而不仅仅是三个圆盘。如果按照前述有关规则来把64个不同尺寸的圆盘从柱子1移至柱子3，那么需要搬动圆盘264

6、－1≈26449=1064log2≈1019.27次！问题归约解法始问题（1，1，1）（3，3，3）算符：将大问题（难度为n）分解为若干个小问题（难度〈=n-1）移n片从a到b的问题将一片从a到b的子问题将n-1片从c到b的子问题将n-1片从a到c的子问题49本原问题：一次只移一片的问题，即状态空间中只需迈一步就可解决的问题问题归约图（1,1,1）=è（3,3,3）（1,2,2）=è（3,2,2）（3,2,2）=è（3,3,3）（1,1,1）=è（1,2,2）Ö（1,1,1）è（1,1,3）（1,1,

7、3）è（1,2,3）（1,2,3）è（1,2,2）（3,2,2）è（3,2,1）（3,2,1）è（3,3,1）（3,3,1）è（3,3,3）ÖÖÖÖÖÖ状态i到目标状态问题可把状态空间中每一状态（节点）看成是从该状态到目标状态所形成的问题：状态i状态j到目标状态的子问题状态i到状态j的子问题状态j493.1.2问题归约方法中的问题描述用状态空间表示来描述某个问题往往是方便的。我们已经知道，任何状态空间搜索问题可以由下列三部分来表示：1.初始状态的集合S；2.把一些状态描述变换为另一些描述的算符集合F；

8、3.目标状态集合G。于是，三元组合（S，F，G）就规定了一个问题，并且可作为一个问题描述。对于梵塔难题，基本上也应用了这种表示法。493.1.3问题归约算符定理证明中问题的归约形式：问题表示：令S代表我们要证明是正确的论点，T代表前提论点的集合。这样，我们就令S

9、T（读做S给T）描述已知T前提的S证明问题。即：若有前提论点集合T,则必有结论S的证明问题归约方式：S｜TS｜T,XX｜T49一般情况下，需加入个前