习题 状态转移法-人狼羊菜问题_第1页
习题 状态转移法-人狼羊菜问题_第2页
习题 状态转移法-人狼羊菜问题_第3页
习题 状态转移法-人狼羊菜问题_第4页
习题 状态转移法-人狼羊菜问题_第5页
已阅读5页，还剩7页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、.,2.2.1人、狼、羊、菜渡河问题,问题提出,一个摆渡人F希望用一条小船把一只狼W、一只羊G和一篮白菜C从一条河的左岸渡到右岸去，而船小只能容纳F、W、G、C中的两个，由于狼会吃羊，羊会吃白菜，在运送的过程中决不能在无人看守的情况下，留下狼和羊，羊和白菜在一起，应该如何渡河才能将狼、羊、白菜都运过河？,.,这是一个有趣的智力游戏问题，可以用推理的方法解决，但比较抽象，不易理解，如果建立数学模型，进行数学化把此问题化为状态转移问题来解决，显得直观且通俗易懂。,建立模型,将人、狼、羊、白菜在左岸的状态依次用一个四维向量表示，设一物在左岸时记相应的分量为1，否则记为0，如A（1，0，1，0）表示人

2、和羊在左岸，没有狼和白菜，并成为一个状态，,.,如果全部运到右岸，这时在左岸的状态是（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

3、，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

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论