512状态空间法 3.状态空间的例子(6/11) 解:首先选取描述问题状态的方法。在这个问题中,需要 考虑两岸的修道士人数和野人数,还需要考虑船在左岸还是在 右岸。从而可用一个三元组来表示状态 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种状态
解：首先选取描述问题状态的方法。在这个问题中，需要 考虑两岸的修道士人数和野人数，还需要考虑船在左岸还是在 右岸。从而可用一个三元组来表示状态 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种状态。 5.1.2 状态空间法 3. 状态空间的例子(6/11) 11
这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) S=(3,2,0)S9=(3,1,0)S0=(3,0,0)S1=(2,2,0) 12=(1,1,0)S13=(0,2,0)S14=(0,1,0)S1s=(0,0,0) 有了这些状态,还需要考虑可进行的操作。 操作是指用船把修道士或野人从河的左岸运到右岸,或从河的 右岸运到左岸。 每个操作都应当满足如下条件: 是船至少有一个人(m或c)操作,离开岸边的m和c的减少数 目应该等于到达岸边的m和c的增加数目 二是每次操作船上人数不得超过2个; 是操作应保证不产生非法状态。 因此,操作应由条件部分和动作部分: 条件:只有当其条件具备时才能使用 动作:刻划了应用此操作所产生的结果
这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个； 三是操作应保证不产生非法状态。 因此，操作应由条件部分和动作部分： 条件：只有当其条件具备时才能使用 动作：刻划了应用此操作所产生的结果。 12
操作的表示: 用符号P表示从左岸到右岸的运人操作 用符号Q表示从右岸到左岸的操作 其中: i表示船上的修道士人数 表示船上的野人数 操作集 本问题有10种操作可供选择 F={P01,P10,P1,P02,P20,Q01,Q10,Q1,Q02,Q203 下面以P和Qo为例来说明这些操作的条件和动作。 操作符号条件 动作 b=1,m=0或3,c≥1 b=0,c=c-1 b=0,m=0或3,c≤2b=1,c=c+1
操作的表示： 用符号Pij表示从左岸到右岸的运人操作 用符号Qij表示从右岸到左岸的操作 其中： i表示船上的修道士人数 j表示船上的野人数 操作集 本问题有10种操作可供选择： F={P01, P10, P11, P02, P20,Q01, Q10, Q11, Q02, Q20} 下面以P01和Q01为例来说明这些操作的条件和动作。 操作符号 条件 动作 P01 b=1, m=0或3, c≥1 b=0, c=c-1 Q01 b=0, m=0或3，c≤2 b=1, c=c+1 13
512状态空间法 3.状态空间的例子(9/11) 例5.3猴子摘香蕉问题。在讨论谓词逻辑知识表示时,我们 曾提到过这一问题,现在用状态空间法来解决这一问题。 解:问题的状态可用4元组 X. V. Z 表示。其中: w表示猴子的水平位置; x表示箱子的水平位置; y表示猴子是否在箱子上, 当猴子在箱子上时,y取1, 否则y取0; z表示猴子是否拿到香蕉, 当拿到香蕉时z取1,否则z取 b
a c b 例5.3 猴子摘香蕉问题。在讨论谓词逻辑知识表示时，我们 曾提到过这一问题，现在用状态空间法来解决这一问题。 解：问题的状态可用4元组 （w, x, y, z） 表示。其中： w表示猴子的水平位置； x表示箱子的水平位置； y表示猴子是否在箱子上， 当猴子在箱子上时，y取1， 否则y取0； z表示猴子是否拿到香蕉， 当拿到香蕉时z取1，否则z取 0。 5.1.2 状态空间法 3. 状态空间的例子(9/11) 14
所有可能的状态为 S:(a,b,0,0)初始状态 S1:(b,b,0,0) 2:(c,C,0,0 S3:(c,C,1,0 S;(c,c,1,1)目标状态 允许的操作为 Goto(u):猴子走到位置u,即 (W,x,0,0)→→(u,x,0,0) Pushbox(v):猴子推着箱子到水平位置v,即 (x,x,0,0)-(v,V,0,0 Climbbox:猴子爬上箱子,即 (x,x,0,0)→(x,X,1,0) Grasp;猴子拿到香蕉,即 (c,C,1,0)→(c,C,1,1) 这个问题的状态空间图如下图所示。不难看出,由初始状 态变为目标状态的操作序列为: & Goto(b), Pushbox(c), Climbbox, Grasp 15
所有可能的状态为 S0 : (a, b, 0, 0) 初始状态 S1 : (b, b, 0, 0) S2 : (c, c, 0, 0) S3 : (c, c, 1, 0) S4 : (c, c, 1, 1) 目标状态 允许的操作为 Goto(u)：猴子走到位置u，即 (w, x, 0, 0)→(u, x, 0, 0) Pushbox(v): 猴子推着箱子到水平位置v，即 (x, x, 0, 0)→(v, v, 0, 0) Climbbox: 猴子爬上箱子，即 (x, x, 0, 0)→(x, x, 1, 0) Grasp；猴子拿到香蕉，即 (c, c, 1, 0 )→(c, c, 1, 1) 这个问题的状态空间图如下图所示。不难看出，由初始状 态变为目标状态的操作序列为： {Goto(b), Pushbox(c), Climbbox, Grasp} 15