状态空间暗示法例：设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,≥c1b=0,c=c-1Q01b=0,m=0或3，c≤2b=1,c=c+1于是，从初始状态出发，可画出该问题的状态空间有向图，见图1.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颠末