农夫过河演示文稿.ppt

10、农夫过河问题 一个人带着狼、山羊河白菜在一条河的左岸，有一条船，大小正好能装下这个人河其他三件东西中的一件。人和他的随行物都要过到河的右岸。人每次只能将一件东西摆过河。但若人将狼和羊留在同一岸而无人照顾的话，狼将把羊吃掉。类似的，若羊和白菜留下来无人照看，羊将会吃掉白菜，请问是否有可能渡过河去，使得羊和白菜都不能被吃掉？如果可能，请用有限自动机写出渡河的方法。 如何考虑： （1）第一，我们会考虑一种方案，只要能渡河就可以了； （2）进一步，我们要考虑会不会有解决该类问题的方法（形式化）：图论、有哪些信誉好的足球投注网站算法（人工智能）； （3）更进一步：这个问题我们该如何设计程序实现。 图论问题 方法是将不可能的条件去除，将可能的条件一一列出，在这些条件之间寻求一种联系，进而将问题以网络图形的形式呈现，再应用图形理论来解决它。 方法是将不可能的条件去除，将可能的条件一一列出，在这些条件之间寻求一种联系，进而将问题以网络图形的形式呈现，再应用图形理论来解决它。 首先看：人狼羊菜的组合方式共有24=16种 方法是将不可能的条件去除，将可能的条件一一列出，在这些条件之间寻求一种联系，进而将问题以网络图形的形式呈现，再应用图形理论来解决它。 首先看：人狼羊菜的组合方式共有24=16种 人，狼，羊，菜，人狼，人羊，人菜，狼羊，狼菜，羊菜，人狼羊，人狼菜，人羊菜，狼羊菜，人狼羊菜，空 去掉不可能的状态：狼羊菜，羊菜，狼羊 与之对应的三种状态也不可能出现，所以剩下10种可能的情形。 将这十种情形看作是点，只有在两种状态可以相互转变的时候，在他们之间建立一条边线。 至此，整个题目就变成了{人狼羊菜}＝。。。＝》{}的过程；也就是从图中找出从“人狼羊菜”到“空”的最短路径。 图论问题 将各个顶点与人狼羊菜这一点的距离标示在图顶处，于是可以看到有两种最迅速而且安全的运送方案 （1）人狼羊菜，狼菜，人狼菜，狼，人狼羊，羊，人羊，空； （2）人狼羊菜，狼菜，人狼菜，菜，人羊菜，羊，人羊，空。 每种方案都要渡河七次。 有哪些信誉好的足球投注网站问题 F W D C F D C W F W G C W G C F G C F W W C F G W G F C F W C G F W G C W F G C F W C G W C F G C F W G F C W G F G C W G F W C F W G C F W G C F W C G W G F C W F G C C F W G G C F W G F W C F G C W F W G C F G W C F W G C G F W C Goal State Repeated State Illegal State F W D C W C F D F W C D C F W D F D C W D F W C F D W C F W D C F W D C W C F D F W C D C F W D F D C W D F W C F D W C F W D C 人独自返回 人带羊到对岸 人带狼到对岸 人带羊返回 人带菜到对岸 人独自返回 人带羊到对岸 Success! 最初状态