图搜索状态空间表示

1、图搜索状态空间图11 状态空间及其搜索的表示 1）状态空间的表示 状态空间以SP指示，其可表示为一个二元组： SP = （S, O） S在问题求解（即搜索）过程中所有可达的合法状态构成的集合； O操作算子的集合，操作算子的执行导致状态的变迁。 状态空间又可描述为一个有向图： 节点：指示状态， 节点间的有向弧：表示状态变迁， 弧上的标签：指示导致状态变迁的操作算子。 状态可通过定义某种数据结构来描述，用于记载问题求解（即搜索）过程中某一时刻问题现状的快照。 21 状态空间及其搜索的表示2）状态空间表示的经典例传教士和野人问题 N个传教士带领N个野人划船渡河， 安全约束： 1）船上人数不得超过载重

2、限量，设为K个人， 2）为预防野人攻击，任何时刻（包括两岸、船上）野人数目不得超过传教士。 特例：N=3，K=2； 变量m传教士在左岸或船上的实际人数， 变量c野人在左岸或船上的实际人数， 变量b指示船是否在左岸（1、0）。 上述约束条件转变为m + c 2, m c。 左岸状态描述为一个三元组： （m, c, b） 考虑到在这个渡河问题中，左岸的状态描述（m, c, b）可以决定右岸的状态，所以整个问题状态就可以左岸的状态来描述，以简化问题的表示。 设初始状态下传教士、野人和船都在左岸，目标状态下这三者均在右岸，问题状态以三元组（m,c,b）表示。 32）状态空间表示的经典例传教士和野人问题

3、 问题求解任务可描述为： （3，3，1） （0，0，0） 该简单问题的状态空间： 可能的状态总数为442 = 32 ， 只有20个状态是合法的（遵守安全约束）， 不合法状态， （1，0，1）， （1，2，1）， （2，3，1） 不可达的合法状态（4个）， （0，0，1）， （0，3，0）。 总共只有16个可达的合法状态。 2类操作算子： L(m,c)指示从左岸到右岸的划船操作， R(m,c)指示从右岸回到左岸的划船操作， m和c取值的可能组合只有5个：10，20，11，01，02。 总共有10个操作算子。 42）状态空间表示的经典例传教士和野人问题 渡河问题状态空间的有向图： 参见图2.151

4、 状态空间及其搜索的表示3）状态空间的搜索 状态空间的搜索以SE指示，其可表示为1个五元组： SE = (S,O,E,I,G) E搜索引擎； I问题的初始状态，I S; G问题的目标状态集，G S。 基本思想通过搜索引擎寻找一个操作算子的调用序列，使问题从初始状态变迁到目标状态之一。 解答路径初-目变迁过程中的产生的状态序列或相应的操作算子调用序列。 搜索引擎可以设计为任意实现搜索算法的控制系统。 状态空间的解答路径有多条，由于一个状态可以有多个可供选择的操作算子： 渡河问题就有无数条解答路径（因为划船操作可逆），但只有4条是最短的，都包含11个操作算子的调用。 状态空间一般都表示为或图也称一

5、般图 操作算子的可选（渡河问题的初始状态节点就有3个），在逻辑上称为“或”关系，意指只要其中有一条路径通往目标状态，就能获得成功解答。除了少数像渡河这样的简单问题外，描述状态空间的一般图都很大，无法直观地画出，只能将其视为隐含图。 搜索图在搜索解答路径的过程中只画出搜索时直接涉及到的节点和弧线，构成所谓的搜索图。 61 状态空间及其搜索的表示4）一般图搜索例八数码游戏 33九宫棋盘，放置数码为1 - 8的8个棋牌，剩下一个空格，只能通过棋牌向空格的移动来改变棋盘的布局。 求解的问题给定初始布局（即初始状态）和目标布局（即目标状态），如何移动棋牌才能从初始布局到达目标布局（参见图2.2）。 解答

6、路径就是一个合法的走步序列。 用一般图搜索方法解决该问题： 为问题状态的表示建立数据结构：33的一个矩阵， * 矩阵元素S ij0,1,8；其中1i,j3， * 数字0指示空格， * 数字1 - 8指示相应棋牌。 1 0 3 1 2 3 图2.2中的八数码问题就可表示为： 7 2 4 8 0 4 6 8 5 7 6 5 74）一般图搜索例八数码游戏 制定操作算子集：* 直观方法为每个棋牌制定一套可能的走步： 左、上、右、下四种移动， 这样就需32个操作算子。* 简易方法仅为空格制定这4种走步， 因为只有紧靠空格的棋牌才能移动。* 空格移动的唯一约束是不能移出棋盘。 八数码问题的搜索图： 参见图2.3 棋盘布局（问题状态）总共9!=362880个， 但搜索图小得多。81 状态空间及其搜索的表示5）状态空间、搜索