状态图

状态图是一个带有标签的有向图，并包含状态信息，可用于指示系统中某些路径只能以特定方式遍历。状态图也称为问题空间模型（Atallah 1998, p. 36-2）。例如，在上面的左图中（由 R. 阿伯特创作），一辆汽车必须在遵守所有交通规则且不掉头的情况下穿过城镇。最初，汽车位于位置 4，向东行驶，并且可以选择移动到位置 1，向东行驶，或位置 5，向东行驶。迷宫对应的状态图在上面的右图中示出。

上面展示了由 R. 阿伯特创建的另一个例子。虽然这个迷宫与第一个非常相似，但状态图却不同。因此，这个迷宫说明了系统规则的微小变化会对状态图产生重大影响。

其他谜题、问题和程序使用状态图作为分析工具。例如，15 拼图可以用一个具有 个节点的的状态图表示。