51.2状态空间法 3.状态空间的例子(111) 例5.1二阶梵塔问题。设有三根钢针,它们的编号分别是 1号、2号和3号。在初始情况下,1号钢针上穿有A、B两个 金片,A比B小,A位于B的上面。要求把这两个金片全部移 到另一根钢针上,而且规定每次只能移动一个金片,任何时 刻都不能使大的位于小的上面 解:设用S=(S10,S1)表示问题的状态,其中,S0表示金 片A所在的钢针号,S1表示金片B所在的钢针号。全部可能 的问题状态共有以下9种: 0=(1,1)S1=(1,2)S2=(1,3)S3=(2,1)S5=(2,2) S=(2,3)S6=(3,1)S1=(3,2)S8=(3,3)
例5.1 二阶梵塔问题。设有三根钢针，它们的编号分别是 1号、2号和3号。在初始情况下，1号钢针上穿有A、B两个 金片，A比B小，A位于B的上面。要求把这两个金片全部移 到另一根钢针上，而且规定每次只能移动一个金片，任何时 刻都不能使大的位于小的上面。 解：设用Sk=(Sk0, Sk1)表示问题的状态，其中，Sk0表示金 片A所在的钢针号，Sk1表示金片B所在的钢针号。全部可能 的问题状态共有以下9种： S0=(1, 1) S1=(1, 2) S2=(1, 3) S3=(2, 1) S5=(2, 2) S5=(2, 3) S6=(3, 1) S7=(3, 2) S8=(3, 3) 5.1.2 状态空间法 3. 状态空间的例子(1/11) 6
512状态空间法 3.状态空间的例子(2/11) 问题的初始状态集合为S={S0 目标状态集合为G={S,S5} 初始状态S和目标状态S4S如图所示 A B B B 123 123 S0=(1,1) S=(2,2) S3=(3,3) 二阶梵塔问题的初始状态和目标状态
A B A B A B 1 2 3 1 2 3 1 2 3 二阶梵塔问题的初始状态和目标状态 问题的初始状态集合为S={S0 } 目标状态集合为G={S4 , S5 } 初始状态S0和目标状态S4、S8如图所示 S0=(1, 1) S4=(2, 2) S8=(3, 3) 5.1.2 状态空间法 3. 状态空间的例子(2/11) 7
512状态空间法 3.状态空间的例子(3/11) 操作分别用A(和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种操作,可构成二阶梵塔问题的 状态空间图,如下图所示
操作分别用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种操作，可构成二阶梵塔问题的 状态空间图，如下图所示。 5.1.2 状态空间法 3. 状态空间的例子(3/11) 8
A(1,2 A(1,3) (3,1) B(1,3 B(1,2) 2,3) (3,2) A(2,3 A(3,2) (3,3) (2,2) 二阶梵塔的状态空间图 从初始节点(1,1到目标节点(2,2)及(3,3的任何一条路径都是问题的 个解。其中,最短的路径长度是3,它由3个操作组成。例如,从(1,1)开始, 通过使用操作A(1,3)、B1,2)及A(3,2),可到达(3,3)
(3,3) (1,3) (1,2) (2,2) 二阶梵塔的状态空间图 从初始节点(1, 1)到目标节点(2, 2)及(3, 3)的任何一条路径都是问题的一 个解。其中，最短的路径长度是3，它由3个操作组成。例如，从 (1, 1)开始， 通过使用操作A(1, 3)、B(1, 2)及A(3, 2)，可到达 (3, 3)。 A(1,2) B(1,3) A(2,3) (1,1) (3,1) (3,2) (2,1) (2,3) A(1,3) B(1,2) A(3,2) 9
512状态空间法 3.状态空间的例子(5/11) 例52修道士( Missionaries)和野人( Cannibals)问题(简称 MC问题)。 设在河的一岸有三个野人、三个修道士和一条船,修道士想 用这条船把所有的人运到河对岸,但受以下条件的约束: 是修道士和野人都会划船,但每次船上至多可载两个人 二是在河的任一岸,如果野人数目超过修道士数,修道士会 被野人吃掉。 如果野人会服从任何一次过河安排,请规划一个确保修道士 和野人都能过河,且没有修道士被野人吃掉的安全过河计划
例5.2 修道士(Missionaries)和野人(Cannibals)问题(简称 M-C问题)。 设在河的一岸有三个野人、三个修道士和一条船，修道士想 用这条船把所有的人运到河对岸，但受以下条件的约束： 一是修道士和野人都会划船，但每次船上至多可载两个人； 二是在河的任一岸，如果野人数目超过修道士数，修道士会 被野人吃掉。 如果野人会服从任何一次过河安排，请规划一个确保修道士 和野人都能过河，且没有修道士被野人吃掉的安全过河计划。 5.1.2 状态空间法 3. 状态空间的例子(5/11) 10