狼羊白菜过河问题 图论
问题:农夫带着狼、羊、白菜从河的左岸到河的右岸,农夫每次只能带一样东西多河,而且,没有农夫看管,狼会吃羊,羊会吃白菜.
提示:利用图论解决问题.(用农夫、狼、羊、白菜及其在左岸还是右岸等表示图中的顶点)
人气:417 ℃ 时间:2020-01-04 02:08:06
解答
用0表示在左岸,1表示在右岸.
用顶点序号的二进制码的0位表示农夫,1位表示狼,2位表示羊,3位表示菜.
那么,总共可能有16个顶点0-15.顶点0表示全在左岸,顶点15表示全在右岸.
当然有些顶点是不允许存在的,比如顶点3,表示农夫和狼在右岸,羊和菜在左岸,羊会吃掉菜.你要把所有这类的顶点去掉.
在剩下的顶点中,你要找出所有的可能的边.比如顶点5表示农夫和羊在右,狼和菜在左,顶点4表示羊在右,那么就存在顶点5到顶点4的有向边.
至此,图已构造完毕,问题就转换成找到一条从顶点0到顶点15的合理路径.
推荐
- 一船夫渡狼、羊、白菜过河,一次只能渡物,且人不在时狼吃羊,羊吃白菜,怎样能安全过河,用图论解题.
- 农夫要将一只狼,一只羊,一棵白菜带过河,一次只能带一样东西,如果带狼,羊就会吃了白菜,应该怎么带呢
- 求程序代码,农夫、狼、羊和白菜过河问题.
- 关于带羊,狼,白菜过河英语文章的问题
- 狼吃羊样吃白菜这是大家都知道的,但是一个农夫要运狼,羊,白菜这三样过河要怎么运?
- 英语翻译:本次会议需要讨论解决以下几个问题
- 线速度,角速度,周期关系
- 求含有“恩”字的褒义成语和贬义成语各两个,
猜你喜欢
- 一个苹果和一个梨重0.29千克,一个苹果和一个橘子重0.24千克,一个梨和一个橘子共重0.24千克.一个苹果的重
- 上课是否专心听讲是取得好成绩的关键
- 有一根高为cm,底面半径为cm的圆柱形铁管,用一段铁丝在铁管上缠绕圈,并使铁丝的两个端点落在援助的同一
- 请问汽车停的是几号车位?
- 配制500mL20%的稀硫酸需98%的硫酸多少毫升?水多少毫升?
- There is( ) breat here I( )all of it Who is singing in the next room?( )must be Tom
- 怎么背英语单词能快一些,记忆的时间长一些呢?我背单词真的很累,背了没多久那些难得又忘了,简单的都记住了.而且那些好不容易不出来的单词,在考试的时候要拼写,但是脑子却一片空白!受不了了!
- 根据句意,选择相应的单词或词组,并用其正确形式填空.