文档介绍：状态空间表示法例:设N个传教士带领N个野人划船渡河,且为安全起见,渡河需遵循两个约束:(1)船上的人数不得超过载重限量,设为K个人;(2)为预防野人攻击,任何时刻(包括两岸、船上)野人数目不得超过传教士数目。应如何规划渡河方案?为便于理解状态空间表示法,可简化该问题到一个特例:N=3,K=2。解:首先选取描述问题状态的方法。在这个问题中,需要考虑两岸的修道士人数和野人数,还需要考虑船在左岸还是在右岸。从而可用一个三元组来表示状态S=(m,c,b)其中,m表示左岸的修道士人数,c表示左岸的野人数,b表示左岸的船数。右岸的状态可由下式确定:右岸修道士数m'=3-m右岸野人数c'=3-c右岸船数b'=1-b在这种表示方式下,m和c都可取0、1、2、3中之一,b可取0和1中之一。因此,共有4×4×2=32种状态。这32种状态并非全有意义,除去不合法状态和修道士被野人吃掉的状态,有意义的状态只有16种:S0=(3,3,1)S1=(3,2,1)S2=(3,1,1)S3=(2,2,1)S4=(1,1,1)S5=(0,3,1)S6=(0,2,1)S7=(0,1,1)S8=(3,2,0)S9=(3,1,0)S10=(3,0,0)S11=(2,2,0)S12=(1,1,0)S13=(0,2,0)S14=(0,1,0)S15=(0,0,0)有了这些状态,还需要考虑可进行的操作。操作是指用船把修道士或野人从河的左岸运到右岸,或从河的右岸运到左岸。每个操作都应当满足如下条件:一是船至少有一个人(m或c)操作,离开岸边的m和c的减少数目应该等于到达岸边的m和c的增加数目;二是每次操作船上人数不得超过2个;三是操作应保证不产生非法状态。因此,操作应由条件部分和动作部分:条件:只有当其条件具备时才能使用动作:刻划了应用此操作所产生的结果。操作的表示:用符号Pij表示从左岸到右岸的运人操作用符号Qij表示从右岸到左岸的操作其中:i表示船上的修道士人数j表示船上的野人数操作集本问题有10种操作可供选择:F={P01,P10,P11,P02,P20,Q01,Q10,Q11,Q02,Q20}下面以P01和Q01为例来说明这些操作的条件和动作。操作符号条件动作P01b=1,m=0或3,c≥1b=0,c=c-1Q01b=0,m=0或3,c≤2b=1,c=c+1于是,从初始状态出发,可画出该问题的状态空间有向图,。二阶梵塔问题设用Sk=(Sk0,Sk1)表示问题的状态,Sk0表示金片A所在钢针号,Sk1表示金片B所在钢针号,全部可能的状态有九种:S0=(1,1),S1=(1,2),S2=(1,3)S3=(2,1),S4=(2,2),S5=(2,3)S6=(3,1),S7=(3,2),S8=(3,3)问题的初始状态集合为S={S0}目标状态集合为G={S4,S8}初始状态S0和目标状态S4、S8如图所示操作分别用A(i,j)和B(i,j)表示A(i,j)表示把金片A从第i号钢针移到j号钢针上;B(i,j)表示把金片B从第i号钢针一到第j号钢针上。共有12种操作,它们分别是:A(1,2)A(1,3)A(2,1)A(2,3)A(3,1)A(3,2)B(1,2)B(1,3)B(2,1)B(2,3)B(3,1)B(3,2)根据上述9种可能的状态和12种操作,可构成二阶梵塔问题的状态空间图,如下图所示。·s---指示初始状态节点;G---指示搜索图;·OPEN---用于存放待扩展节点的表;·CLOSE---用于存放已扩展节点的表;·FIRST(OPEN)---指示取OPEN表首的节点作为当前要被扩展的节点n;·REMOVE(n,OPEN)---将节点n从OPEN表中删去;·ADD(n,CLOSE)---把节点n加入到CLOSE表中;·EXPAND(n)---扩展节点n。深度优先宽度优先在3×3的方格棋盘上,分别放置了表有数字1、2、3、4、5、6、7、8的八张牌,初始状态S0,目标状态Sg,如下图所示。可以使用的操作有空格左移,空格上移,空格右移,空格下移即只允许把位于空格左、上、右、下方的牌移入空格。要求应用宽度优先和深度优先搜索策略寻找从初始状态到目标状态的解路径。评价函数的格式:f(n)=g(n)+h(n)f(n):评价函数h(n):启发函数·g*(n):从初始结点s到结点n的最短路径的耗散值;·h*(n):从结点n到目标结点g的最短路径的耗散值;·f*(n)=g*(n)+h*(n):从初始结点s经过结点n到目标结点g的最短路径的耗散值;·g(n)、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)的估计值。在A算法中,如果满足条件:h(n)≤h*(n)则A算法称为A*算法。解树的耗散值可按如下规则计算:(1)若n为终止节点,则其代价h(n)=0;(2)若n为或节点,且