人、狼、羊、菜渡.ppt

人、狼、羊、菜渡河问题一个摆渡人 F 希望用一条小船把一只狼 W ,一头羊 G 和一篮白菜 C 从一条河的左岸渡到右岸去,而船小只能容纳 F,W,G,C 中的两个,决不能在无人看守的情况下,留下狼和羊在一起,羊和白菜在一起,应怎样渡河才能将狼、羊、白菜都运过去? 这是一个有趣的智力游戏问题,虽然可以用递推的方法解决,但我们把此问题化为状态转移问题来解决。可取状态: 将人、狼、羊、菜依次用一个四维向量表示,当一物在左岸时,记相应的分量为 1, 否则记为 0,如 A(1,0,1,0) 表示人和羊在左岸, 并称为一个状态,则根据问题中的限制条件知有些状态是允许的,有的是不允许的, 凡系统可以允许存在的状态称为可取状态。 B(1,1,1,0) 及 C(0,0,1,1) ? 可取运载: 把每运载一次也用一个四维向量来表示,如 D(1,1,0,0) 表示人和狼在船上,而羊和白菜不在船上,这自然是可取的运载,因为船可以载两物,而 E(1,0,1,1) 则是不可取的运载。?可取状态(共 10 个) ?(1,1,1,1)(0,0,0,0) ?(1,1,1,0)(0,0,0,1) ?(1,1,0,1)(0,0,1,0) ?(1,0,1,1)(0,1,0,0) ?(1,0,1,0)(0,1,0,1) ?可取运载(共四个) ?( 1,1,0,0 ) ?( 1,0,1,0 ) ?( 1,0,0,1 ) ?( 1,0,0,0 ) 可取状态为什么成对出现? 可取运算: ?规定 A和B 相加时对每一分量按二进制法则进行。这样,一次渡河就是一个可取状态向量与一个可取运载向量相加。若可取状态经过加法运算后仍是可取状态,这种运算称为可取运算。问题转化为:从初始状态(1,1,1,1) 经过多少次( 奇数) 可取运算才能转化为状态(0,0,0,0) 。如果一个状态可取就标注 Y ,否则标注 N ,虽可取但重复标注 C, 于是问题可用穷举法解答如下: N N N Y????????????????)1,1,1,0( )0,1,1,0( )1,1,0,0( )1,0,1,0()0,0,0,1( )1,0,0,1( )0,0,1,1( )0,1,0,1()1,1,1,1()1( Y N N C ????????????????)1,0,1,1( )0,0,1,1( )1,1,0,1( )1,1,1,1()0,0,0,1( )1,0,0,1( )0,0,1,1( )0,1,0,1()1,0,1,0()2( C Y Y N ????????????????)1,0,1,0( )0,0,1,0( )1,0,0,0( )1,1,1,0()0,0,0,1( )1,0,0,1( )0,0,1,1( )0,1,0,1()1,0,1,1()3( N N C Y????????????????)1,0,0,1( )0,0,0,1( )1,0,1,1( )1,1,0,1()0,0,0,1( )1,0,0,1( )0,0,1,1( )0,1,0,1()1,0,0,0()4( 1N C N Y????????????????)0,0,1,1( )1,0,1,1( )0,0,0,1( )0,1,1,1()0,0,0,1( )1,0,0,1( )0,0,1,1( )0,1,0,1()0,0,1,0(