农夫过河问题？

sipingal

用C语言编程输出最少步骤的过河方法
有一个农夫带一条狼、一只羊和一棵白菜过河。如果没有农夫看管，则狼要吃羊，羊要吃白菜。但是船很小，只够农夫带一样东西过河。问农夫该如何解此难题？

kj501

用图论的方法解决。

doubleelec

一种苯办法:

从初始状态起,穷举所有的可能,记下每次动作(过河或返回)之后的状态(河这边的东西,河对岸的东西),生成一棵树,树的节点记录状态,边的权值记录动作.如果这种状态是不允许的(比如把狼和羊放一起),就不要这个节点.

按层次遍历这棵树,找到第一个符合结束条件的状态,从初始状态到这个状态所经历的边的动作连起来就是所求的最短步骤.

以上两步可以合为一步来做,如果在生成树的时候就按层次遍历的顺序.

我给的附件是一张图,这只是个示意,为了画图方便我把动作写在了节点上.这张图中明显有不必要的节点,比如把狼带过去再带回来又恢复初态是没必要的,在编程的时候当然要有所判断.

doubleelec

附件:

sipingal

能否大体给我概述下？
http://www.linuxsir.cn/forum.php?mod=viewthread&tid=141776

doubleelec

找一本<数据结构>的书看看如何用队列实现"树的按层次遍历",然后结合我上面的算法推敲一下如何编程实现,查不多就是那个C语言程序了,那个Pascal的程序也差不多,那个数组就是我说的"状态",所谓"广度优先搜索"是对图来说的,对树(也是一种图)来说就是按层次遍历.

我从树的角度讲(实现时不一定要建立一个实体的树),基本过程就是:

(1) 树根入队列

(2) 循环进行以下步骤
1> 从队列取出节点(第一次取出的是根)
2> 处理节点(判断非法状态,结束状态等,作出不同的反应),并根据可能出现的状态生成子节点
3> 将子节点放入队列,进入下一轮处理

如果不了解他的算法思想,看程序是比较费劲的,建议你先去看一下数据结构中"树的层次遍历"或"图的广度优先搜索".

freesoft

搜索

kittig

看看吴文虎编的 《实用算法的分析与设计》
清华大学的。

就是这样。
用 N 代表农民 用 W 代表狼，用 G代表羊。

然后写出可以共存的几个状态。和状态之间的转换关系。
寻找一条路径。

wide288

是图，还是树，
树，－－＞两：一，广度优先
            二，深度优先
图，－－－－－－－＞生成树，吧。？
不懂。

kittig

树的复杂度好像高了点。不过还好这个题目规模不大。不会用太长的时间。
用图的话，可能算法时间复杂度要低一些吧。
而且求出最短路径的话，就是最佳的做法。

农民 P， 狼 W， 羊 G， 菜 C。
初始
    PWGC | river | (NULL)

最后的状态是
    (NULL) | river | PWGC

各个中间状态
河左岸 pwfc -> pw,pf,pc,...wg，wc。。。

如果那个状态是不可以的，比如，wg，那么从前一个状态到这个状态的路径长度就是无穷。否则是一个比较小的数，比如1，
构造图，求最短路。