狼羊白菜过河问题图论问题:农夫带着狼、羊、白菜从河的左岸到河-查字典问答网
分类选择

来自鲁保云的问题

  狼羊白菜过河问题图论问题:农夫带着狼、羊、白菜从河的左岸到河的右岸,农夫每次只能带一样东西多河,而且,没有农夫看管,狼会吃羊,羊会吃白菜.提示:利用图论解决问题.(用农夫、狼

  狼羊白菜过河问题图论

  问题:农夫带着狼、羊、白菜从河的左岸到河的右岸,农夫每次只能带一样东西多河,而且,没有农夫看管,狼会吃羊,羊会吃白菜.

  提示:利用图论解决问题.(用农夫、狼、羊、白菜及其在左岸还是右岸等表示图中的顶点)

1回答
2020-04-26 19:22
我要回答
请先登录
程繁科

  用0表示在左岸,1表示在右岸.

  用顶点序号的二进制码的0位表示农夫,1位表示狼,2位表示羊,3位表示菜.

  那么,总共可能有16个顶点0-15.顶点0表示全在左岸,顶点15表示全在右岸.

  当然有些顶点是不允许存在的,比如顶点3,表示农夫和狼在右岸,羊和菜在左岸,羊会吃掉菜.你要把所有这类的顶点去掉.

  在剩下的顶点中,你要找出所有的可能的边.比如顶点5表示农夫和羊在右,狼和菜在左,顶点4表示羊在右,那么就存在顶点5到顶点4的有向边.

  至此,图已构造完毕,问题就转换成找到一条从顶点0到顶点15的合理路径.

2020-04-26 19:27:06

最新问答

推荐文章

猜你喜欢

附近的人在看

推荐阅读

拓展阅读

  • 大家都在看
  • 小编推荐
  • 猜你喜欢
  •