2 qq 26822029 qq_26822029 于 2016.03.08 12:00 提问

农夫过河问题用深度优先遍历和广度优先遍历?

农夫过河问题用深度优先遍历和广度优先遍历的区别?用哪个更好?

2个回答

lx624909677
lx624909677   Ds   Rxr 2016.03.08 18:53

求解这个问题的最简单的方法是一步一步进行试探,每一步都搜索所有可能的选择,对前一步合适的选择再考虑下一步的各种方案。
用计算机实现上述求解的搜索过程可以采用两种不同的策略:一种是广度优先(breadth_first) 搜索,另一种是深度优先(depth_first) 。
广度优先:
u 广度优先的含义就是在搜索过程中总是首先搜索下面一步的所有可能状态,然后再进一步考虑更后面的各种情况。
u 要实现广度优先搜索,一般都采用队列作为辅助结构。把下一步所有可能达到的状态都列举出来,放在这个队列中,然后顺序取出来分别进行处理,处理过程中把再下一步的状态放在队列里……。
u 由于队列的操作遵循先进先出的原则,在这个处理过程中,只有在前一步的所有情况都处理完后,才能开始后面一步各情况的处理。
三、 算法的精化
要模拟农夫过河问题,首先需要选择一个对问题中每个角色的位置进行描述的方法。一个很方便的办法是用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。例如用0表示农夫或者某东西在河的南岸,1表示在河的北岸。因此整数5(其二进制表示为0101) 表示农夫和白菜在河的南岸,而狼和羊在北岸。

四、 算法的实现
完成了上面的准备工作,现在的问题变成:
从初始状态二进制0000(全部在河的南岸) 出发,寻找一种全部由安全状态构成的状态序列,它以二进制1111(全部到达河的北岸) 为最终目标,并且在序列中的每一个状态都可以从前一状态通过农夫(可以带一样东西)划船过河的动作到达。
为避免不必要的瞎费功夫,要求在序列中不应该出现重复的状态。为了实现广度优先搜索,算法中需要使用了一个整数队列moveTo,它的每个元素表示一个可以安全到达的中间状态。另外还需要一个数据结构记录已被访问过的各个状态,以及已被发现的能够到达当前这个状态的路径。
由于在这个问题的解决过程中需要列举的所有状态(二进制0000 ~ 1111)一共16种,所以可以构造一个包含16个元素的整数顺序表来满足以上的要求。用顺序表的第i个元素记录状态i是否已被访问过,若已被访问过则在这个顺序表元素中记入前驱状态值,算法中把这个顺序表叫做route。route的每个分量初始化值均为-1,每当我们在队列中加入一个新状态时,就把顺序表中以该状态作下标的元素的值改为达到这个状态的路径上前一状态的下标值。route的一个元素具有非负值表示这个状态已访问过,或是正被考虑。最后我们可以利用route顺序表元素的值建立起正确的状态路径。

caozhy
caozhy   Ds   Rxr 2016.03.08 12:06
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
c实现农夫过河问题
问题描述:一个农夫带着一只狼、一只羊和一棵白菜,身处河的南岸。他要把这些东西全部运到北岸。问题是他面前只有一条小船,船小到只能容下他和一件物品,另外只有农夫能撑船。另外,因为狼能吃羊,而羊爱吃白菜,所以农夫不能留下羊和白菜或者狼和羊单独在河的一边,自己离开。请问农夫该采取什么方案才能将所有的东西运过河呢? 思路:此题与通常的过河问题不同之处是,不考虑过河时与物品花费的时间,而是考虑河两岸物品是否
用队列解决农夫过河问题
题目:农夫要把狼、羊、菜和自己运到河对岸去,只有农夫能够划船,农夫每次只能运一种东西,就是如果没有农夫看着,羊会偷吃菜,狼会吃羊。 #include using namespace std; #define NUM 50 template class Seq { private: T * elem; int front; int rear; int maxsize; in
农夫过河问题算法设计与实现
农夫过河算法基于队列的实现
用prolog解决农夫过河问题
在swi-prolog上实现的,能很好地解决农夫过河问题!
农夫过河问题(图的邻接矩阵)
/******************************************************************************* *农夫过河问题(图的邻接矩阵存储,深度优先遍历): * *一个农夫带着一只羊、一只狼、和一颗白菜过河(左岸->右岸); * *河边只有一条船,由于船太小,只能装下农夫和他的一样东西; * *
农夫过河问题的c语言实现
文章来源:http://blog.csdn.net/neweastsun/archive/2009/11/08/4785611.aspx  一、        问题需求分析 一个农夫带着一只狼、一只羊和一棵白菜,身处河的南岸。他要把这些东西全部运到北岸。问题是他面前只有一条小船,船小到 只能容下他和一件物品,另外只有农夫能撑船。另外,因为狼能吃羊,而羊爱吃白菜,所以农夫不能
Java语言解决农夫过河问题
问题描述:农夫要带鱼、狗、猫过河到对岸.,有一条船,只能坐一个人,农夫每次只能带一样动物过河,当农夫不在的时侯狗会咬猫,猫会吃鱼.,请问怎么顺序过呢?要求:编写程序,由程序来推出过河的顺序 用Java语言实现的
农夫过河问题 简单的搜索
// 用一个二进制串表示状态0,表示东西或者人在河的这边 // 1表示东西或者人在河的另一边 // 比如0000表示都在起始的位置,1111表示都到了对岸 // 通过状态的转移,来找到路径 #include #include #include #include using namespace std; const int maxn = 100; const int inf = 0x7f7
java 农夫过河问题(包括有界面和无界面的)
该资源包括有界面和无界面的。一个农夫带着—只狼、一只羊和—棵白菜,身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船,船只能容下他和—件物品,另外只有农夫才能撑船。如果农夫在场,则狼不能吃羊,羊不能吃白菜,否则狼会吃羊,羊会吃白菜,所以农夫不能留下羊和白菜自己离开,也不能留下狼和羊自己离开,而狼不吃白菜。
C++农夫过河问题代码
#include<stdio.h> #include<stdlib.h> #define MAXNUM 20 typedef int DataType; struct SeqQueue /* 顺序队列类型定义 */ { int f,r; DataType q[MAXNUM]; };