小C的第一宇宙
状态空间法
wangc
Nov 17, 2017
阅读本文需要 11 分钟(按字数)

状态空间法

简介

状态空间法是人工智能中最基本的问题求解方法，它所采用的问题表示方法称为状态空间表示法。任何以状态和操作为基础的问题求解方法都可称为状态空间问题求解方法，简称状态空间法。其中，状态空间搜索是一种用状态空间法求解问题时的搜索方法。

基本概念

  • 状态空间(State space)用来描述一个问题的全部状态以及这些状态之间的相互关系。常用一个三元组表示为：(S, F, G)其中，S为问题的所有初始状态集合；F为操作的集合；G为目标状态的集合。状态空间也可用一个赋值的有向图来表示，该有向图称为状态空间图。在状态空间图中，节点表示问题的状态，有向边表示操作。
  • 状态(state)是表示问题求解过程中每一步问题状况的数据结构，它可用如下形式表示：Sk= {Sk0, Skl, •••} 在这种表示方式中，当对每一个分量都给予确定的值时，就得到了一个具体的状态。实 际 上 ， 任何一种类型的数据结构都可以用来描述状态，只要它有利于问题求解，就可以选用。
  • 操作(operator)也称为算符，它是把问题从一种状态变换为另一种状态的手段。当对一个问题状态使用某个可用操作时，它将引起该状态中某些分量值的变化，从而使问题从一个具体状态变为另一个具体状态。操作可以是一个机械步骤、一个运算、一条规则或一个过程。操作可理解为状态集合上的一个函数，它描述了状态之间的关系。

状态空间表示

在状态空间表示法中，问题是用“状态”和“操作”来表示的，问题求解过程是用“状态空间”来表示的。

相关连接：陈述性知识表示方法

状态空间求解

用状态空间法求解问题的基本过程是，首先为问题选择适当的“状态”及“操作 ”的形式化描述方法;然后从某个初始状态出发，每次使用一个“操作”，递增地建立起操作序列，直到达到目标状态为止。此 时 ，由初始状态到目标状态所使用的算符序列就是该问题的一个解。

实例：二阶梵塔问题

二阶梵塔问题。设有三根钢针，它们的编号分别是1号、2号和3号。在初始情况 下，1 号钢针上穿有A和B两个金片，A比B小，A位于B的上面。要求把这两个金片全部移到另一根钢针上，而且规定每次只能移动一个金片，任何时刻都不能使大片位于小片的上面。

解：设用Sk = {SKA, SKB}表本问题的状态，其中，SKA表示金片A所在的钢针号，SKB表示金片B所在的钢针号。全部可能的问题状态共有以下9种： S0 = (1, 1)， S1 = (1 , 2)， S2 = (1, 3)， S3 = (2, 1)，S4 = (2, 2)，S5 = (2, 3)， S6 = (3, 1)， S7 = (3, 2)， S8 = (3, 3)。其中，初始状态S0和目标状态S4，S8如下图所示。

image

问题的初始状态集合为S = {S0}，目标状态集合为G = {S4, S8}。操作分别用Aij和Bij表示。其中，表示把金片A从第i号钢针移到第j号钢针上;Bij表示把金片B从第i号钢针移到第j号钢针上。共有12种操作，它们分别是：A12，A13，A21，A23，A31，A32，B12，B13，B21，B23，B31，B32。

根据上述9种可能的状态和12种操作，可构成二阶梵塔问题的状态空间图，如下图所示。在该图中，从初始节点(1, 1)到目标节点(2, 2)及(3, 3)的任何一条路径都是问题的一个解。其中，最短的路径长度是3，它由3个操作组成。例如，从初始状态(1，1)开始，通过使用操作A13，B12及A32可到达目标状态(2, 2)。

image

状态空间搜索

上述问题求解过程实际上是一个搜索过程，自然的我们可以根据是否使用启发性信息将状态空间搜索方法分为状态空间的盲目搜索和状态空间的启发式搜索。

状态空间的盲目搜索

（关于盲目搜索…） 状态空间的盲目搜索是一种基于问题状态空间表示的盲目搜索算法。根据状态空间采用的数据结构的不同，它可分为图搜索算法和树搜索算法两大类型。由于图搜索算法较为复杂，且一般问题多数都可用树搜索算法解决，这里主要讨论树搜索算法，包括一般树和代价树的盲目搜索算法。

一般树的盲目搜索

广度优先搜索

BFS，其英文全称是Breadth First Search。BFS并不使用经验法则算法。从算法的观点，所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。一般的实验里，其邻居节点尚未被检验过的节点会被放置在一个被称为open的容器中（例如队列或是链表），而被检验过的节点则被放置在被称为closed的容器中。（open-closed表）

这种搜索策略的搜索过程是:从初始节点S。开始逐层向下扩展，在第n层节点还没有全部搜索完之前，不进人第n+1层节点的搜索。Open表中的节点总是按进入的先后排序，先进人Open表的节点排在前面，后进入Open表的节点排在后面。 广度优先捜索算法如下：

  1. 把初始节点S0放入Open表中；
  2. 如果Open表为空，则问题无解，失败退出；
  3. 把Open表的第一个节点取出，放人Closed表，并记该节点为n;
  4. 考察节点W是否为目标节点。若是，则得到问题的解，成功退出；
  5. 若节点n不可扩展，则转第2步；
  6. 扩展节点n，将其子节点放人Open表的尾部，并为每一个子节点设置指向父节点的指针 ，然后转第2步。

深度优先搜索

深度优先搜索算法和广度优先搜索算法的步骤基本相同，它们之间的主要区别 在于，Open表中的节点排序不同。在深度优先算法中，最 后 进 人 Open表的节点总是排在最前面，即后生成的节点先扩展，其具体搜索过程及例子此处省略。

深度优先搜索是一种非完备策略，即对某些本身有解的问题，采用深度优先搜索可能找不到最优解，也可能根本找不到解。常用的解决办法是增加一个深度限制，当搜索达到一定深度但还没有找到解时，停止深度搜索，向宽度发展。这种方法被称为有界深度优先搜索。

状态空间的启发式搜索

（关于启发式搜索…）

A算法

在图搜索算法中，如果能在搜索的每一步都利用估价函数对Open表中的节点进行排序，则该搜索算法为A算法。由于估价函数中带有问题自身的启发性信息， 因此，A算法也被称为启发式搜索算法。

根据搜索过程中选择扩展节点的范围，启发式搜索算法可分为全局择优搜索算法和局部择优搜索算法。其中，全局择优搜索算法每当需要扩展节点时，总是从OPen表的所有节点中选择一个估价函数值最小的节点进行扩展。局部择优搜索算法每当需要扩展节点时，总是从刚生成的子节点中选择一个估价函数值最小的节点进行扩展。下面主要讨论全局择优搜索算法。 全局择优搜索算法的搜索过程可描述如下：

  1. 把初始节点放人Open表中，f(S0）= g(S0）+ h(S0)。
  2. 如果Open表为空，则问题无解，失败退出。
  3. 把Open表的第一个节点取出放人Closed表 ，并记该节点为n。
  4. 考察节点n是否为目标节点。若是，则找到了问题的解，成功退出。
  5. 若节点n不可扩展，则转第（2)步。
  6. 扩展节点n，生成其子节点ni(i=1, 2, …) …），计算每一个子节点的估价值f(ni)(i = 1, 2,…），并为每一个子节点设置指向父节点的指针，然后将这些子节点放人Open表中。
  7. 根据各节点的估价函数值，对Open表中的全部节点按从小到大的顺序重新进行排序。
  8. 转第(2)步。 由于上述算法的第(7)步要对Open表中的全部节点按其估价函数值从小到大重新进行排序 ，这样在算法第(3)步取出的节点就一定是Open表的所有节点中估价函数值最小的一个节点。因此，它是一种全局择优的搜索方式。

对上述算法进一步分析还可以发现:如果取估价函数f(n) = g (n)，则它将退化为代价树的广度优先搜索；如果取估价函数f(n) = g (n)，则它将退化为广度优先搜索。可见，广度优先搜索和代价树的广度优先搜索是全局择优搜索的两个特例。

A*算法

上一节讨论的启发式搜索算法，都没有对估价函数f(n)作任何限制。实际上，估价函数对搜索过程是十分重要的，如果选择不当，则有可能找不到问题的解，或者找到的不是问题的最优解。为此，需要对估价函数进行某些限制，就是对估价函数加上一些限制后得到的一种启发式搜索算法。

假设f*(n)从初始节点S0出发，约束经过节点n到达目标节点Sg的最小代价值。估价函数f(n)则是f*(n)的估计值。显然，f*(n)应由以下两部分所组成:一部分是从初始节点S0到节点n的最小代价，记为，g*(n);另一部分是从节点n到目标节点Sg的最小代价，记为h*(n)，当问题有多个目标节点时，应取其中代价最小的一个。因此有f*(n) = g*(n) + h*(n)。把估价函数f(n)与f*(n)相比，g(n)是对g*(n)的一个估计，h(n)是对h*(n)的一个估计。在这两个估计中，尽管g(n)的值容易计算，但它不一定就是从初始节点S。到节点W的真正最小代价，很有可能从初始节点S。到节点n的真正最小代价还没有找到，故有g(n)≥g*(n)。

有了g*(n)和h*(n)的定义，如果我们对A算法(全局择优的启发式搜索算法）中的g(n)和办h(n)分别提出如下限制：

  • g(n)是对g*(n)的估计，且g(n)>0;
  • h(n)是h*(n)的下界，即对任意节点打均有h(n)≤h*(n)。 则称得到的算法为A*算法 。