高中信息技术 浙教版选修5 5.1状态空间的概念和表示方法(共13张PPT)

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