状态空间的概念和表示方法

状态空间的概念和表示方法1状态空间问题举例首先让我们看下面两个例子：八数码问题，也叫重排九宫问题。在一个3×3的方格棋盘上放置着1，2，3，4，5，6，7，8八个数码，每个数码占一格，余下的一个是空格。这些数码可在棋盘上移动。移动规则是：与空格相邻的数码方可移入空格。问题的目标是：对于指定的初始棋局通过移动数码块，得到目标棋局（如图所示），要求给出数码的移动步骤。2状态空间的基本概念和特点首先我们引入状态空间的几个基本概念。1.状态状态是描述问题在求解过程中任意一确定时刻的状况，它表征了问题特征和结构等。如，在八数码问题中，可以把棋局看成状态。那么初始棋局就是初始状态，目标棋局为目标状态。在迷官问题中，k在S，可以看作一种状态，它是初始状态k在S，也是一种状态，k到了S，是目标状态。2.状态转换规则状态转换规则就是能使问题由一种状态改变为另一种状态的条件和操作。在八数码问题中，可以定义四条移动规则：邻接空格的数码可以右移一格、左移一格、上移一格或下移格。利用这些规则可以使八数码棋局从一个状态转换到另一个状态。0g43.状态空间状态空间是指问题的全部状态及一切可用的状态转换规则所集合。如何用状态空间表示法表示问题呢？我们以八数码问题为例介绍这种表示方法。状态：一个问题的起始状态称为初始状态，要达到的最终目标称为目标状态，八数码问题的初始状态（S）为初始棋局，目标状态（S）为目标棋局。如下图所示。0g八数码问题的所有的状态和状态转换规则构成的集合就是八数码问题的状态空间。将八数码问题用状态空间表示出来就是八数码问题的状态空间表示。一般人工智能问题的状态空间都非常大，最简单的八数码问题就会有362880（9!）种状态。

4.状态图状态空间也可以用图的形式来表达出来，这种图称为状态空间图，简称状态图。其中，节点表示状态；有向边（弧）表示状态转换规则，八数码问题的状态空间图，图中有S、S至S共34个节点，即八数码问题中的34个状态。因为八数码问题的状态数量非常大，在这里只两出状态图的部分。0133

5.用Prolog语言描述状态空间用状态空间表示法表示问题的一个优点是此表示法易于计算机语言实现。在第三章中，我们学习了一种人工智能语言——Prolog语言。我们可不可以用Prolog来描述问题的状态空间呢？3状态空间问题求解的基本方法把所求解的问题用状态空间的形式表示出来以后，原来的问题求解就转化为对状态空间问题的求解，对状态空间问题的求解过程其实就是一个搜索过程。从初始状态开始，不断地应用规则，从一个状态转变为另一个状态，最后达到目标状态为止，这种求解过程称为状态空间法。要使用状态空间法解决问题，首先要用一定的数据结构，比如字符串、数组、矩阵、树、表、集合等，来描述状态空间，在确定了一个合适的数据结构后，一个状态就对应该结构的一个确定的值，这种方法也叫做状态描述。例如，八数码问题既可以通过矩阵，又可用数组来描述。对于状态空间表示的问题，其求解过程可以归结为对状态空间的搜索。搜索技术，特别是启发式搜索技术在人工智能领域中，是问题求解的主要方法之一，一直受到高度重视，一些著名的人工智能程序，如纽厄尔、肖和西蒙的“LogicTheorist”、通用问题求解程序GPS，塞缪尔的跳棋程序“Checkers”，格林布莱特的国际象棋程序等都是采用搜索技术来解决问题的程序。今天，搜索技术已广泛应用于自然语言理解、自动程序设计、模式识别、机器人学、专家系统、数学定理自动证明、博弈和信息检索等众多领域。在状态空间法中，基于问题解决效率方面的原因，通常，不是把问题的全部状态空间图直接存入计算机，而是仅仅在计算机中存入关于该问题的各种知识，再根据推理（或搜索）的需要，逐步生成问题的状态空间图。在计算机中，根据有关知识逐步产生问题的状态空间图，并检索所产生的状态空间是否也包含了目标状态，这一过程被称作搜索过程。决定搜索过程怎样进行，即搜索策略的选定主要取决于如何选取规则。选取规则有两种基本方式：一种是不考虑问题所具有的特定知识，系统根据事先确定的某