人工智能+野人传教士过河问题c程序+深度优先

//******************************问题描述***************************************
//有三个牧师（也有的翻译为传教士）和三个野人过河，只有一条能装下两个人的船，在
//河的任何一方或者船上，如果野人的人数大于牧师的人数，那么牧师就会有危险.
//初始状态：左岸，3野人，3牧师；
// 右岸，0野人，0牧师；
// 船停在左岸，船上有0个人
//目标状态：左岸，0野人，0牧师；
// 右岸，3野人，3牧师；
// 船停在右岸，船上有0个人；
//******************************************************************************

#include
#include
#define MAX 50 //定义open数组的大小 open数组用来存储所有出现的合法状态
#define MAX1 5 //定义 boatState数组的大小 boatState数组用来存储求解过程中合法的算符
#define M 3 //定义野人的数目
#define C 3 //定义传教士的数目
#define B 2 //定义船的容量
#define S -1 //定义船在哪岸 -1代表左 1代表右
void expand(); //声明函数
void find();
struct state //定义结构体 存储当前状态 其中m表示野人数 c表示传教士数 s表示船在哪岸
{ // f标记该状态是否被扩展过 pre指向该状态的前一状态
int m;
int c;
int s;
int f;
struct state *pre;
};
struct boat //定义结构体 存储算符 m表示船要运走的野人数 c表示要运走的传教士数
{
int m;
int c;
};
struct state open[MAX];//定义open数组和boatState数组
struct boat boatState[MAX1];
int top=0; //定义open数组的下标 指向最后一个元素
int sum=0; //用来存储解的个数
int j=-1; //用来存储算符的个数
//*********************************************************************************
void inist() //初始化算符
{
int m;
int c;
for(m=0;m<=M;m++)
{
for(c=0;c<=C;c++)
{
if((m <= c || c == 0) && (m+c)<=B && (m || c))
{
j++;
boatState[j].m = m;
boatState[j].c = c;
}
}
}
}
//*******************************************************************************
int goal(struct state * p) //判断当前状态是否目标状态
{
if(p->m==0&&p->c==0&&p->s==1) return 1;
else return 0;
}
//******************************************************************************
void print(struct state * p) //输出解
{
printf("第%d个解是：\n",++sum);
struct state * pTemp=p;
struct state temp[MAX];
int i=1;
while(pTemp)
{
temp[i].m=pTemp->m;
temp[i].c=pTemp->c;
temp[i].s=pTemp->s;
i++;
pTemp=pTemp->pre;
}
while(--i)
{
printf("[%d,%d,%d]--",temp[i].m,temp[i].c,temp[i].s);

}
printf("完成\n");
}
//******************************************************************************
void expand(struct state * p)//扩展当前状态
{
p->f=1;
int i=0;
for(;i<=j;i++)
{
int m = p->m + boatState[i].m * p->s;
int c = p->c + boatState[i].c * p->s;
int s = (-1)*p->s;
int m1 = M - m;
int c1 = C - c;
if ((m <= c || c == 0) &&(m1 <= c1 || c1 == 0) && m >=0 && c >=0 && m1 >=0 && c1 >= 0)
{
int flag=1;
struct state * pTemp=p;
while (pTemp->pre != 0)
{
if (pTemp->pre->m == m && pTemp->pre->c == c && pTemp->pre->s ==s)
{
flag=0;
break;
}
pTemp=pTemp->pre;
}
if(flag)
{
top++;
open[top].m=m;
open[top].c=c;
open[top].s=s;
open[top].f=0;
open[top].pre=p;
}
}
}
p=&open[top];
find(p);
}
//******************************************************************************
void find(struct state * p) //查找解过程
{
int i;
for (i=top;i>=0;)
{
if (!(p->f))
{
if(goal(p))
{
print(p);
p->f=1;
continue;
}
else expand(p);
break;
}
else p=&open[--i];
}
}
//******************************************************************************
int main(int argc, char *argv[])
{

struct state *pHead;
pHead=open;
open[top].m=M;
open[top].c=C;
open[top].s=S;
open[top].f=0;
open[top].pre=0;
inist();
find(pHead);
system("PAUSE");
return 0;
}
//****************编于2008年10月13日 蔡志庆 九江学院 信息A051202*********************