问题描述：
一农夫带着一头狼，一只羊和一个白菜过河，小船只能一次装载农夫和一样货物，狼会吃羊，羊会吃白菜，只有农夫在时才安全。现欲让所有物品包括农夫都安全过道河对岸，求最佳算法。
解法如下：
1.农夫带羊过去，自己回来
2.农夫带狼过去，带羊回来
3.农夫带白菜过去，自己回来
4.农夫带羊过去
全部安全过岸.
深度优先搜索方法：首先扩展最新产生的结点，每层只对一个结点进行扩展，除非搜索失败或以达到预先约定的最大深度，才会退回去搜索原来来忽略的结点。
广度优先搜索方法：以接近起始结点的程度依次扩展结点，即对下一层结点搜索前，必须先搜索完本层所有结点。
深度优先（栈）源代码：
#include<iostream>
using namespace std;
#define VertexNum 16
//最大顶点数
typedef struct // 图的顶点
{
int farmer;
// 农夫
int wolf;
// 狼
int sheep;
// 羊
int veget;
// 白菜
}Vertex;
typedef struct
{
int vertexNum;
// 图的当前顶点数
Vertex vertex[VertexNum];
// 顶点向量（代表顶点）
bool Edge[VertexNum][VertexNum];
// 邻接矩阵. 用于存储图中的边，其矩阵元素个数取决于顶点个数，与边数无关
}AdjGraph;
// 定义图的邻接矩阵存储结构
bool visited[VertexNum] = {false};
// 对已访问的顶点进行标记（图的遍历）
int retPath[VertexNum] = {-1};
// 保存DFS搜索到的路径，即与某顶点到下一顶点的路径
// 查找顶点（F，W，S，V）在顶点向量中的位置
int locate(AdjGraph *graph, int farmer, int wolf, int sheep, int veget)
{
// 从0开始查找
for (int i = 0; i < graph->vertexNum; i++)
{
if ( graph->vertex[i].farmer == farmer && graph->vertex[i].wolf == wolf
&& graph->vertex[i].sheep == sheep && graph->vertex[i].veget == veget )
{
return i;
//返回当前位置
}
}
return -1;
//没有找到此顶点
}
// 判断目前的（F，W，S，V）是否安全
bool isSafe(int farmer, int wolf, int sheep, int veget)
{
//当农夫与羊不在一起时，狼与羊或羊与白菜在一起是不安全的
if ( farmer != sheep && (wolf == sheep || sheep == veget) )
{
return false;
}
else
{
return true;
// 安全返回true
}
}
// 判断状态i与状态j之间是否可转换
bool isConnect(AdjGraph *graph, int i, int j)
{
int k = 0;
if (graph->vertex[i].wolf != graph->vertex[j].wolf)
{
k++;
}
if (graph->vertex[i].sheep != graph->vertex[j].sheep)
{
k++;
}
if (graph->vertex[i].veget != graph->vertex[j].veget)
{
k++;
}
// 以上三个条件不同时满足两个且农夫状态改变时，返回真, 也即农夫每次只能带一件东西过桥
if (graph->vertex[i].farmer != graph->vertex[j].farmer && k <= 1)
{
return true;
}
else
{
return false;
}
}
// 创建连接图
void CreateG(AdjGraph *graph)
{
int i = 0;
int j = 0;
// 生成所有安全的图的顶点
for (int farmer = 0; farmer <= 1; farmer++)
{
for (int wolf = 0; wolf <= 1; wolf++)
{
for (int sheep = 0; sheep <= 1; sheep++)
{
for (int veget = 0; veget <= 1; veget++)
{
if (isSafe(farmer, wolf, sheep, veget))
{
graph->vertex[i].farmer = farmer;
graph->vertex[i].wolf = wolf;
graph->vertex[i].sheep = sheep;
graph->vertex[i].veget = veget;
i++;
}
}
}
}
}
// 邻接矩阵初始化即建立邻接矩阵
graph->vertexNum = i;
for (i = 0; i < graph->vertexNum; i++)
{
for (j = 0; j < graph->vertexNum; j++)
{
// 状态i与状态j之间可转化，初始化为1，否则为0
if (isConnect(graph, i, j))
{
graph->Edge[i][j] = graph->Edge[j][i] = true;
}
else
{
graph->Edge[i][j] = graph->Edge[j][i] = false;
}
}
}
return;
}
// 判断在河的那一边
char* judgement(int state)
{
return ( (0 == state) ? "左岸" : "右岸" );
}
// 输出从u到v的简单路径，即顶点序列中不重复出现的路径
void printPath(AdjGraph *graph, int start, int end)
{
int i = start;
cout << "farmer" << ", wolf" << ", sheep" << ", veget" << endl;
while (i != end)
{
cout << "(" << judgement(graph->vertex[i].farmer) << ", " << judgement(graph->vertex[i].wolf)
<< ", " << judgement(graph->vertex[i].sheep) << ", " << judgement(graph->vertex[i].veget) << ")";
cout << endl;
i = retPath[i];
}
cout << "(" << judgement(graph->vertex[i].farmer) << ", " << judgement(graph->vertex[i].wolf)
<< ", " << judgement(graph->vertex[i].sheep) << ", " << judgement(graph->vertex[i].veget) << ")";
cout << endl;
}
// 深度优先搜索从u到v的简单路径 //DFS--Depth First Search
void dfsPath(AdjGraph *graph, int start, int end)
{
int i = 0;
visited[start] = true; //标记已访问过的顶点
if (start == end)
{
return ;
}
for (i = 0; i < graph->vertexNum; i++)
{
if (graph->Edge[start][i] && !visited[i])
{
retPath[start] = i;
dfsPath(graph, i, end);
}
}
}
int main()
{
AdjGraph graph;
CreateG(&graph);
int
start = locate(&graph, 0, 0, 0, 0);
int end = locate(&graph, 1, 1, 1, 1);
dfsPath(&graph, start, end);
if (visited[end]) // 有结果
{
printPath(&graph, start, end);
return 0;
}
return -1;
}
输出结果：
http://s6/middle/8292a06agbef72735c565&690
广度优先（队列）源代码：
#include<stdio.h>
#include<stdlib.h>
#define
MAXNUM 20
typedef int DataType;
struct SeqQueue
{
int f, r;
DataType
q[MAXNUM];
};
typedef struct SeqQueue
*PSeqQueue;
PSeqQueue createEmptyQueue_seq( void ) {
PSeqQueue
paqu = (PSeqQueue)malloc(sizeof(struct SeqQueue));
if (paqu ==
NULL)
printf("Out of space!! \n");
else
paqu->f = paqu->r = 0;
return
(paqu);
}
int isEmptyQueue_seq( PSeqQueue paqu ) {
return
paqu->f == paqu->r;
}
void enQueue_seq( PSeqQueue paqu, DataType x )
{
if (
(paqu->r + 1) % MAXNUM ==
paqu->f )
printf( "Full queue.\n" );
else {
paqu->q[paqu->r] = x;
paqu->r = (paqu->r + 1) %
MAXNUM;
}
}
void deQueue_seq( PSeqQueue paqu ) {
if(
paqu->f == paqu->r )
printf( "Empty Queue.\n" );
else
paqu->f = (paqu->f + 1) %
MAXNUM;
}
DataType frontQueue_seq( PSeqQueue paqu ) {
return
(paqu->q[paqu->f]);
}
int farmer(int location) {
return 0 !=
(location & 0x08);
}
int wolf(int location) {
return 0 !=
(location & 0x04);
}
int cabbage(int location) {
return 0 !=
(location & 0x02);
}
int goat(int location) {
return 0
!=(location & 0x01);
}
int safe(int location) {
if
((goat(location) == cabbage(location))
&&
(goat(location) != farmer(location)) )
return 0;
if
((goat(location) == wolf(location))
&&
(goat(location) != farmer(location)))
return 0;
return
1;
}
void farmerProblem( ) {
int movers,
i, location, newlocation;
int
route[16];
PSeqQueue
moveTo;
moveTo =
createEmptyQueue_seq( );
enQueue_seq(moveTo, 0x00);
for (i = 0;
i < 16; i++) route[i] = -1;
route[0]=0;
while
(!isEmptyQueue_seq(moveTo)&&(route[15]
== -1)) {
location = frontQueue_seq(moveTo);
deQueue_seq(moveTo);
for (movers = 1; movers <= 8; movers
<<= 1) {
if ((0 != (location & 0x08)) == (0 != (location
& movers))) {
newlocation = location^(0x08|movers);
if (safe(newlocation) &&
(route[newlocation] == -1)) {
route[newlocation] = location;
enQueue_seq(moveTo, newlocation);
}
}
}
}
if(route[15]
!= -1) {
printf("The reverse path is : \n");
for(location = 15; location >= 0; location =
route[location]) {
printf("The location is : %d\n",location);
if (location == 0) return;
}
}
else
printf("No solution.\n");
}
int main() {
farmerProblem( );
return
0;
}
输出结果：
http://s1/middle/8292a06agbef747f3b590&690
加载中，请稍候......
加载中…
(2012-05-01 18:28:30)