通过例子引入状态图的概念：一个简单的例子：设有三枚钱币，其排列处在“正，正，反”状态，现允许每次可翻动其中任意一个钱币，问只允许操作三次的情况下，如何翻动钱币使其变成“正，正，正”或“反，反，反”状态。若“正面”用“1”表示，“反面”用“0”表示，则问题化成求解从初始状态（1,1,0）到目标状态（1，1，1）或(0,0,0)的路径问题，且该路径的长度为3。（1，1，0）--------->（1，1，1）或（1,1,0）--------->（0,0,0）

另一个例子--八数码问题（8-puzzle problem）在一个3*3的方格棋盘上放置着1，2，3，4，5，6，7，8八个数码，每个数码占一个格，且有一个空格。这些数码可在棋盘上移动，其移动规则是：与空格相邻的数码方可移入空格。现在的问题是对于给定的初始棋局和目标棋局（如下图），给出移动的序列。

ab

以上两问题虽然内容不同，但抽象地来看，它们都是在某个有向图中寻找目标或路径的问题。人工智能科学中，把这种描述问题的有向图称为状态空间图，简称状态图（state diagram）。因为图中的一个结点(node)代表问题中的一种格局或状态；边表示两个结点之间的某种联系（某种操作、规则、变换、算子、通道或关系）。在状态图中，从初始结点到目标结点的一条路径或者所找到的目标结点就是相应的一个解。许多智力问题（Hanoi塔，旅行商问题，N皇后问题，农夫过河问题）都可以归结成状态图问题。例子一的状态图：

.

例子二的部分状态图：

练习：N皇后问题就是在N*N的棋盘上放置N个皇后的方法解，满足每行、每列和对角线上只允许出现一个皇后，例如以下是8皇后问题的解。要求画出4皇后问题的状态空间图，然后求解目标。Q x x x x x x x x x x x Q x x x x x x x x x x Q x x x x x Q x x x x Q x x x x x x x x x x x Q x x Q x x x x x x x x x Q x x x x