A算法解决野人过河问题
问题描述:
有3个道士,3个野人来到河的左岸,左岸有一条小船,船只能载两个人,任何时候,道士的人数不能小于野人的人数,否则野人就会把道士吃掉,如何用小船把道士和野人都安全的送到右岸……
注:算法在设计的时候考虑的是 m个道士,n个野人,船可载人数为r个,所以改动野人,道士和船可载人数的个数,程序依然可以正确推理
A算法解决代码:
#include<stdio.h>
#include<stdlib.h>
#define d 3 //道士的个数
#define y 3 //野人的个数
#define r 2 //船可载的人数
#define bool int
#define true 1
#define false 0
struct state //状态结构体
{
int ds; //河左岸道士的人数
int yr; //河左岸野人的人数
bool boat; //船的状态,为true时在左岸,为false时在右岸
int depth; //搜索的深度 g(n)
int num; //启发搜索的中的 f(n)
struct state * before; //父节点指针
struct state * next; //下一个节点的指针
};
typedef struct state sta;
bool empty(sta * link) //判断链表是否为空
{
if(link->next==NULL)
return true;
else
return false;
}
sta * getwei(sta * link) //获得链表的尾部指针
{
sta * p=link;
while(p->next!=NULL)
{
p=p->next;
}
return p;
}
void showtest(sta * open) //打印链表中元素的信息
{
sta * p=open->next;
printf("********************************************\n");
while(p!=NULL)
{
printf("%d %d %d\t",p->ds,p->yr,p->boat);
p=p->next;
}
printf("\n");
}
bool hfzt(sta * p) //判断状态节点是否合法
{
if(p->ds==0||p->ds==d|| (p->ds>=p->yr&&(d-p->ds)>=(y-p->yr)) )
return true;
else
return false;
}
bool judgerepeat(sta * pnow,sta * link) //判断状态在链表中是否已出现
{
sta * p;
p = link->next;
while(p!=NULL)
{
if(pnow->ds==p->ds&&pnow->yr==p->yr&&pnow->boat==p->boat)
{
return true;
}
else
{
p=p->next;
}
}
return false;
}
void buildopen(sta * pz,sta * open,sta * close) //构建open表
{
sta * pw = getwei(open);
sta * p;
int i,j; //i 是船上道士数,j是船上野人数
for(i=0;i<=r;i++)
{
for(j=0;j<=r-i;j++)
{
if(i==0&&j==0)
continue;
if(j>i&&i!=0)
continue;
if(pz->boat==true)
{
if(pz->ds<i||pz->yr<j)
continue;
}
if(pz->boat==false)
{
if( (d-pz->ds)<i||(y-pz->yr)<j )
continue;
}
p = (sta *)malloc(sizeof(sta));
if(pz->boat==true)
{
p->ds=pz->ds-i;
p->yr = pz->yr - j;
p->boat =false;
}
else
{
p->ds=pz->ds+i;
p->yr=pz->yr+j;
p->boat=true;
}
if(!hfzt(p)||judgerepeat(p,open)||judgerepeat(p,close))
{
free(p);
continue;
}
p->depth = pz->depth +1;
p->before = pz;
p->num = p->ds + p->yr +p->depth;
p->next=NULL;
pw->next=p;
pw=p;
}
}
}
sta * judgebest(sta * open) //选择最优的状态
{
sta * p1=open;
sta * p2=open->next;
sta * pbest1=open;
sta * pbest2=open->next;
sta * pbest;
while(p2!=NULL)
{
if(p2->num<pbest2->num)
{
pbest2=p2;
pbest1=p1;
}
else
{
p1=p2;
p2=p2->next;
}
}
pbest = pbest2;
pbest1->next = pbest2->next;
return pbest;
}
void buildclose(sta * close,sta * pbest) //构建close表
{
sta * pw= getwei(close);
pw->next= pbest;
pbest->next=NULL;
pw=pbest;
}
bool goal(sta * pg) //判断是否是目标状态
{
if(pg->ds==0&&pg->yr==0&&pg->boat==false)
return true;
else
return false;
}
sta * tuili(sta * open ,sta * close) //推理机
{
sta * p0;
sta * pwclose;
sta * pwopen = open->next;
p0 = judgebest(open);
close->next = p0;
pwclose = close->next;
while(!goal(p0))
{
buildopen(p0,open,close);
//showtest(open);
if(empty(open))
break;
p0 = judgebest(open);
//printf("*****p0 %d %d %d \n",p0->ds,p0->yr,p0->boat);
buildclose(close,p0);
}
return p0;
}
void show(sta * pd) //打印推理出的解法
{
//printf("****************\n");
//printf("pd %d %d %d\n",pd->ds,pd->yr,pd->boat);
sta * link=(sta * )malloc(sizeof(sta));
sta * p;
sta * pw;
link->before=NULL;
link->next=NULL;
pw=link;
while(1)
{
if(pd==NULL)
break;
//printf("pd %d %d %d\n",pd->ds,pd->yr,pd->boat);
p= (sta *)malloc(sizeof(sta));
p->ds=pd->ds;
p->yr=pd->yr;
p->boat = pd->boat;
p->depth=pd->depth;
p->num=pd->num;
p->next=NULL;
pw->next=p;
p->before=pw;
pw=p;
pd=pd->before;
}
//printf("aaaaaaaaaaaaaaaaaaaa\n");
while(pw->before!=NULL)
{
printf("(%d,%d,%d)\n",pw->ds,pw->yr,pw->boat);
pw=pw->before;
}
printf("\n");
}
void chushihua(sta * open,sta * close) //初始化open表和close表
{
sta * p;
open->before=NULL;
open->next=NULL;
p=(sta *)malloc(sizeof(sta)); //初始化第一个状态
p->boat=true;
p->depth=0;
p->ds=d;
p->yr=y;
p->num=0;
p->before=NULL;
p->next=NULL;
open->next=p;
close->next=NULL;
}
int main()
{
sta * dd;
sta * open=(sta *)malloc(sizeof(sta));
sta * close=(sta *)malloc(sizeof(sta));
chushihua(open,close);
dd = tuili(open,close);
printf("道士数: %d 野人数:%d 船可载人数:%d\n",d,y,r);
if(!goal(dd)&&empty(open))
printf("此情况无解!\n");
else
{
printf("具体的解法:\n");
show(dd);
}
return 0;
}
ye-ren-guo-he.zip_river
版权申诉
17 浏览量
2022-09-20
20:37:43
上传
评论
收藏 2KB ZIP 举报
钱亚锋
- 粉丝: 86
- 资源: 1万+