习题状态转移法-人狼羊菜问题.ppt

人、狼、羊、菜渡河问题,问题提出,一个摆渡人F希望用一条小船把一只狼W、一只羊G和一篮白菜C从一条河的左岸渡到右岸去，而船小只能容纳F、W、G、C中的两个，由于狼会吃羊，羊会吃白菜，在运送的过程中决不能在无人看守的情况下，留下狼和羊，羊和白菜在一起，应该如何渡河才能将狼、羊、白菜都运过河？,这是一个有趣的智力游戏问题，可以用推理的方法解决，但比较抽象，不易理解，如果建立数学模型，进行数学化把此问题化为状态转移问题来解决，显得直观且通俗易懂。,建立模型,将人、狼、羊、白菜在左岸的状态依次用一个四维向量表示，设一物在左岸时记相应的分量为1，否则记为0，如A（1，0，1，0）表示人和羊在左岸，没有狼和白菜，并成为一个状态，,如果全部运到右岸，这时在左岸的状态是（0，0，0，0）根据数学中的乘法原理可得，共有2222=22=16种，但由问题中限制的条件可知有的状态是允许的，而有的状态是不允许的，凡是问题条件允许存在的状态称为可取状态，如（1，0，1，0）（即人和羊在一起）是一个可取状态，但（0，0，1，1）（羊和白菜在一起）是一个不可取状态。,一、可取状态 A（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，0，0，0）（0，1，1，1）（0，1，1，0）（1，0，0，1）（0，0，1，1）（1，1，0，0）是不可取的6种状态。,二、可行运载B（4种）次序是（人，狼，羊，白菜）（1，0，1，0）（1，1，0，0）（1，0，0，1）（1，0，0，0）,三、加减运算规则规定A（可取状态）与B（可行运载）相加减类似于二进制取尾法则进行运算0+0=0，1+0=1，0+1=1，1+1=0；0-0=0，1-0=1，0-1=1，1-1=0。,问题转化为：从初始状态（1，1，1，1）经过多少次加减运算转化为状态（0，0，0，0）。这就把一个实际问题转化为进行可取加减运算的数学问题了。,模型运算,如果一个状态是可取的就打“”，否则就打“”，虽然可取但已出现过的状态打“E”，每次运去用减法，每次运回用加法，于是问题可利用穷举法解答如下：,初始状态 可行运载（去）运载后左边状态,运去后左边状态 可行运载（回）当前左边状态,第七步出现了（0，0，0，0）状态,实际问题转化为数学游戏问题，再借助规定的数学运算求出结果，即实现建模，易于在计算机上实现,