农夫过河算法
‘壹’ 算法“农夫过河”程序 望高手指错修改
v!=1111
能这么用么,这里的1111应该是十进制的1111了吧.
bitset没用过,不知道是不是要用
v.to_ulong()!=0x0F
算法上也有问题,就是当某种走法不成功时,退回上层递归后,没有回复到走之前的状态.应该设个临时变量等于v,对临时变量进行flip和search递归.
另外,采用某种走法前的判断if语句也有问题,比如v[farmer]==v[sheep],我们已经知道正确走法的第一步就是农夫和羊过,但第二步的时候, 农夫和羊都在对岸,值都是1,仍相等,就又都走回来了.
我个人认为,这个问题应该构造树,然后层次遍历,而现在的程序是深度优先遍历.
‘贰’ 农夫过河的图算法
#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;
}
‘叁’ 高分跪求求过河问题程序算法！
paddy102的专栏
CSDNBlog | 我的首页 | 联系作者 | 聚合 | 登录 5篇文章 :: 0篇收藏:: 0篇评论:: 0个Trackbacks
文章
C++/Visual C++(RSS)
算法设计(RSS)
游戏开发(RSS)
收藏
相册
存档
2004年06月(4)
2004年04月(1)
野人过河问题算法分析
野人过河问题算法分析
野人过河问题属于人工智能学科中的一个经典问题，问题描述如下： 有三个牧师（也有的翻译为传教士）和三个野人过河，只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于牧师的人数，那么牧师就会有危险. 你能不能找出一种安全的渡河方法呢？
一、算法分析
先来看看问题的初始状态和目标状态，假设和分为甲岸和乙岸：
初始状态：甲岸，3野人，3牧师；
乙岸，0野人，0牧师；
船停在甲岸，船上有0个人；
目标状态：甲岸，0野人，0牧师；
乙岸，3野人，3牧师；
船停在乙岸，船上有0个人；
整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。问题状态的改变是通过划船渡河来引发的，所以合理的渡河操作就成了通常所说的算符，根据题目要求，可以得出以下5个算符（按照渡船方向的不同，也可以理解为10个算符）：
渡1野人、渡1牧师、渡1野人1牧师、渡2野人、渡2牧师
算符知道以后，剩下的核心问题就是搜索方法了，本文采用深度优先搜索，通过一个FindNext(…)函数找出下一步可以进行的渡河操作中的最优操作，如果没有找到则返回其父节点，看看是否有其它兄弟节点可以扩展，然后用Process(…)函数递规调用FindNext(…)，一级一级的向后扩展。
搜索中采用的一些规则如下：
1、渡船优先规则：甲岸一次运走的人越多越好（即甲岸运多人优先），同时野人优先运走；
乙岸一次运走的人越少越好（即乙岸运少人优先），同时牧师优先运走；
2、不能重复上次渡船操作（通过链表中前一操作比较），避免进入死循环;
3、任何时候河两边的野人和牧师数均分别大于等于0且小于等于3；
4、由于只是找出最优解，所以当找到某一算符（当前最优先的）满足操作条件后，不再搜索其兄弟节点，而是直接载入链表。
5、若扩展某节点a的时候，没有找到合适的子节点，则从链表中返回节点a的父节点b，从上次已经选择了的算符之后的算符中找最优先的算符继续扩展b。
二、基本数据结构
仔细阅读问题，可以发现有些基本东西我们必须把握，例如：每时刻河两岸野人牧师各自的数目、船的状态、整个问题状态。所以我们定义如下几个数据结构：
typedef struct _riverside // 岸边状态类型
{
int wildMan; // 野人数
int churchMan; // 牧师数
}RIVERSIDE;
typedef struct _boat // 船的状态类型
{
int wildMan; // 野人数
int churchMan; // 牧师数
}BOAT;
typedef struct _question // 整个问题状态
{
RIVERSIDE riverSide1; // 甲岸
RIVERSIDE riverSide2; // 乙岸
int side; // 船的位置, 甲岸为-1, 乙岸为1
BOAT boat; // 船的状态
_question* pPrev; // 指向前一渡船操作
_question* pNext; // 指向后一渡船操作
}QUESTION;
用QUESTION来声明一个最基本的链表。
三、程序流程及具体设计
本文只找出了最优解，据我所知，本问题有三种解。如果真要找出这三种解，^_^，那就得加强对链表的操作了，比如说自己写一个动态链表类，顺便完成一些初始化工作，估计看起来会舒服些。
下面给出部分关键程序：
// 主函数
int main()
{
// 初始化
QUESTION* pHead = new QUESTION;
pHead->riverSide1.wildMan = 3;
pHead->riverSide1.churchMan = 3;
pHead->riverSide2.wildMan = 0;
pHead->riverSide2.churchMan = 0;
pHead->side = -1; // 船在甲岸
pHead->pPrev = NULL;
pHead->pNext = NULL;
pHead->boat.wildMan = 0;
pHead->boat.churchMan = 0;
if (Process(pHead))
{
// ......... 遍历链表输出结果
}
cout<<"成功渡河。";
}
else
cout<<"到底怎样才能渡河呢? 郁闷!"<<endl;
// 回收内存空间
while (pHead)
{
QUESTION* pTemp = pHead->pNext;
delete pHead;
pHead=pTemp;
}
pHead = NULL;
return 0;
}
// 渡船过程, 递规调用函数FindNext(...)
BOOL Process(QUESTION* pQuest)
{
if (FindNext(pQuest))
{
QUESTION* pNew = new QUESTION;
pNew->riverSide1.wildMan = pQuest->riverSide1.wildMan + pQuest->boat.wildMan*(pQuest->side);
pNew->riverSide1.churchMan = pQuest->riverSide1.churchMan + pQuest->boat.churchMan*(pQuest->side);
pNew->riverSide2.wildMan = 3 - pNew->riverSide1.wildMan;
pNew->riverSide2.churchMan = 3 - pNew->riverSide1.churchMan;
pNew->side = (-1)*pQuest->side;
pNew->pPrev = pQuest;
pNew->pNext = NULL;
pNew->boat.wildMan = 0;
pNew->boat.churchMan = 0;
pQuest->pNext = pNew;
if (pNew->riverSide2.wildMan==3 && pNew->riverSide2.churchMan==3)
return TRUE; // 完成
return Process(pNew);
}
else
{
QUESTION* pPrev = pQuest->pPrev;
if (pPrev == NULL)
return FALSE; // 无解
delete pQuest;
pPrev->pNext = NULL;
return Process(pPrev); // 返回其父节点重新再找
}
return TRUE;
}
// 判断有否下一个渡河操作, 即根据比较算符找出可以接近目标节点的操作
// 算符共5个: 1野/ 1牧 / 1野1牧 / 2野 / 2牧
BOOL FindNext(QUESTION* pQuest)
{
// 基本规则
// 渡船的优先顺序: 甲岸运多人优先, 野人优先; 乙岸运少人优先, 牧师优先.
static BOAT boatState[5]; // 5个算符
if (pQuest->side == -1)
{
boatState[0].wildMan = 2;
boatState[0].churchMan = 0;
boatState[1].wildMan = 1;
boatState[1].churchMan = 1;
boatState[2].wildMan = 0;
boatState[2].churchMan = 2;
boatState[3].wildMan = 1;
boatState[3].churchMan = 0;
boatState[4].wildMan = 0;
boatState[4].churchMan = 1;
}
else
{
boatState[0].wildMan = 0;
boatState[0].churchMan = 1;
boatState[1].wildMan = 1;
boatState[1].churchMan = 0;
boatState[2].wildMan = 0;
boatState[2].churchMan = 2;
boatState[3].wildMan = 1;
boatState[3].churchMan = 1;
boatState[4].wildMan = 2;
boatState[4].churchMan = 0;
}
int i; // 用来控制算符
if (pQuest->boat.wildMan == 0 && pQuest->boat.churchMan == 0) // 初始状态, 第一次渡河时
i = 0; // 取算符1
else
{
for (i=0; i<5; i++) // 扩展同一节点时, 已经用过的算符不再用, 按优先级来
if (pQuest->boat.wildMan == boatState[i].wildMan && pQuest->boat.churchMan == boatState[i].churchMan)
break;
i++;
}
if (i < 5)
{
int j;
for (j=i; j<5; j++)
{
int nWildMan1 = pQuest->riverSide1.wildMan + boatState[j].wildMan * pQuest->side;
int nChurchMan1 = pQuest->riverSide1.churchMan + boatState[j].churchMan * pQuest->side;
int nWildMan2 = 3 - nWildMan1;
int nChurchMan2 = 3 - nChurchMan1;
// 判断本次操作的安全性, 即牧师数量>=野人或牧师数为0
if ((nWildMan1 <= nChurchMan1 || nChurchMan1 == 0) &&
(nWildMan2 <= nChurchMan2 || nChurchMan2 == 0) &&
nWildMan1 >=0 && nChurchMan1 >=0 && nWildMan2 >=0 && nChurchMan2 >= 0)
{
// 本操作是否重复上次操作,注意方向不同
if (pQuest->pPrev != NULL)
{
if (pQuest->pPrev->boat.wildMan == boatState[j].wildMan &&
pQuest->pPrev->boat.churchMan == boatState[j].churchMan)
continue;
}
break; // 该操作可行, 推出循环，只找出当前最优节点
}
}
if (j < 5)
{
pQuest->boat.wildMan = boatState[j].wildMan;
pQuest->boat.churchMan = boatState[j].churchMan;
return TRUE;
}
}
return FALSE;
}
Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=21630
[点击此处收藏本文] 发表于 2004年04月07日 2:18 PM
没有评论。
发表评论
大名：
请输入尊姓大名
网址：
验证码
评论
请输入评论
记住我？
--------------------------------------------------------------------------------
网站简介－广告服务－网站地图－帮助信息－联系方式－English－问题报告
CSDN北京百联美达美数码科技有限公司 版权所有 京 ICP 证 020026 号 CSDN
&; 2000-04, CSDN.NET, All Rights Reserved
--------------------------------------------------------------------------------
Copyright &; paddy102 Powered By .Text
‘肆’ 广度优先 算法，各位帮帮。。急
个人对广度优先算法的理解是每次优先遍历父结点下的直接子结点，遍历完这些直接子结点之后再从这些子结点开始遍历他们的直接子结点，以此类推下去，直到找到终点。所以，此处肯定是需要使用到迭代了。在此我想写出我的思路来与楼主交流下。
1.确定startway点和endway点以后，找到startway点，并对该点下的子结点进行遍历。如你此处选择的startway是牧野草原04 即位置在ab(04)，endway是牧野草原15，那么ab(04)下的直接子结点可认为是牧野草原06、牧野草原08和牧野草原10。我们开始按照广度优先算法遍历到牧野草原15。
2.首先我们遍历完04的子结点（06，08，10），发现没有15。
3.接下来我们遍历结点06的子结点（04，05，03），发现没有15.
4.然后，我们开始遍历结点08的子结点（4，15，16），发现15，于是整个遍历结束。
PS:对于回路的子结点不应该考虑遍历，比如06中04的回路。
‘伍’ 农夫过河问题的求解
#include<iostream.h>
#include<stdio.h>
#defineMAXNUM 20
typedefstruct //顺序队列类型定义
{
int f, r; //f表示头，r 表示尾
int q[MAXNUM];//顺序队
}SeqQueue,*PSeqQueue;
PSeqQueuecreateEmptyQueue_seq( ) //创建队列
{
PSeqQueue paqu = new SeqQueue;
if(paqu == NULL)
cout<<"Out of space!"<<endl;
else
paqu->f=paqu->r=0;
return (paqu);
}
intisEmptyQueue_seq( PSeqQueue paqu ) //判断paqu 所指是否是空队列
{
return paqu->f==paqu->r;
}
voidenQueue_seq(PSeqQueue paqu,int x) //在队列中插入一元素 x
{
if ((paqu->r+1)%MAXNUM==paqu->f)
cout<<"队列已满."<<endl;
else
{
paqu->q[paqu->r]=x;
paqu->r=(paqu->r+1)%MAXNUM;
}
}
void deQueue_seq(PSeqQueue paqu) //删除队列头部元素
{
if( paqu->f==paqu->r)
cout<<"队列为空"<<endl;
else
paqu->f=(paqu->f+1)%MAXNUM;
}
intfrontQueue_seq( PSeqQueue paqu ) //对非空队列,求队列头部元素
{
return (paqu->q[paqu->f]);
}
intfarmer(int location) //判断农夫位置对0做与运算，还是原来的数字，用来判断位置
{
return 0 != (location & 0x08);
}
intwolf(int location) //判断狼位置
{
return 0 != (location & 0x04);
}
intcabbage(int location) //判断白菜位置
{
return 0 != (location & 0x02);
}
intgoat(int location) //判断羊的位置
{
return 0 !=(location & 0x01);
}
intsafe(int location) // 若状态安全则返回 true
{
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]; //记录已考虑的状态路径
int print[MAXNUM];
PSeqQueue moveTo;
moveTo = createEmptyQueue_seq( );//新的队列判断路径
enQueue_seq(moveTo, 0x00); //初始状态为0
for (i = 0; i < 16; i++)
route[i] = -1; //-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)
{
cout<<"过河步骤是 : "<<endl;
i=0;
for(location = 15; location >= 0; location= route[location])
{
print[i]=location;
i++;
if (location == 0)
break;
}
int num=i-1;
int temp[20][4];
int j;
for(i=num;i>=0;i--)
{
for(j=3;j>=0;j--)
{
temp[num-i][j]=print[i]%2;
print[i]/=2;
temp[0][j]=0;
temp[num+1][j]=1;
}
}
for(i=1;i<=num;i++)
{
cout<<"\t\t\tNO ."<<i<<"\t";
if(i%2==1)
{
if(temp[i][3]!=temp[i-1][3])
cout<<"农夫带羊过南岸";
if(temp[i][2]!=temp[i-1][2])
cout<<"农夫带白菜过南岸";
if(temp[i][1]!=temp[i-1][1])
cout<<"农夫带狼过南岸";
if(temp[i][3]==temp[i-1][3]&&temp[i][2]==temp[i-1][2]&&temp[i][1]==temp[i-1][1])
cout<<"农夫自己过南岸";
}
else if(i%2==0)
{
if(temp[i][3]!=temp[i-1][3])
cout<<"农夫带羊回北岸";
if(temp[i][2]!=temp[i-1][2])
cout<<"农夫带白菜回北岸";
if(temp[i][1]!=temp[i-1][1])
cout<<"农夫带狼回北岸";
if(temp[i][3]==temp[i-1][3]&&temp[i][2]==temp[i-1][2]&&temp[i][1]==temp[i-1][1])
cout<<"农夫自己回北岸";
}
cout<<endl;
}
}
else
cout<<"Nosolution."<<endl;
}
int main() /*主函数*/
{
farmerProblem();
return 0;
}