• 状态空间图表示方法的核心思想：
– 将一个复杂问题表示为若干离散状态
– 将衔接、转移、导致等关系表示为状态之间的连接
– 所有状体和连接构成状态图
状态空间图不一定总能“画出来”，只有两个要素：状态、连接。建立状态空间图，需要：
– 定义状态形式
– 定义状态之间的连接的意义
– 定义问题的解的形式（状态解、路线解、最优值解等）
例 5.1：农夫过河问题
• 农夫、狼、羊、白菜过河的游戏。
– 只有农夫能开船
– 船上只能放 1 个物品
– 没有农夫看管，狼会吃羊，羊会吃白菜
• 如何过河？
Step1：设计状态空间
• 涉及的 4 个对象可以表示为
– N（代表农夫） L（代表狼） Y（代表羊） B（代表白菜）
• 状态表示成 4 维向量，每个分量为 0、1 值，代表 N、L、Y、B，过河的状态，1 为已经过河，0 为未过河。
– 如:（1,1,0,0）表示农夫和狼已经渡河，羊和白菜未渡河。
Step1：设计状态空间
• 该状态空间 多包含 16 种状态。但并不是所有状态都合理。
– 如： 1100 不是一个合理状态，因为羊会吃白菜。
• 实际上，问题只有 10 种合理的状态。
– 0000，0001，0010，0100，0101
– 1010，1011，1101，1110，1111
• 显然，初始状态是 0000，终止状态是 1111
Step2：分析状态转移
• 对于简单问题，建立状态图可以采用“直接法”。
– 从初始状态开始
– 找出所有可能的下一步状态
– 逐步连接，直至达到所有终止状态同时遍历完所有合理状态
Step3：分析解的形式
• 这个问题有明确的“解状态”，
• 即达到（1，1，1，1）状态就成功。
• 同时也是一个“数值优化”的问题
– 少需要几步就能完成？
例 5.2 八格拼图游戏
• 游戏的棋局是由 1 到 8 这 8 个数字的数牌和一个空位排成3∗3 的阵列。
• 要求通过移动数牌，使得该棋局转为标准形式。
• 下面是一个一般 8 数码阵列向标准阵列转换的实例。
Step1：设计状态空间
• 以不同的棋局作为状态。
– 为了方便，可以用矩阵来表示棋局中的位置。
– 如：Sij表示第 i 行、第 j 列的位置：
Step2：定义状态转移
• 认为棋局的改变，是通过移动“空位”来实现的。显然，只有 4 种动作：使空位向上、下、左、右移动，
注意，并非在所有位置都有 4 种移动方式，合理移动规则：
Step3：分析解的形式
• 棋类游戏一般都有明确的结束状态
• 本题的 优解的形式，是“达到结束状态消耗的步数”。因此是数值优化型解。
小结
• 对于简单问题，可以直接构造状态图。
• 对于大多数复杂的问题，状态图无法完全画出，此时清晰定义状态转移的方式，也可以建模。
• 问题的解有很多形式，要有清晰的定义。
• 这样，就完成了状态图的构建，下一节介绍采用何种策略搜索状态空间，来求出问题的解。
