




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、1,2.2.1人、狼、羊、菜渡河问题,问题提出,一个摆渡人F希望用一条小船把一只狼W、一只羊G和一篮白菜C从一条河的左岸渡到右岸去,而船小只能容纳F、W、G、C中的两个,由于狼会吃羊,羊会吃白菜,在运送的过程中决不能在无人看守的情况下,留下狼和羊,羊和白菜在一起,应该如何渡河才能将狼、羊、白菜都运过河?,2,这是一个有趣的智力游戏问题,可以用推理的方法解决,但比较抽象,不易理解,如果建立数学模型,进行数学化把此问题化为状态转移问题来解决,显得直观且通俗易懂。,建立模型,将人、狼、羊、白菜在左岸的状态依次用一个四维向量表示,设一物在左岸时记相应的分量为1,否则记为0,如A(1,0,1,0)表示人
2、和羊在左岸,没有狼和白菜,并成为一个状态,,3,如果全部运到右岸,这时在左岸的状态是(0,0,0,0)根据数学中的乘法原理可得,共有2222=22=16种,但由问题中限制的条件可知有的状态是允许的,而有的状态是不允许的,凡是问题条件允许存在的状态称为可取状态,如(1,0,1,0)(即人和羊在一起)是一个可取状态,但(0,0,1,1)(羊和白菜在一起)是一个不可取状态。,4,一、可取状态 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) 右边五个正好是左边五个的相反状态。,5,(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),6,三、加减运算规则 规定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)。这就把一个实际问题转化为进行可取加减运算的数学问题了。,7,模型运算,如果一个状态是可取的就打“”,否则就打“”,虽然可取但已出现过的状态打“E ”,每次运去用减法,每次运回用加法,于是问题可利用穷举法解答如下:,初始状态 可行运载(去) 运载后左边状态,8,运去后左边状态 可行运载(回) 当前左边状态,9,10,11,第七步出现了(0,
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 私人田地买卖合同协议书
- 混凝土工合同分包协议书
- 空压机出租租赁合同范本
- 食堂托管承包协议书范本
- 瓷砖墙改造租房合同范本
- 申请签订意向协议书范本
- 机械技术学徒培训协议书
- 电梯广告发布协议书范本
- 独家合作分发协议书范本
- 船舶清洁合同协议书范本
- 以人民为中心思想存在问题
- 2023年重庆市大渡口区八桥镇社区工作人员考试模拟题及答案
- GB/T 19466.1-2004塑料差示扫描量热法(DSC)第1部分:通则
- GB/T 18606-2001气相色谱-质谱法测定沉积物和原油中生物标志物
- GB 2811-1989安全帽
- 《中国近现代史纲要》 课件 第十一章 中国特色社会主义进入新时代
- 金字塔原理(完整版)
- “扬子石化杯”第36届中国化学奥林匹克(初赛)选拔赛暨2022年江苏赛区复赛试题及答案
- 公共经济学ppt课件(完整版)
- 浙江省引进人才居住证申请表
- DB62∕T 4134-2020 高速公路服务区设计规范
评论
0/150
提交评论