知识表示状态空间问题归约表示法.pptVIP

解题过程：**将原始问题归约为一个较简单问题集合，要把所有圆盘都移至柱子3，我们必须首先把圆盘C移至柱子3；而且在移动圆盘C至柱子3之前，要求柱子3必须是空的。只有在移开圆盘A和B之后，才能移动圆盘C；而且圆盘A和B最好不要移至柱子3就不能把圆盘C移至柱子3。因此，首先应该把圆盘A和B移到柱子2上。然后才能够进行关键的一步，把圆盘C从柱子1移至柱子3，并继续解决难题的其余部分。将原始难题归约（简化）为下列子难题：移动圆盘A和B至柱子2的双圆盘难题，如图(a)所示。0102把原始难题归约（简化）为以下三个子难题：移动圆盘A和B至柱子2的双圆盘难题；如图(a)所示移动圆盘C至柱子3的单圆盘难题；如图(b)所示移动圆盘A和B至柱子3双圆盘难题；如图(c)所示梵塔问题归约图：子问题2可作为本原问题考虑，因为它的解只包含一步移动。应用一系列相似的推理，子问题1和子问题3也可被归约为本原问题，如图2.10所示。这种图式结构，叫做与或图(AND/ORgraph)。它能有效地说明如何由问题归约法求得问题的解答。把一个问题描述变换为一个归约或后继问题描述的集合，这是由问题归约算符进行的。变换所得所有后继问题的解就意味着父辈问题的一个解。所有问题归约的目的是最终产生具有明显解答的本原问题。这些问题可能是能够由状态空间有哪些信誉好的足球投注网站中走动一步来解决的问题，或者可能是别的具有已知解答的更复杂的问题。一般地，我们用一个类似图的结构来表示把问题归约为后继问题的替换集合，这种结构图叫做问题归约图，或叫与或图。如下图所示:一些关于与或图的术语：父节点、子（后继）节点、弧线、起始节点。终叶节点：对应于原问题的本原节点。或节点：只要解决某个问题就可解决其父辈问题的节点集合，如（M，N，H）。与节点：只有解决所有子问题，才能解决其父辈问题的节点集合，如（B,C)和（D,E,F）各个结点之间用一端小圆弧连接标记。与或图：由与节点及或节点组成的结构图。问题求解技术两个主要的方面**问题的表示：如果描述方法不对，对问题求解会带来很大的困难求解的方法：采用试探有哪些信誉好的足球投注网站方法。状态空间法三要点**状态（state）：表示问题解法中每一步问题状况的数据结构；1算符（operator）：把问题从一种状态变换为另一种状态的手段；2状态空间方法：基于解答空间的问题表示和求解方法，它是以状态和算符为基础来表示和求解问题的。3要完成某个问题的状态描述，必须确定三件事：该状态描述方式，特别是初始状态描述；操作符集合及其对状态描述的作用；目标状态描述的特性。定义:**状态(state)：为描述某类不同事物间的差别而引入的一组最少变量q0，q1，…，qn的有序集合，其矢量形式如下：式中每个元素qi(i=0,1，…，n)为集合的分量，称为状态变量。给定每个变量的一组值就得到一个具体的状态，如Qk=[q0k，q1k，...，qnk]T它只是问题所有可能状态的罗列，还必须描述这些状态之间的可能变化。所谓操作，或称为算子是引起状态中的某分量发生改变，从而使问题由一个具体状态A变化为另一具体状态B的作用。算符：使问题从一种状态变化为另一种状态的手段称为操作符或算符。操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。01问题的状态空间(statespace)：是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即所有可能的问题初始状态集合S(初始状态S0∈S)、操作符集合F以及目标状态集合G(G?S)。可把状态空间记为三元状态(S，F，G)。02状态空间可用有向图来表示03状态空间的一个解使一个有限的操作算子序列，它使初始状态转化为目标状态：S0-f1-S1-f2-...fk-G如何把初始棋局变换为目标棋局呢？问题的解答就是某个合适的棋子走步序列，如左移棋子12，下移棋子15，右移棋子4，…等等。让我们先用数码难题(puzzleproblem)来说明状态空间表示的概念。由15个编有1至15并放在4×4方格棋盘上的可走动的棋子组成。棋盘上总有一格是空的，以便可能让空格周围的棋子走进空格，这也可以理解为移动空格。图中绘出了两种棋局，即初始棋局和目标棋局，它们对应于该下棋问题的初始状态和目标状态。（a）初始棋局（b）目标棋局十五数码难题141021368571231154911151413121110987654321030201总状态为16!＝20922789888000由