人狼羊菜安全渡河问题_第1页
人狼羊菜安全渡河问题_第2页
人狼羊菜安全渡河问题_第3页
全文预览已结束

下载本文档

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

文档简介

人、狼、羊、菜安全渡河问题摘要羊过麟问题箜一人能羊疆题西乘具繇篱篇1菜题蠡渺岸问题分析设图的顶点v=(m,n,p,q),m表示人，n代表狼，p代表羊，q代表白菜，且m,n,p,qe{-1,0,1},-1代表此岸，0代表船上，1代表彼岸。根据题意，问题变成了找出从顶点(-1,-1,-1,-1)到顶点(1,1,1,1)路径(即是一棵以(-1,-1,-1,-1)为根结点，(1,1,1,1,)为叶子结点的树)的问题。通过分析问题知道：顶点v必须满足以下条件：当m^0时，n,p,q尹0因为乘船时必须有人在上面；当mUp时，n尹p,q尹p即当人与羊不在一起时，必羊和狼不在一起，羊和菜不在一起；当n、p、q中有一个为0时其余两个都不能为0.设相邻顶点Vi=(m1,n1,p1,q1),Vj=(m2,n2,p2,q2).设Tm=m2-m1,Tn=n2-n1,Tp=p2-p1,Tq=q2-q1,易见TU(-1,0,1)，因为状态必须是渐变的，不能逾越中间一个状态。路径应该满足以下条件：|Tm|乂0,即人前后的状态必须改变；|Tn|+|Tp|+|Tq|=0或=1,因为最多仅能有一个物品随人转移，可以为0是因为允许人一个物品都不带；当|Tn|+|Tp|+|Tq|=1时设状态改变的物品为x,必有Tx=Tm，因为物体状态的改变必是人状态改变的结果，且与人的改变方向一致。根据上述规则建立符合条件的树：用穷举法产生81个顶点；由顶点法则排除不合理点，还剩k个可行点；3，用（-1，-1，-1，-1）和（1，1，1，1）分别作为根结点和叶子结点;用路径法则选取正确点：从（-1，-1，-1，-1）为起点开始从剩下的k-1-1个可行顶点中找到合理点，再以此点为新的起点从剩下的k-1-1-1个可行点中按路径法则找合理点……以此类推找到最后一个合理点为（1，1，1，1）。最后结果如图所示： -(-1-1-1-1)（0，-1,0，-1）（1，-1,1，-1）（0，-1,1，-1）(-1,-1,1,-1)（0,0,1，-1）(0,-1,1,0)（1,1,1，-1）(1,-1,1,1)(0,1,0,-1)(0,-1,0,1)(-1,1,-1,-1)(-1,-1,-1,1)(0,1-1,0)(0,0,-1,1)(1,1,-1,1)[(0,1,-1,1)(-1,1,-1,1)L(0,1,0,1)(1,1,1,1)参考文献［1］ 郭强，孙浩.运筹学原理与算法［M］西安:西北工业大学出版社，2006.［2］ 严蔚敏，吴伟民.数据结构［M］.北京：清华大学出版社，2002.［3］ 俞涛.“船运狼，羊，菜”问题的新解法［J］.河北师范大学学报:自然科学版，1996,20（4）：27-29.［4］ 王家华，/r

人人文库> 全部分类> 图纸下载 > 毕业设计

温馨提示

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

最新文档

评论

0/150

提交评论