状态空间图 一个简单的例子 设有三枚钱币 其排列处在 正 正 反 状态 现允许每次可翻动其中任意一个钱币 问只允许操作三次的情况下 如何翻动钱币使其变成 正 正 正 或 反 反 反 状态 若 正面 用 1 表示 反面 用 0 表示 则问题化成求解从初始状态 1 1 0 到目标状态 1 1 1 或 0 0 0 的路径问题 且该路径的长度为3 1 1 0 1 1 1 或 1 1 0 0 0 0 状态图 传教士和野人问题 1 综合数据库 用三元组表示 即 ML CL BL 其中0 ML CL 3 BL 0 1 此时问题述简化为 3 3 1 0 0 0 状态空间的总状态数为4 4 2 32 根据约束条件的要求 可以看出只有20个合法状态 状态空间图 人工智能科学中 把这种描述问题的有向图称为状态空间图 简称状态图 statediagram 因为图中的一个结点 node 代表问题中的一种格局或状态 边表示两个结点之间的某种联系 某种操作 规则 变换 算子 通道或关系 在状态图中 从初始结点到目标结点的一条路径或者所找到的目标结点就是相应的一个解