📄 用问题归约法解猴子和香蕉问题.htm
字号:
<html>
<head>
<meta http-equiv="Content-Type"
content="text/html; charset=gb_2312-80">
<meta name="GENERATOR" content="Microsoft FrontPage 4.0">
<title>用问题归约法解猴子和香蕉问题</title>
</head>
<body bgcolor="#CCFFFF">
<p align="center"><font size="6">猴子和香蕉问题的与或图</font></p>
<p align="center"><a href="andorpicture.jpg"><img src="andorpicture.jpg"
width="1180" height="431" border="0"></a></p>
<p align="left"><font size="6">解答序列：</font></p>
<p align="left"><font size="5">{goto(b),pushbox(c),climbbox,grasp}</font></p>
<p align="left"><font size="5">1.关键算符</font></p>
<p align="left"><font size="5">
在问题求解过程中，具有决定性作用的算符叫做关键算符。</font></p>
<p align="left"><font size="5">2.差别</font></p>
<p align="left"><font size="5">
寻找候选关键算符的一种方法就是要计算某个问题(S,F,G)的差别.不能被S满足的条件的部分表列就组成了差别。我们选择最重要的不满足条件作为差别。</font></p>
<p align="left"><font size="5">猴子和香蕉问题把4个算符的作用结果和适用条件重写如下：</font></p>
<p align="left"><font size="5">f<sub>1</sub>:(W,0,Y,z)--goto(U)-->(U,0,Y,z)</font></p>
<p align="left"><font size="5">f<sub>2</sub>:(W,0,W,z)--pushbox(V)-->(V,0,V,z)</font></p>
<p align="left"><font size="5">f<sub>3</sub>:(W,0,W,z)--climbbox-->(W,1,W,z)</font></p>
<p align="left"><font size="5">f<sub>4</sub>:(c,1,c,0)--grasp-->(c,1,c,1)</font></p>
<p align="left"><font size="5">初始状态描述为表(a,0,b,0)</font></p>
<p align="left"><font size="5">F={f<sub>1</sub>,f<sub>2</sub>,f<sub>3</sub>,f<sub>4</sub>}是4个算符的集合</font></p>
<p align="left"><font size="5">G是满足目标条件的状态集合，初始问题变为</font></p>
<p align="left"><font size="5">（{a,0,b,0},F,G),由于F在本问题中不发生变化可从表中删去,得（{a,0,b,0}，G)</font></p>
<p align="left"><font size="5">于是，归约过程如下：</font></p>
<p align="left"><font size="5">首先，计算初始问题的差别，表列(a,0,b,0)不满足目标测试的原因在于最后一个元素不是1。与规约这个差别相关的关键算符是f<sub>4</sub>=grasp,用f<sub>4</sub>来归约，得到一对子问题</font></p>
<p align="left"><font size="5"> （{a,0,b,0},G<sub>f4</sub>)</font></p>
<p align="left"><font size="5"> (f<sub>4</sub>(S<sub>1</sub>），G)</font></p>
<p align="left"><font size="5">其中，</font><font size="5">G<sub>f4</sub>是适用于算符f<sub>4</sub>的状态描述集合，而S<sub>1</sub>是G<sub>f4</sub>中由求解（{a,0,b,0},G<sub>f4</sub>)而得到的状态。</font></p>
<p align="left"><font size="5"> 要求解问题</font><font size="5">（{a,0,b,0},G<sub>f4</sub>)，计算其差别。由(a,0,b,0)所描述的状态不在G<sub>f4</sub>中。因为：(1)箱子b不在c处，(2)猴子不在c处，(3)猴子不在箱子上，有下列关键算符</font></p>
<p align="left"><font size="5">f<sub>2</sub>:pushbox（c)</font></p>
<p align="left"><font size="5">f<sub>1</sub>:goto(c)</font></p>
<p align="left"><font size="5">f<sub>3</sub>:climbbox</font></p>
<p align="left"><font size="5">
这些关键算符的第一个，用来把问题</font><font size="5">（{a,0,b,0},G<sub>f4</sub>)归约为一对子问题</font></p>
<p align="left"><font size="5">（1-1）</font><font size="5">（{a,0,b,0},G<sub>f2</sub>）</font></p>
<p align="left"><font size="5">（1-2） </font><font size="5">(f<sub>2</sub>(S<sub>11</sub>），G<sub>f4</sub>）</font></p>
<p align="left"><font size="5">其中</font><font size="5">S<sub>11</sub>€G<sub>f2</sub>由求解(1-1)得到的。</font></p>
<p align="left"><font size="5">求解（1-1），计算它的差别：猴子不在b处</font></p>
<p align="left"><font size="5">这个差别给出关键算符</font></p>
<p align="left"><font size="5">f<sub>1</sub>:goto(b)</font></p>
<p align="left"><font size="5">
这个关键算符又被用来把问题</font><font size="5">（{a,0,b,0},G<sub>f2</sub>）归结为一对子问题</font></p>
<p align="left"><font size="5">（1-11）</font><font size="5">（{a,0,b,0},G<sub>f1</sub>）</font></p>
<p align="left"><font size="5">（1-12）</font><font size="5"> (f<sub>1</sub>(S<sub>111</sub>），G<sub>f2</sub>）</font></p>
<p align="left"><font size="5">
第一个问题已是本原问题，差别为零，因为(a,0,b,0)是在域f<sub>1</sub>内，f<sub>1</sub>可用来求解此问题。求解第二个子问题</font></p>
<p align="left"><font size="5">由于</font><font size="5">f<sub>1</sub>(S<sub>111</sub>）=(b,0,b,0)</font></p>
<p align="left"><font size="5">(1-12)变为（{b,0,b,0},G<sub>f2</sub>)</font></p>
<p align="left"><font size="5">这个问题也是本原问题，因为(b,0,b,0)在域f<sub>2</sub>内，f<sub>2</sub>，可用于求解此问题。依此继续进行下去，直到最后解答此初始问题为止。</font></p>
<p align="left"> </p>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -