题目
狼羊白菜过河问题 图论
问题:农夫带着狼、羊、白菜从河的左岸到河的右岸,农夫每次只能带一样东西多河,而且,没有农夫看管,狼会吃羊,羊会吃白菜.
提示:利用图论解决问题.(用农夫、狼、羊、白菜及其在左岸还是右岸等表示图中的顶点)
问题:农夫带着狼、羊、白菜从河的左岸到河的右岸,农夫每次只能带一样东西多河,而且,没有农夫看管,狼会吃羊,羊会吃白菜.
提示:利用图论解决问题.(用农夫、狼、羊、白菜及其在左岸还是右岸等表示图中的顶点)
提问时间:2020-08-01
答案
用0表示在左岸,1表示在右岸.
用顶点序号的二进制码的0位表示农夫,1位表示狼,2位表示羊,3位表示菜.
那么,总共可能有16个顶点0-15.顶点0表示全在左岸,顶点15表示全在右岸.
当然有些顶点是不允许存在的,比如顶点3,表示农夫和狼在右岸,羊和菜在左岸,羊会吃掉菜.你要把所有这类的顶点去掉.
在剩下的顶点中,你要找出所有的可能的边.比如顶点5表示农夫和羊在右,狼和菜在左,顶点4表示羊在右,那么就存在顶点5到顶点4的有向边.
至此,图已构造完毕,问题就转换成找到一条从顶点0到顶点15的合理路径.
用顶点序号的二进制码的0位表示农夫,1位表示狼,2位表示羊,3位表示菜.
那么,总共可能有16个顶点0-15.顶点0表示全在左岸,顶点15表示全在右岸.
当然有些顶点是不允许存在的,比如顶点3,表示农夫和狼在右岸,羊和菜在左岸,羊会吃掉菜.你要把所有这类的顶点去掉.
在剩下的顶点中,你要找出所有的可能的边.比如顶点5表示农夫和羊在右,狼和菜在左,顶点4表示羊在右,那么就存在顶点5到顶点4的有向边.
至此,图已构造完毕,问题就转换成找到一条从顶点0到顶点15的合理路径.
举一反三
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
奥巴马演讲不用看稿子.为什么中国领导演讲要看?
想找英语初三上学期的首字母填空练习……
英语翻译
1,人们染上烟瘾,最终因吸烟使自己丧命.
最新试题
- 1求助 用present progressive造句 5个 在线等~~~~~~谢谢~~~~~~~~~
- 21克尼古丁中含有氮元素__克 __克尼古丁中含氮元素5克
- 3火箭燃料液态氧,液态氢为什么是采用降低温度,压缩体积两种方法把气体液化的?
- 4工业污水盐分(mg/l)比氯离子浓度(mg/l)小为什么
- 5sin36度 sin23度 sin27度16‘ sin27度36’‘求大小
- 6《三国演义》中的故事、歇后语、成语
- 7如图,在三角形ABC中,AD是中线,过点D 分别作三角形ABD、三角形ACD的高DE、DF,若AB=4cm,AC=3cm,DE+DF=3.5cm,求DF的长
- 8How about buying some tofu?的意思是为什么不买一些豆腐?句子中buy为什么加ing?
- 9(初一数学)AB两地相距20千米,小王驾驶汽车以55千米每时的速度从A地出发,小李骑摩托车以45千
- 10见异思迁
热门考点