农夫过河问题状态图及程序
-
农夫过河问题状态图及程序
一、
问题需求分析
一个农夫带着一只狼、
一只羊和一棵白菜，身处河的南岸。
他要把这些东西全部运到北岸。问题是他面前只有一
条小
船，船小到只能容下他和一件物品，另外只有农夫能撑船。
另外，因为狼能吃羊，而羊爱吃白菜，所以农夫不能留下羊
和白菜或者狼和羊单独在河的
一边，自己离开。请问农夫该
采取什么方案才能将所有的东西运过河呢？
二、
算法选择
求解这个问题的最简单的方
法是一步一步进行试探，每一步
都搜索所有可能的选择，对前一步合适的选择再考虑下一
步
的各种方案。
用计算机实现上述求
解的搜索过程可以采用两种不同的策
略：
一种是广度优先
(breadth_first)
搜索，
另
一种是深度优先
(depth_first)
。
广度优先：
u
广度优先的含义就是在搜索过程中总是首先搜索下面一
步的所有可能
状态
，然后再进一步考虑更后面的各种情况。
u
要实现广度优先搜索，
一般都
采用队列作为辅助结构。
把
下一步所有可能达到的
状态
都列举出来，放在这个队列中，
然后顺序取出来
分别进行处理，处理过程中把再下一步的
状
态
< br>放在队列里
……
。
u
由于队列的操作遵循先进先出的原则，在这个处理过程
中，只有在前一步的所有情况都处理完后，才能开始后面一
步各
情况的处理。
三、
算法的精化
要模拟
农夫过河问题
，首先需要选择一个对问题中每个角色<
/p>
的位置进行描述的方法。一个很方便的办法是用四位二进制
数顺序
分别表示农夫、狼、白菜和羊的位置。例如用
0
表示
农夫或者某东西在河的南岸，
1
表示在河的北岸。
因此整数
5(
其二进制表示为
0101
)
表示农夫和白菜在河的南岸，而狼
和羊在北岸。
四、
算法的实现
完成了上面的准备工作，现在的问题变成：
< br>从初始
状态
二进制
0000(<
/p>
全部在河的南岸
)
出发，
寻找一种全
部由安全
状态
构
成的
状态
序列，它以二进制
1111(
全部到达
河的北岸
)
为最终目标，并且在序列中的每一个
状态
都可以
从前一
状态
通过农夫（可以带一样东西）划船
过河的动作到
达。
为避免不必要的瞎
费功夫，要求在序列中不应该出现重复的
状态
。为了实现广度优
先搜索，算法中需要使用了一个整数
队列
moveTo
，它的每个元素表示一个可以安全到达的中间
状态
。另外还需要一个数据结构记录已被访问过的各个
状
态
，以
及
已被发现的能够到达当前这个
状态
的路径。
由于在
这个问题的解决过程中需要列举的所有
状态
(
< br>二进制
0000 ~ 1111)
一共
< br>16
种，
所以可以构造一个包含
16
个元素的
整数顺序表来满足以上的要求。用顺序表的第
i
个元素记录
状态
i
是否已被访问过，若已被访问过则在这个顺序表元素
中记入前
驱
状态
值，算法中把这个顺序表叫做
r
oute
。
route
的每个分量初始
化值均为
-1
，每当我们在队列中加入一个新
< br>状态
时，就把顺序表中以该
状态
作下标的元素的值改为达到
这个
状态
的
路径上前一
状态
的下标值。
route
的一个元素具有
非负值表示这个
状态<
/p>
已访问过，或是正被考虑。最后我们可
以利用
route
顺序表元素的值建立起正确的
状态
路径。
五、
程序
代码
// farmerProblem.c
//
用队列解决
农夫过河问题
#include
#include
typedef
int DataType;
//
顺序队列：类型和界面函数声明
struct SeqQueue
{
//
顺序队列类型定义
int
MAXNUM; //
队列中最大元素个数
int f, r;
DataType
*q;
};
typedef struct
SeqQueue *PSeqQueue; //
顺序队列类型的指针
类型
PSeqQueue
createEmptyQueue_seq(int m)
{
//
创建一个空队列
PSeqQueue queue =
(PSeqQueue)malloc(sizeof(struct
SeqQueue));
if (queue !=
NULL)
{
queue->q
= (DataType*)malloc(sizeof(DataType) *m);
if (queue->q)
{
queue->MAXNUM = m;
queue->f = 0;
queue->r = 0;
return
(queue);
}
else
free(queue);
}
printf(
存储分配失败
return NULL;
}
int isEmptyQueue_seq(PSeqQueue queue)
{
//
判断队列是否为空
return (queue->f == queue->r);
}
void enQueue_seq(PSeqQueue
queue, DataType x)
//
在队尾插入元素
x
{
if ((queue->r + 1) % queue->MAXNUM
== queue->f)
printf(
else
{
queue->q[queue->r] = x;
queue->r = (queue->r + 1) % queue->MAXNUM;
}
}
void deQueue_seq(PSeqQueue queue)
//
删除队列头部元素
{
if (queue->f ==
queue->r)
printf(