人工智能状态空间问题求解方法

状态空间法的基本思想是用 “状态”和“操作”来表示和求解问题。

状态空间问题表示

在状态空间表示法中&＃xff0c;问题是用“状态”和“操作”来表示的。

状态

状态是表示问题求解过程中每一步状况的数据结构。它可用如下形式表示&＃xff1a;

S_k \ &＃61; \ \{S_{k0},S_{k1},...,S_{kn}\}


当对每一个分量都赋予确定的值时&＃xff0c;就得到了一个具体的状态。

注&＃xff1a;任何一种类型的数据结构都可以用以描述状态&＃xff0c;只要它有利于问题求解&＃xff0c;就可以选用。

操作

操作也可以称为算符&＃xff0c;它是把问题从一种状态转换为另一种状态的手段。

当对一个问题状态使用某个可用操作时&＃xff0c;它将引起该状态中某些分量值的变化&＃xff0c;从而使问题从一个具体状态变为另一个具体状态。

状态空间

状态空间是由一个问题的全部状态&＃xff0c;以及这些状态之间的相互关系所构成的集合&＃xff0c;可用一个三元组&＃xff1a;

(S,F,G)


来表示。其中&＃xff0c;S为问题所有初始状态的集合&＃xff0c;F为操作的集合&＃xff0c;G为目标状态的集合。

状态空间也可用一个赋值的有向图来表示&＃xff0c;该有向图为状态空间图。节点表示问题的状态&＃xff0c;有向边表示操作。

状态空间问题的求解

所有以状态和操作为基础的问题求解方法都可称为状态空间问题求解方法&＃xff0c;简称状态空间法。基本过程是&＃xff1a;

1. 为问题选择适当的“状态”和“操作”的形式化描述方法
2. 从某个初试状态出发&＃xff0c;每次使用一个“操作”&＃xff0c;递增的建立起操作序列&＃xff0c;直到达到目标状态为止

此时&＃xff0c;由初始状态到目标状态所使用的算符序列就是该问题的一个解。

例子

二阶梵塔问题

MC问题&＃xff08;修道士与野人问题&＃xff09;