《5习题 状态转移法-人狼羊菜问题.ppt》由会员分享，可在线阅读，更多相关《5习题 状态转移法-人狼羊菜问题.ppt（12页珍藏版）》请在金锄头文库上搜索。
1、2 2 1人 狼 羊 菜渡河问题 问题提出 一个摆渡人F希望用一条小船把一只狼W 一只羊G和一篮白菜C从一条河的左岸渡到右岸去 而船小只能容纳F W G C中的两个 由于狼会吃羊 羊会吃白菜 在运送的过程中决不能在无人看守的情况下 留下狼和羊 羊和白菜在一起 应该如何渡河才能将狼 羊 白菜都运过河 这是一个有趣的智力游戏问题 可以用推理的方法解决 但比较抽象 不易理解 如果建立数学模型 进行数学化把此问题化为状态转移问题来解决 显得直观且通俗易懂 建立模型 将人 狼 羊 白菜在左岸的状态依次用一个四维向量表示 设一物在左岸时记相应的分量为1 否则记为0 如A 1 0 1 0 表示人和羊在左岸
2、没有狼和白菜 并成为一个状态 如果全部运到右岸 这时在左岸的状态是 0 0 0 0 根据数学中的乘法原理可得 共有2 2 2 2 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 右边五个正好是
3、左边五个的相反状态 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 状态 实际问题转化为数学游戏问题 再借助规定的数学运算求出结果 即实现建模 易于在计算机上实现
