第二讲知识表示状态空间问题归约表示法课件

第二讲知识表示状态空间问题归约表第二讲知识表示状态空间问题归约表示法示法11、用道德的示范来造就一个人，显然比用法律来约束他更有价值。希腊12、法律是无私的，对谁都一视同仁。在每件事上，她都不徇私情。托马斯13、公正的法律限制不了好的自由，因为好人不会去做法律不允许的事情。弗劳德14、法律是为了保护无辜而制定的。爱略特15、像房子一样，法律和法律都是相互依存的。伯克状状态空空间法三要点法三要点状状态态（state）：表表示示问问题题解解法法中中每每一一步步问问题题状状况况的数据结构；的数据结构；算算符符（operator）：把把问问题题从从一一种种状状态态变变换换为为另另一一种状态的手段；种状态的手段；状状态态空空间间方方法法：基基于于解解答答空空间间的的问问题题表表示示和和求求解解方方法法，它它是是以以状状态态和和算算符符为为基基础础来来表表示示和和求求解解问问题的。题的。2024/7/1661.问题状态描述要完成某个问题的状态描述，必须确定三件事：要完成某个问题的状态描述，必须确定三件事：1.该状态描述方式，特别是初始状态描述；该状态描述方式，特别是初始状态描述；2.操作符集合及其对状态描述的作用；操作符集合及其对状态描述的作用；3.目标状态描述的特性。目标状态描述的特性。2024/7/167定定义:状状态态(state)：为为描描述述某某类类不不同同事事物物间间的的差差别别而而引引入入的的一一组组最最少少变变量量q0，q1，qn的的有有序序集集合合，其其矢量形式如下：矢量形式如下：式式中中每每个个元元素素qi(i=0,1，n)为为集集合合的的分分量量，称称为为状态变量。状态变量。2024/7/168给给定定每每个个变变量量的的一一组组值值就就得得到到一一个个具具体体的的状状态态，如如 Qk=q0k，q1k，.，qnkT 它它只只是是问问题题所所有有可可能能状状态态的的罗罗列列，还还必必须须描描述述这这些状态之间的可能变化。些状态之间的可能变化。所所谓谓操操作作，或或称称为为算算子子是是引引起起状状态态中中的的某某分分量量发发生生改改变变，从从而而使使问问题题由由一一个个具具体体状状态态A变变化化为为另另一一具体状态具体状态B的作用。的作用。2024/7/169算符算符：使问题从一种状态变化为另一种状态的手段称为使问题从一种状态变化为另一种状态的手段称为操操作符作符或或算符算符。操作符可为走步、过程、规则、数学算子、。操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。运算符号或逻辑符号等。问题的状态空间问题的状态空间(state space)：是一个表示该问题全部可能是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即所有可能状态及其关系的图，它包含三种说明的集合，即所有可能的问题初始状态集合的问题初始状态集合S(初始状态初始状态S0S)、操作符集合、操作符集合F以及以及目标状态集合目标状态集合G(G S)。可把状态空间记为三元状态。可把状态空间记为三元状态(S，F，G)。状态空间可用状态空间可用有向图有向图来表示来表示2024/7/1610状状态态空空间间的的一一个个解解 使使一一个个有有限限的的操操作作算算子子序序列列，它它使使初初始始状状态态转转化化为为目目标标状状态态：S0-f1-S1-f2-.fk-G 2024/7/1611状态空间表示详释让让我我们们先先用用数数码码难难题题(puzzle problem)来来说说明明状状态态空空间间表表示示的的概概念念。由由15个个编编有有1至至15并并放放在在44方方格格棋棋盘盘上上的的可可走走动动的的棋棋子子组组成成。棋棋盘盘上上总总有有一一格格是是空空的的，以以便便可可能能让让空空格格周周围围的的棋棋子子走走进进空空格格，这这也也可可以以理理解解为为移移动动空空格格。图图中中绘绘出出了了两两种种棋棋局局，即即初初始始棋棋局局和和目目标标棋棋局局，它它们们对对应应于于该该下下棋棋问问题题的初始状态和目标状态。的初始状态和目标状态。如如何何把把初初始始棋棋局局变变换换为为目目标标棋棋局局呢呢？问问题题的的解解答答就就是是某某个个合合适适的的棋棋子子走走步步序序列列，如如左左移移棋棋子子12，下移棋子下移棋子15，右移棋子，右移棋子4，等等。等等。2024/7/1612 （a）初始棋局）初始棋局 （b）目标棋局）目标棋局 十五数码难题十五数码难题1410213685712311549111514131211109876543212024/7/1613总状态为总状态为16!20922789888000由于棋盘的对称性，实际状态数减半由于棋盘的对称性，实际状态数减半上、下、左、右移动四种操作上、下、左、右移动四种操作2024/7/1614十十五五数数码码难难题题最最直直接接的的求求解解方方法法是是尝尝试试各各种种不不同同的的走走步步，直直到到偶偶然然得得到到该该目目标标棋棋局局为为止止。这这种种尝尝试试本本质质上上涉涉及及某某种种试试探探搜搜索索。从从初初始始棋棋局局开开始始，试试探探(对对于于一一般般问问题题实实际际上上是是由由计计算算机机进进行行计计算算和和执执行行的的)由由每每一一合合法法走走步步得得到到的的各各种种新新棋棋局局，然然后后计计算算再再走走一一步步而而得得到到的的下下一一组组棋棋局局。这这样样继继续续下下去去，直直至至达达到到目目标标棋棋局局为为止止。把把初初始始状状态态可可达达到到的的各各状状态态所所组组成成的的空空间间设设想想为为一一幅幅由由各各种种状状态态对对应应的的节节点点组组成成的的图图。这这种种图图称称为为状状态态图图。图图中中每每个个节节点点标标有有它它所所代代表表的的棋棋局局。首首先先把把适适用用的的算算符符用用于于初初始始状状态态，以以产产生生新新的的状状态态；然然后后，再再把把另另一一些些适适用用算算符符用用于于这这些些新新的的状状态态；这这样样继继续续下去，直至产生目标状态为止。下去，直至产生目标状态为止。部分状态图为：部分状态图为：2024/7/16151410213685712311549111410213685712311549111410213685712431159111410213685712311549111410213657128311549111410213685712431159111410213685712431159111410213857612311549112024/7/1616我们一般用状态空间法这一术语来表示下述方法：我们一般用状态空间法这一术语来表示下述方法：从从某某个个初初始始状状态态开开始始，每每次次加加一一个个操操作作符符，递递增增地地建建立立起操作符的试验序列，直到目标状态为止。起操作符的试验序列，直到目标状态为止。寻寻找找状状态态空空间间的的全全部部过过程程包包括括从从旧旧的的状状态态描描述述产产生生新新的的状状态态描描述述，以以及及此此后后检检验验这这些些新新的的状状态态描描述述，看看其其是是否否描描述述了了该该目目标标。这这种种检检验验往往往往只只是是查看某个状态是否与给定的查看某个状态是否与给定的 目标状态描述相匹配。目标状态描述相匹配。2024/7/1617要完成某个问题的状态描述，必须确定三件事：要完成某个问题的状态描述，必须确定三件事：1.该状态描述方式，特别是初始状态描述；该状态描述方式，特别是初始状态描述；2.操作符集合及其对状态描述的作用；操作符集合及其对状态描述的作用；3.目标状态描述的特性。目标状态描述的特性。2024/7/16182.状态图示法 图论中的几个中的几个术语节节点点(node)：图图形形上上的的汇汇合合点点，用用来来表表示示状状态态、事事件件和和时时 间间关关系系的的汇汇合合，也也可可用用来来指指示示通通路路的的汇汇合；合；弧线弧线(arc)：节点间的连接线；：节点间的连接线；有有向向图图(directed graph)：一一对对节节点点用用弧弧线线连连接接起起来，从一个节点指向另一个节点。来，从一个节点指向另一个节点。2024/7/1619后后继继节节点点(descendant node)与与父父辈辈节节点点(parent node)：如如果果某某条条弧弧线线从从节节点点ni指指向向节节点点nj，那那么么节节点点nj就就叫叫做做节节点点ni的的后后继继节节点点或或后后裔裔，而而节节点点ni叫做节点叫做节点nj的的父辈节点父辈节点或或祖先祖先。路路径径：某某个个节节点点序序列列(ni1,ni2,nik)当当j=2，3，k时时，如如果果对对于于每每一一个个ni,j-1都都有有一一个个后后继继节节点点nij存存在在，那那么么就就把把这这个个节节点点序序列列叫叫做做从从节节点点ni1至至节节点点nik的长度为的长度为k的的路径路径。代代价价：用用c(ni,nj)来来表表示示从从节节点点ni指指向向节节点点nj的的那那段段弧线的代价。弧线的代价。2024/7/1620如果从节点如果从节点ni至节点至节点nj存在有一条路径，那么就称节点存在有一条路径，那么就称节点nj 是从节点是从节点ni可达到的节点可达到的节点。两节点间路径的两节点间路径的代价代价等于连接该路径上各节点的所有弧线等于连接该路径上各节点的所有弧线代价之和。最小者称为代价之和。最小者称为最小代价的路径。最小代价的路径。2024/7/1621显显式式表表示示：各各节节点点及及其其具具有有代代价价的的弧弧线线由由一一张张表表明明确确给给出出。此此表表可可能能列列出出该该图图中中的的每每一一节节点点、它它的后继节点以及连接弧线的代价。的后继节点以及连接弧线的代价。隐隐式式表表示示：节节点点的的无无限限集集合合si作作为为起起始始节节点点是是已已知知的的。后后继继节节点点算算符符也也是是已已知知的的，它它能能作作用用于于任任一一节节点点以以产产生生该该节节点点的的全全部部后后继继节节点点和和各各连连接接弧弧线的代价。线的代价。2024/7/1622图的显式和隐式表示 一一个个图图可可由由显显式式说说明明也也可可由由隐隐式式说说明明。显显然然，显显式式说说明明对对于于大大型型的的图图是是不不切切实实际际的的，而而对对于于具具有有无无限限节节点点集集合合的的图图则是不可能的。则是不可能的。此此外外，引引入入后后继继节节点点算算符符的的概概念念是是方方便便的的。后后继继节节点点算算符符也也是是已已知知的的，它它能能作作用用于于任任一一节节点点以以产产生生该该节节点点的的全全部部后后继继节节点点和和各各连连接接弧弧线线的的代代价价(用用我我们们的的状状态态空空间间术术语语来来说说，后后继继算算符符是是由由适适用用于于已已知知状状态态描描述述的的算算符符集集合合所所确确定定的的)。把把后后继继算算符符应应用用于于si的的成成员员和和它它们们的的后后继继节节点点以以及及这这些些后后继继节节点点的的后后继继节节点点，如如此此无无限限制制地地进进行行下下去去，最最后后使使得得由由和和si所所规规定定的的隐隐式式图图变变为为显显示示图图。把把后后继继算算符符应应用用于于节点的过程，就是扩展一个节点的过程。节点的过程，就是扩展一个节点的过程。2024/7/1623因因此此，搜搜索索某某个个状状态态空空间间以以求求得得算算符符序序列列的的一一个个解解答答的的过过程程，就就对对应应于于使使隐隐式式图图足足够够大大一一部部分分变变为为显显式式以以便便包包含含目目标标的的过过程程。这这样样的的搜搜索索图图是是状状态空间问题求解的主要基础。态空间问题求解的主要基础。问问题题的的表表示示对对求求解解工工作作量量有有很很大大的的影影响响。人人们们显显然然希希望望有有较较小小的的状状态态空空间间表表示示。许许多多似似乎乎很很难难的的问问题题，当当表表示示适适当当时时就就可可能能具具有有小小而而简简单单的的状状态态空间。空间。2024/7/16243.状态空间表示举例 各各种种问问题题都都可可用用状状态态空空间间加加以以表表示示，并并用用状状态态空空间搜索法来求解。间搜索法来求解。如如果果能能够够用用一一种种不不同同的的表表示示方方法法来来求求解解用用一一问问题题，也不必感到惊讶。也不必感到惊讶。产生式系生式系统（Production System）是描述搜索过程的方法。是描述搜索过程的方法。2024/7/1625一个一个产生式系生式系统由下面三部分由下面三部分组成：成：一一个个总总数数据据库库(global database)：它它含含有有与与具具体体任任务务有有关关的的信信息息；随随着着应应用用情情况况的的不不同同，这这些些数数据据库库可可能能小小得得像像数数字字矩矩阵阵那那样样简简单单，或或许许大大得得如如检检索索文文件件结结构构那那么复杂。么复杂。一一套套规规则则：它它对对数数据据库库进进行行操操作作运运算算。每每条条规规则则由由左左右右两两部部分分组组成成，左左部部鉴鉴别别规规则则的的适适用用性性或或先先决决条条件件，右右部部描描述述规规则则应应用用时时所所完完成成的的动动作作。应应用用规规则则来来改改变变数据库，就象应用算符来改变状态一样数据库，就象应用算符来改变状态一样一一个个控控制制策策略略：它它确确定定应应该该采采用用哪哪一一条条适适用用规规则则，而而且且当当数数据据库库的的终终止止条条件件满满足足时时，就就停停止止计计算算。控控制制策策略由控制系统选择和确定。略由控制系统选择和确定。2024/7/1626状态空间表示举例 猴猴子子和和香香蕉蕉问问题题(monkey and banana problem)在在一一个个房房间间内内有有一一只只猴猴子子(可可把把这这只只猴猴子子看看做做一一个个机机器器人人)、一一个个箱箱子子和和一一束束香香蕉蕉。香香蕉蕉挂挂在在天天花花板板下下方方，但但猴猴子子的的高高度度不不足足以以碰碰到到它它。那那么么这这只只猴猴子子怎怎样样才才能能摘摘到到香香蕉蕉呢呢?图图中中表表示示出出猴猴子子、香香蕉蕉和和箱箱子在房间内的相对位置。子在房间内的相对位置。2024/7/1627用一个四元表列用一个四元表列(W,x,Y,z)来表示这个问题的状态，来表示这个问题的状态，其中其中W猴子的水平位置猴子的水平位置X当猴子在箱子顶上时取当猴子在箱子顶上时取X=1；否则取；否则取X=0Y箱子的水平位置箱子的水平位置Z当猴子摘到香蕉时取当猴子摘到香蕉时取Z=1；否则取；否则取Z=02024/7/1628这个问题中的操作这个问题中的操作(算符算符)如下：如下：(1)goto(U)猴子走到水平位置猴子走到水平位置U，或者用产生式规则表示为，或者用产生式规则表示为 (W，0，Y，z)(U，0，Y，z)即应用操作即应用操作goto(U)，能把状态，能把状态(W，0，Y，z)变换为状态变换为状态(U，0，Y，z)。(2)pushbox(V)猴子把箱子推到水平位置猴子把箱子推到水平位置V，即有，即有 (W，0，W，z)(V，0，V，z)应当注意的是，要应用算符应当注意的是，要应用算符pushbox(V)，就要求产生式规，就要求产生式规则的左边，猴子与箱子必须在同一位置上，并且，猴子不则的左边，猴子与箱子必须在同一位置上，并且，猴子不是在箱子顶上。这种强加于操作的适用性条件，叫做是在箱子顶上。这种强加于操作的适用性条件，叫做产生产生式规则的先决条件式规则的先决条件。2024/7/1629(3)climbbox猴子爬上箱顶，即有猴子爬上箱顶，即有 (W，0，W，z)(W，1，W，z)在应用算符在应用算符climbbox时也必须注意到，猴子和箱子应当在时也必须注意到，猴子和箱子应当在同一位置上，而且猴子不在箱顶上同一位置上，而且猴子不在箱顶上。(4)grasp猴子摘到香蕉，即有猴子摘到香蕉，即有 (c,1,c,0)(c,1,c,1)其中，其中，c是香蕉正下方的地板位置，在应用算符是香蕉正下方的地板位置，在应用算符grasp时，要求猴子和箱子都在位置时，要求猴子和箱子都在位置c上，并且猴子已在箱子顶上，并且猴子已在箱子顶上。上。2024/7/1630应应当当说说明明的的是是，在在这这种种情情况况下下，算算符符(操操作作)的的适适用用性性及及作作用用均均由由产产生生式式规规则则表表示示。例例如如，对对于于规规则则(2)，只只有有当当算算符符pushbox(V)的的先先决决条条件件，即即猴猴子子与与箱箱子子在在同同一一位位置置上上而而且且猴猴子子不不在在箱箱顶顶上上这这些些条条件件得得到到满满足足时时，算算符符pushbox(V)才才是是适适用用的的。这这一一操操作作算算符符的的作作用用是是猴猴子子把把箱箱子子推推到到位位置置V。在在这这一一表表示示中中，目目标标状状态态的的集集合合可可由由任任何何最最后后元元素素为为1的表列来描述。的表列来描述。2024/7/1631令令初初始始状状态态为为(a,0,b,0)。这这时时，goto(U)是是唯唯一一适适用用的的操操作作，并并导导致致下下一一状状态态(U,0,b,0)。现现在在有有3个个适适用用的的操操作作，即即goto(U)，pushbox(V)和和climbbox(若若U=b)。把把所所有有适适用用的的操操作作继继续续应应用用于于每每个个状状态态，我我们们就就能能够够得得到到状状态态空空间间图图。从从图图不不难难看看出出，把把该该初初始始状态变换为目标状态的操作序列为状态变换为目标状态的操作序列为 goto(b),pushbox(c),climbbox,grasp2024/7/16322024/7/1633问题归约法 问问题题归归约约(problem reduction)是是另另一一种种问问题题描描述述与与求解方法。求解方法。先先把把问问题题分分解解为为子子问问题题和和子子-子子问问题题，然然后后解解决决较较小小的的问题。问题。对对该该问问题题的的某某个个具具体体子子集集的的解解答答就就意意味味着着对对原原始始问问题题的的一个解答。一个解答。2024/7/16341.问题归约描述问题归约表示的问题归约表示的组成部分组成部分：一个初始问题描述；一个初始问题描述；一套把问题变换为子问题的操作符；一套把问题变换为子问题的操作符；一套本原问题描述。一套本原问题描述。其其中中的的每每一一个个问问题题是是不不证证明明的的，自自然然成成立立的的，如如公公理理、已已知知的的实事等（本原问题集）实事等（本原问题集）问问题题归归约约的的实实质质：从从目目标标(要要解解决决的的问问题题)出出发发逆逆向向推推理理，建建立立子子问问题题以以及及子子问问题题的的子子问问题题，直直至至最最后把初始问题归约为一个平凡的本原问题集合。后把初始问题归约为一个平凡的本原问题集合。2024/7/1635梵塔难题 有有3个个柱柱子子(1，2和和3)和和3个个不不同同尺尺寸寸的的圆圆盘盘（A，B和和C）。在在每每个个圆圆盘盘的的中中心心有有一一个个孔孔，所所以以圆圆盘盘可可以以堆堆叠叠在在柱柱子子上上。最最初初，3个个圆圆盘盘都都堆堆在在柱柱子子1上上：最最大大的的圆圆盘盘C在在底底部部，最最小小的的圆圆盘盘A在在顶顶部部。要要求求把把所所有有圆圆盘盘都都移移到到柱柱子子3上上，每每次次只只许许移移动动一一个个，而而且且只只能能先先搬搬动动柱柱子子顶顶部部的的圆圆盘盘，还还不不许许把把尺尺寸寸较较大大的的圆圆盘盘堆堆放放在在尺尺寸寸较较小小的的圆圆盘盘上上。这这个个问问题题的的初始配置和目标配置如图所示。初始配置和目标配置如图所示。2024/7/1636解解题过程：程：将将原原始始问问题题归归约约为为一一个个较较简简单单问问题题集集合合，要要把把所所有有圆圆盘盘都都移移至至柱柱子子3，我我们们必必须须首首先先把把圆圆盘盘C移移至至柱柱子子3；而而且且在在移移动动圆圆盘盘C至至柱柱子子3之之前前，要要求求柱柱子子3必必须须是是空空的的。只只有有在在移移开开圆圆盘盘A和和B之之后后，才才能能移移动动圆圆盘盘C；而而且且圆圆盘盘A和和B最最好好不不要要移移至至柱柱子子3就就不不能能把把圆圆盘盘C移移至至柱柱子子3。因因此此，首首先先应应该该把把圆圆盘盘A和和B移移到到柱柱子子2上上。然然后后才才能能够够进进行行关关键键的的一一步步，把把圆圆盘盘C从从柱柱子子1移移至至柱柱子子3，并并继继续续解解决难题的其余部分。决难题的其余部分。将将原原始始难难题题归归约约（简简化化）为为下下列列子子难难题题：移移动动圆圆盘盘A和和B至柱子至柱子2的双圆盘难题，如图的双圆盘难题，如图(a)所示。所示。2024/7/1637把原始难题归约（简化）为以下三个子难题：把原始难题归约（简化）为以下三个子难题：移动圆盘移动圆盘A和和B至柱子至柱子2的双圆盘难题；如图的双圆盘难题；如图(a)所示所示移动圆盘移动圆盘C至柱子至柱子3的单圆盘难题的单圆盘难题；如图；如图(b)所示所示移动圆盘移动圆盘A和和B至柱子至柱子3双圆盘难题；如图双圆盘难题；如图(c)所示所示2024/7/1638图图 2.7 2.7 梵塔问题解答梵塔问题解答(a)(a)图图 2.8 2.8 梵塔问题解答梵塔问题解答(b)(b)图图 2.9 2.9 梵塔问题解答梵塔问题解答(c)(c)2024/7/1639梵梵塔塔问问题题归归约约图图：子子问问题题2可可作作为为本本原原问问题题考考虑虑，因因为为它它的的解解只只包包含含一一步步移移动动。应应用用一一系系列列相相似似的的推推理理，子子问问题题1和和子子问问题题3也也可可被被归归约约为为本本原原问问题题，如如图图2.10所所示示。这这种种图图式结构，叫做式结构，叫做与或图与或图(AND/OR graph)。它能有效地说明如何由问题归约法求得问题的解答。它能有效地说明如何由问题归约法求得问题的解答。图图 2.10 2.10 梵塔问题归约图梵塔问题归约图2024/7/1640把把一一个个问问题题描描述述变变换换为为一一个个归归约约或或后后继继问问题题描描述述的的集集合合，这这是是由由问问题题归归约约算算符符进进行行的的。变变换换所所得得所有后继问题的解就意味着父辈问题的一个解所有后继问题的解就意味着父辈问题的一个解。所所有有问问题题归归约约的的目目的的是是最最终终产产生生具具有有明明显显解解答答的的本本原原问问题题。这这些些问问题题可可能能是是能能够够由由状状态态空空间间搜搜索索中中走走动动一一步步来来解解决决的的问问题题，或或者者可可能能是是别别的的具具有有已知解答的更复杂的问题。已知解答的更复杂的问题。2024/7/16412.与或图表示 一一般般地地，我我们们用用一一个个类类似似图图的的结结构构来来表表示示把把问问题题归归约约为为后后继继问问题题的的替替换换集集合合，这这种种结结构构图图叫叫做做问问题归约图题归约图，或叫，或叫与或图与或图。如下图所示。如下图所示:图图 2.13 2.13 子问题集合子问题集合图图 2.14 2.14 与或图与或图2024/7/1642一些关于一些关于与或图的术语与或图的术语：父父节点点、子（后子（后继）节点点、弧弧线、起始起始节点点。终叶叶节点点：对应于原问题的本原节点。：对应于原问题的本原节点。或或节点点：只只要要解解决决某某个个问问题题就就可可解解决决其其父父辈辈问问题题的的节节点点集合，如（集合，如（M，N，H）。）。与与节点点：只只有有解解决决所所有有子子问问题题，才才能能解解决决其其父父辈辈问问题题的的节节点点集集合合，如如（B,C)和和（D,E,F）各各个个结结点点之之间间用用一一端端小圆弧连接标记。小圆弧连接标记。与或与或图：由：由与与节点点及及或或节点点组成的结构图。组成的结构图。2024/7/1643可解可解节点点的一般定义的一般定义(1)终叶节点是可解节点终叶节点是可解节点(因为它们与本原问题相关连因为它们与本原问题相关连)。(2)如如果果某某个个非非终终叶叶节节点点含含有有或或后后继节点点，那那么么只只要要当当其其后后继继节节点点至至少少有有一一个个是是可可解解的的时时，此此非非终终叶叶节节点点才才是是可解的。可解的。(3)如如果果某某个个非非终终叶叶节节点点含含有有与与后后继节点点，那那么么只只要要当当其后继节点全部为可解时，此非终叶节点才是可解的。其后继节点全部为可解时，此非终叶节点才是可解的。2024/7/1644不可解不可解节点点的一般定义的一般定义:(1)没有后裔的非终叶节点为不可解节点。没有后裔的非终叶节点为不可解节点。(2)如如果果某某个个非非终终叶叶节节点点含含有有或或后后继节点点，那那么么只只有有当当其全部后裔为不可解时，此非终叶节点才是不可解的。其全部后裔为不可解时，此非终叶节点才是不可解的。(3)如如果果某某个个非非终终叶叶节节点点含含有有与与后后继节点点，那那么么只只要要当当其其后后裔裔至至少少有有一一个个为为不不可可解解时时，此此非非终终叶叶节节点点才才是是不不可可解的。解的。2024/7/1645图2.15 中，终叶节点用字母t表示，有解节点用小原点表示，而解图用粗线分支表示。图图 2.15 2.15 与或图例子与或图例子2024/7/1646与或图构成规则(1)与与或或图图中中的的每每个个节节点点代代表表一一个个要要解解决决的的单单一一问问题题或或问问题题集集合合。图图中所含起始节点对应于原始问题。中所含起始节点对应于原始问题。(2)对应于本原问题的节点，叫做终叶节点，它没有后裔。对应于本原问题的节点，叫做终叶节点，它没有后裔。(3)对对于于把把算算符符应应用用于于问问题题A的的每每种种可可能能情情况况，都都把把问问题题变变换换为为一一个个子问题集合；有向弧线自子问题集合；有向弧线自A 指向后继节点表示所求得的子问题集合。指向后继节点表示所求得的子问题集合。(4)一一般般对对于于代代表表两两个个或或两两个个以以上上子子问问题题集集合合的的每每个个节节点点，有有向向弧弧线线从从此此节节点点指指向向此此子子问问题题集集合合中中的的各各个个节节点点。由由于于只只有有当当集集合合中中所所有有的的项项都都有有解解时时，这这个个子子问问题题的的集集合合才才能能获获得得解解答答，所所以以这这些些子子问问题题节节点点叫做与节点。叫做与节点。(5)在在特特殊殊情情况况下下，当当只只有有一一个个算算符符可可应应用用于于问问题题A，而而且且这这个个算算符符产产生生具具有有一一个个以以上上子子问问题题的的某某个个集集合合时时，由由上上述述规规则则3和和规规则则4所所产产生生的图可以得到简化。的图可以得到简化。因此，代表子问题集合的中间或节点可以被略去，如右图所示。因此，代表子问题集合的中间或节点可以被略去，如右图所示。图图 2.16 2.16 与或树与或树2024/7/16473.问题归约机理 关关键算符算符 对对于于许许多多状状态态空空间间的的搜搜索索问问题题，要要推推测测一一个个状状态态空空间间算算符符的的特特性性并并不不是是太太困困难难的的。也也就就是是说说，尽尽管管寻寻求求某某个个解解答答中中整整个个算算符符序序列列的的问问题题是是困困难难的的，但但是是规规定定这这些些算算符符中中的的一一个个却却往往往往是是容容易易的的。当当应应用用该该算算符符中中的的一一个个被被认认为为是是问问题题求求解解的的决决定定性性步步骤骤时时，寻寻找找这这样样一一个个算算符符的的可可能能性性就就增增加加了了。例例如如，对对我我们们前前面面讨讨论论过过的的梵梵塔塔问问题题，移移动动圆圆盘盘C至至柱柱子子3这这个个算算符符可可被被选选为为问问题题求求解解的的决决定定性性步步骤骤(见见图图2.9)，我我们们把把这这种种具具有有决决定定性性作作用用的的算算符符叫做叫做关键算符关键算符。2024/7/1648当当某某个个关关键键算算符符被被决决定定时时，它它可可被被用用来来辨辨别别问问题题归归约约过过程程中中的的路路标标。假假设设F中中的的某某个个f是是由由三三元元状状态态(S，F，G)表表示示的的问问题题的的关关键键算算符符。既既然然我我们们认认为为f必必定定要要应应用用，所所以以(S，F，G)表表示示第第一一个个后后裔裔问问题题是是一一个个对对应应于于寻寻找找一一条条通通向向某某一一f适适用用的的状状态态的的路路径径问问题题。令令Gf表表示示f适适用用的的所所有有状状态态的的集集合合。由由此此，我我们们设设立立了了一一个个由由(S，F，Gf)描描述述的的子子问问题题。一一旦旦这这个个子子问问题题获获得得解解决决，规规定定一一个个状状态态gGf,我我们们就就能能够够设设立立由由(g,F,f(g)表表示示的的本本原原问问题题，其其中中，f(g)表表示示把把f应应用用于于g而而得得到到的的状状态态。因因为为这这个个问问题题仅仅仅仅由由应应用用关关键键算算符符f来来解解决决，所所以以它它是是本本原原的的。于于是是，剩剩下下的的(未未解解决决的的)是是由三元状态由三元状态(f(g),F,G)描述的问题。描述的问题。当当某某个个状状态态空空间间的的关关键键算算符符能能够够被被规规定定时时，我我们们就就能能应应用用下列问题归约下列问题归约(见图见图2.17)。2024/7/1649我我们们没没有有表表示示出出本本原原问问题题(g,F,f(g)(g,F,f(g)而而简简化化了了这这个个图图。然然后后，这这两两个个后后裔裔问问题题能能够够用用直直接接的的状状态态空空间间搜搜索索技技术术或或进进一一步步的的问问题题归归约约来来求求解解。如如果果采采用用进进一一步步的的归归约约策策略略，我我们们必必定定能能够够辨辨识识问问题题(S(S，F F，Gf)Gf)的的某某个个关关键键算算符符，并并继继续续归归约约下去下去。图图 2.172.172024/7/1650对对于于许许多多问问题题，我我们们往往往往无无法法辨辨别别某某单单个个关关键键算算符符和和预预先先知知道道其其为为某某个个问问题题解解答答的的决决定定性性步步骤骤。我我们们只只能能推推测测某某个个算算符符的的子子集集合合，其其中中某某个个算算符符很很有有可可能能是是决决定定性性的的。该该子子集集合合中中的的每每个个算算符符产产生生一一对对后后裔裔问问题题。当当从从各各种种替替换换算算符符中中寻寻求求某某个个解解答答时时，从从一一个个应应用用这这种种想想法法的的搜搜索索过过程程可可建建立立起一个与或图。起一个与或图。要要应应用用这这个个方方法法，首首先先我我们们必必须须有有某某种种方方法法用用来来计计算算任任何何状状态态空空间间搜搜索索问问题题的的候候选选关关键键算算符符集集合合。下面我们要叙述以差别为基础的一种特别方法。下面我们要叙述以差别为基础的一种特别方法。2024/7/1651 差差别寻寻找找候候选选关关键键算算符符的的一一种种方方法法涉涉及及计计算算某某个个问问题题(S，F，G)的的差差别别。粗粗略略地地说说，问问题题(S，F，G)的的差差别别就就是是用用S的的元元对对由由集集合合G规规定定的的目目标标进进行行测测试试失失败败原原因因的的部部分分表表列列(如如果果S的的某某个个元元是是在在G中中，那那么么此此问问题题就就获获得得解解决决，也也就就不不存存在在差差别别)。举举例例来来说说，如如果果目目标标集集合合G由由某某个个状状态态条条件件集集合合所所规规定定，而而且且某某个个sS满满足足这这些些条条件件中中的的某某些些但但不不是是全全部部条条件件，那那么么，差差别别可可由由不不能能被被s满满足足的的条条件件的的部部分分表表列列组组成成。如如果果这这些些条条件件能能够够按按其其重重要要性性分分类类，那那么么我我们们宁宁愿愿选选用用最最重重要要的的不不满满足足条条件件作作为为差别。差别。2024/7/1652其其次次，我我们们把把某某些些状状态态空空间间算算符符或或算算符符集集合合与与每每个个可可能能的的差差别别结结合合起起来来。这这些些算算符符是是候候选选关关键键算算符符。只只有有当当应应用用某某个个算算符符是是与与消消去去某某个个差差别别相相关关时，此算符才与那个差别结合在一起。时，此算符才与那个差别结合在一起。2024/7/1653猴子和香蕉问题的与或图2024/7/1654解答序列：解答序列：goto(b),pushbox(c),climbbox,grasp1.关键算符关键算符 在在问问题题求求解解过过程程中中，具具有有决决定定性性作作用用的的算算符符叫叫做做关关键键算算符。符。2.差别差别寻寻找找候候选选关关键键算算符符的的一一种种方方法法就就是是要要计计算算某某个个问问题题(S,F,G)的的差差别别.不不能能被被S满满足足的的条条件件的的部部分分表表列列就就组组成成了了差差别别。我我们们选选择择最最重要的不满足条件作为差别重要的不满足条件作为差别。2024/7/1655猴子和香蕉问题把猴子和香蕉问题把4个算符的作用结果和适用条件个算符的作用结果和适用条件重写如下：重写如下：f1:(W,0,Y,z)-goto(U)-(U,0,Y,z)f2:(W,0,W,z)-pushbox(V)-(V,0,V,z)f3:(W,0,W,z)-climbbox-(W,1,W,z)f4:(c,1,c,0)-grasp-(c,1,c,1)2024/7/1656初始状态描述为表初始状态描述为表(a,0,b,0)F=f1,f2,f3,f4是是4个算符的集合个算符的集合G是是满满足足目目标标条条件件的的状状态态集集合合，初初始始问问题题变变为为（a,0,b,0,F,G),由由于于F在在本本问问题题中中不不发发生生变变化化可可从从表中删去表中删去,得（得（a,0,b,0，G)2024/7/1657于是，归约过程如下：于是，归约过程如下：首首先先，计计算算初初始始问问题题的的差差别别，表表列列(a,0,b,0)不不满满足足目目标标测测试试的的原原因因在在于于最最后后一一个个元元素素不不是是1。与与规规约约这这个个差差别别相相关关的的关关键键算算符符是是f4=grasp,用用f4来来归归约约，得得到到一一对对子子问问题题 （a,0,b,0,Gf4)(f4(S1），），G)其其中中，Gf4是是适适用用于于算算符符f4的的状状态态描描述述集集合合，而而S1是是Gf4中由求解（中由求解（a,0,b,0,Gf4)而得到的状态。而得到的状态。2024/7/1658要求解问题（要求解问题（a,0,b,0,Gf4)，计算其差别。，计算其差别。由由(a,0,b,0)所描述的状态不在所描述的状态不在Gf4中。中。因因为为：(1)箱箱子子b不不在在c处处，(2)猴猴子子不不在在c处处，(3)猴猴子子不不在在箱子上，有下列关键算符箱子上，有下列关键算符f2:pushbox（c)f1:goto(c)f3:climbbox2024/7/1659这些关键算符的第一个，用来把问题（这些关键算符的第一个，用来把问题（a,0,b,0,Gf4)归归约为一对子问题约为一对子问题（1-1）（）（a,0,b,0,Gf2）（1-2）(f2(S11），），Gf4）其中其中S11 Gf2由求解由求解(1-1)得到的。得到的。求解（求解（1-1），计算它的差别：猴子不在），计算它的差别：猴子不在b处处这个差别给出关键算符这个差别给出关键算符f1:goto(b)2024/7/1660这这个个关关键键算算符符又又被被用用来来把把问问题题（a,0,b,0,Gf2）归归结结为为一对子问题一对子问题（1-11）（）（a,0,b,0,Gf1）（1-12）(f1(S111），），Gf2）第第一一个个问问题题已已是是本本原原问问题题，差差别别为为零零，因因为为(a,0,b,0)是是在域在域f1内，内，f1可用来求解此问题。可用来求解此问题。求解第二个子问题求解第二个子问题由于由于f1(S111）=(b,0,b,0)(1-12)变为（变为（b,0,b,0,Gf2)这这个个问问题题也也是是本本原原问问题题，因因为为(b,0,b,0)在在域域f2内内，f2，可可用用于于求求解解此此问问题题。依依此此继继续续进进行行下下去去，直直到到最最后后解解答答此初始问题为止。此初始问题为止。2024/7/1661谢谢46、我们若已接受最坏的，就再没有什么损失。卡耐基47、书到用时方恨少、事非经过不知难。陆游48、书籍把我们引入最美好的社会，使我们认识各个时代的伟大智者。史美尔斯49、熟读唐诗三百首，不会作诗也会吟。孙洙50、谁和我一样用功，谁就会和我一样成功。莫扎特