野人与传教士问题A算法.docx
- 文档编号:18546590
- 上传时间:2023-08-19
- 格式:DOCX
- 页数:16
- 大小:23.11KB
野人与传教士问题A算法.docx
《野人与传教士问题A算法.docx》由会员分享,可在线阅读,更多相关《野人与传教士问题A算法.docx(16页珍藏版)》请在冰点文库上搜索。
野人与传教士问题A算法
野人与传教士问题(A*算法)
SY0903620赵磊
一、实验题目
请用A*算法实现传教士和野人问题
问题:
设有3个传教士和3个野人来到河边,打算乘一只船从右岸渡到左岸去。
该船的负载能力为两人。
在任何时候,如果野人人数超过传教士人数,那么野人就会把传教士吃掉。
他们怎样才能用这条船安全地把所有人都渡过河去?
算法设计要求给出:
状态表示,规则库,启发函数等
二、实验目的
通过具体问题的编程求解,利用A*算法解决此经典问题,了解人工智能的启发式搜索算法的基本过程与原理。
三、设计思想
1、编程工具
采用C++语言在VisualStudio6.0环境下编写;
2、整体思想
(1)把初始结点So放入OPEN表中,计算f(So)。
(2)如果OPEN为空,则搜索失败,退出。
(3)把OPEN中的第一个节点(记为节点n)从表中移出放入CLOSED表。
(4)考察节点n是否为目标节点。
若是,则求得问题的解,退出。
(5)若节点n不可扩展,则转第
(2)步。
(6)扩展节点n,用估价函数f(x)计算每个子节点的估价值,并为每个子节点配置指向父节点的指针,把这些子节点都送到OPEN表中,然后对OPEN表中的全部节点按估价值从小到大的顺序排列。
3、具体说明
用A*算法求解传教士与野人问题。
M=C=5,K=3。
节点估价值设为f(n)=h(n)+g(n),g(n)设为节点搜索深度,而h(n)=m(n)+c(n)-2b(n),其中m:
河左岸的传教士人数;c:
河左岸的野人人数;b:
船是否在左岸,1:
表示在左岸,0:
表示不在左岸。
采用结构体定义形式,定义状态节点*NewNode(intm,intc,intb),其中包含m左岸传教士人数、c左岸野人人数、b船状态(左或右)。
开始状态为(3,3,1),目标状态为(0,0,0)。
若需要条件满足,即任何时候,如果野人人数超过传教士人数,那么野人就会把传教士吃掉,要对状态结点的安全性进行判断,判断一个状态是否为安全的,即是否满足在河的任何一岸,传教士人数不少于野人人数,或者只有野人而没有传教士。
对于超出参数范围的状态,也认为是不安全的。
即判断:
if(pNode->m<0||
pNode->c<0||
pNode->m>M||
pNode->c>M)return0;
if(pNode->m==M||
pNode->m==0)return1;
要扩展节点n生成其全部后继节点.对于n的每一个后继节点m配置指向父节点的指针时:
a)计算f(m)
b)如果m既不在OPEN表中,也不在CLOSED表中,则用估价函数f把它添入OPEN表.从m加一指向父辈节点n的指针。
c)如果m已在OPEN表或CLOSED表上,则比较刚刚对m计算过的值f和前面计算过的该节点在表中的f值.如果新的f值较小,则
I.以此新值取代旧值
II.从m指向n,而不是指向它的父辈节点
III.如果节点m在CLOSED表中,则把它移回OPEN表
四、具体函数功能
1)
intEqual(structNODE*pNode1,structNODE*pNode2)
功能:
判断两个节点所表示的状态是否相等
入口参数:
pNode1:
指向节点1的指针
pNode2:
指向节点2的指针
返回值:
当两个节点所表示的状态相等时,返回1,否则返回0
2)
structNODE*NewNode(intm,intc,intb)
功能:
动态产生一个节点,其状态值由参数m,c,b给定。
入口参数:
m:
河左岸的传教士人数
c:
河左岸的野人人数
b:
船是否在左岸,1:
表示在左岸,0:
表示不在左岸
返回值:
指向新产生的节点的指针,或者空间不够时,返回NULL
3)
voidFreeList(structNODE*pList)
功能:
释放动态产生的链表
入口参数:
pList:
指向OPEN表或者CLOSED表的指针
返回值:
无
4)
structNODE*In(structNODE*pNode,structNODE*pList)
功能:
判断一个节点是否在一个链表中
入口参数:
pNode:
指向给定节点的指针
pList:
指向给点链表的指针
返回值:
当pNode在pList中时,返回以pNode为首的链表
的后一部分;否则返回NULL
5)
structNODE*Del(structNODE*pNode,structNODE*pList)
功能:
从链表pList中删除节点pNode
入口参数:
pNode:
指向给定节点的指针
pList:
指向给定的链表
返回值:
删除给定节点后的链表
6)
structNODE*AddToOpen(structNODE*pNode,structNODE*pOpen)
功能:
将一个节点按照f值(从小到大)插入到OPEN表中
入口参数:
pNode:
指向给定节点的指针
pOpen:
指向OPEN表的指针
返回值:
指向插入给定节点后OPEN表的指针
注意:
同一个节点(具有相同指针的一个节点),只能向表中添加一次,否则可能会造成循环链表
7)
structNODE*AddToClosed(structNODE*pNode,structNODE*pClosed)
功能:
将一个节点插入到CLOSED表中
入口参数:
pNode:
指向给定节点的指针
pClosed:
指向CLOSED表的指针
返回值:
指向插入给定节点后CLOSED表的指针
注意:
同一个节点(具有相同指针的一个节点),只能向表中添加一次,否则可能会造成循环链表
8)
voidPrintList(structNODE*pList)
功能:
在屏幕上打印一个链表,用于调试程序
入口参数:
pList:
指向链表的指针
返回值:
无
9)
voidPrintNode(structNODE*pNode)
功能:
在屏幕上打印一个节点,用于调试程序
入口参数:
pNode:
指向节点的指针
返回值:
无
10)
voidPrintPath(structNODE*pGoal)
功能:
在屏幕上打印解路径。
在搜索过程中,每个节点指向其父节点,从目标节点开始,逆向打印各节点,既得到解路径
入口参数:
pGoal:
指向求解得到的目标节点
返回值:
无
11)
intIsGrandFather(structNODE*pNode,structNODE*pFather)
功能:
判断一个节点是否与自己的祖父节点所表示的状态一样
入口参数:
pNode:
指向给定节点的指针
pFather:
指向给定节点的父节点的指针
返回值:
当给定节点所表示的状态与自己的祖父一样时,返回1,否则返回0
12)
intIsGoal(structNODE*pNode)
功能:
判断给定节点是否为目标节点
入口参数:
pNode:
指向给定节点的指针
返回值:
当给定节点是目标节点时,返回1,否则返回0
13)
intSafe(structNODE*pNode)
功能:
判断一个状态是否为安全的,即是否满足在河的任何一岸,传教士人数不少于野人人数,或者只有野人而没有传教士。
对于超出参数范围的状态,也认为是不安全的
入口参数:
pNode:
指向给定节点的指针
返回值:
当给定节点安全时,返回1,否则返回0
14)
intH_Function(structNODE*pNode)
功能:
计算给定节点的h值,h=m+c-2b
入口参数:
pNode:
指向给定节点的指针
返回值:
h值
15)
structNODE*A_Star(structNODE*s)
功能:
A*算法主函数
入口参数:
s:
指向初始节点的指针
返回值:
指向求解得到的目标节点的指针,或者返回NULL表示空间不够用或者找不到问题的解
五、程序源代码
#defineM3//传教士总人数
#defineC3//野人总人数
#defineK2//船一次可以乘坐的最多人数
structNODE
{
intm;//在左岸的传教士人数
intc;//在左岸的野人人数
intb;//b=1表示船在左岸,b=0表示船在右岸
doubleg;//该节点的g值
doublef;//该节点的f值
structNODE*pFather;//指向该节点的父节点
structNODE*pNext;//在OPEN表或者CLOSED表中,指向下一个元素
};
structNODE*g_pOpen=NULL;//全程变量,OPEN表
structNODE*g_pClosed=NULL;//全程变量,CLOSED表
intEqual(structNODE*pNode1,structNODE*pNode2)
{
if(pNode1->m==pNode2->m&&
pNode1->c==pNode2->c&&
pNode1->b==pNode2->b)return1;
elsereturn0;
}
structNODE*NewNode(intm,intc,intb)
{
structNODE*pNode=NULL;
pNode=malloc(sizeof(structNODE));
if(pNode==NULL)returnNULL;
pNode->m=m;
pNode->c=c;
pNode->b=b;
pNode->g=0;
pNode->f=0;
pNode->pFather=NULL;
pNode->pNext=NULL;
returnpNode;
}
voidFreeList(structNODE*pList)
{
structNODE*pNode=NULL;
while(pList)
{
pNode=pList;
pList=pList->pNext;
free(pNode);
}
}
structNODE*In(structNODE*pNode,structNODE*pList)
{
if(pList==NULL)returnNULL;
if(Equal(pNode,pList))returnpList;
returnIn(pNode,pList->pNext);
}
structNODE*Del(structNODE*pNode,structNODE*pList)
{
if(pList==NULL)returnpList;
if(Equal(pNode,pList))returnpList->pNext;
pList->pNext=Del(pNode,pList->pNext);
returnpList;
}
structNODE*AddToOpen(structNODE*pNode,structNODE*pOpen)
{
if(pOpen==NULL)//OPEN表为空
{
pNode->pNext=NULL;
returnpNode;
}
if(pNode->f
{
pNode->pNext=pOpen;//插入到OPEN的最前面
returnpNode;
}
pOpen->pNext=AddToOpen(pNode,pOpen->pNext);//递归
returnpOpen;
}
structNODE*AddToClosed(structNODE*pNode,structNODE*pClosed)
{
pNode->pNext=pClosed;
returnpNode;
}
voidPrintList(structNODE*pList)
{
while(pList)//依次打印链表
{
printf("((%d%d%d)%f%f)\n",pList->m,pList->c,pList->b,pList->g,pList->f);
pList=pList->pNext;
}
}
voidPrintNode(structNODE*pNode)
{
printf("((%d%d%d)%f%f)\n",pNode->m,pNode->c,pNode->b,pNode->g,pNode->f);
}
voidPrintPath(structNODE*pGoal)
{
if(pGoal==NULL)return;
PrintPath(pGoal->pFather);//递归
printf("(%d%d%d)\n",pGoal->m,pGoal->c,pGoal->b);
}
intIsGrandFather(structNODE*pNode,structNODE*pFather)
{
if(pFather==NULL)return0;
if(pFather->pFather==NULL)return0;
returnEqual(pNode,pFather->pFather);
}
intIsGoal(structNODE*pNode)
{
if(pNode->m==0&&
pNode->c==0&&
pNode->b==0)return1;
elsereturn0;
}
intSafe(structNODE*pNode)
{
if(pNode->m<0||
pNode->c<0||
pNode->m>M||
pNode->c>M)return0;
if(pNode->m==M||
pNode->m==0)return1;
return(pNode->m==pNode->c);
}
intH_Function(structNODE*pNode)
{
returnpNode->m+pNode->c-2*pNode->b;
}
structNODE*A_Star(structNODE*s)
{
structNODE*n=NULL,*m=NULL,*pNode=NULL;
inti,j;
g_pOpen=s;//初始化OPEN表和CLOSED表
g_pClosed=NULL;
while(g_pOpen)//OPEN表不空
{
n=g_pOpen;//取出OPEN表的第一个元素n
if(IsGoal(n))returnn;//如果n为目标节点,则成功结束
g_pOpen=g_pOpen->pNext;//否则,从OPEN表中删除n
g_pClosed=AddToClosed(n,g_pClosed);//将n加入到CLOSED中
//以下两重循环,i表示上船的传教士人数,j表示上船的野人人数
for(i=0;i<=K;i++)
{
for(j=0;j<=K;j++)
{
if(i+j==0||//非法的上船组合
i+j>K||
(i!
=0&&i if(n->b==1)//当船在左岸时 { m=NewNode(n->m-i,n->c-j,0);//产生下一个状态m } else//当船在右岸时 { m=NewNode(n->m+i,n->c+j,1);//产生下一个状态m } if(m==NULL)returnNULL;//如果空间不够用,则失败结束 if(IsGrandFather(m,n)||! Safe(m)){ free(m); continue; } m->pFather=n;//标记其父节点为n m->g=n->g+1;//其g值为其父节点的g值加1 m->f=m->g+H_Function(m);//计算其f值,f=g+h if(pNode=In(m,g_pOpen))//如果m已经出现在OPEN表中 { if(m->f { //则将该节点从OPEN表中删除,并将m加入到OPEN表中。 g_pOpen=AddToOpen(m,Del(pNode,g_pOpen)); free(pNode); } else//否则舍弃m { free(m); } } elseif(pNode=In(m,g_pClosed))//如果m已经出现在CLOSED中 { if(m->f { //则将该节点从CLOSED表中删除,并重新添加到OPEN表中 g_pClosed=Del(pNode,g_pClosed); g_pOpen=AddToOpen(m,g_pOpen); free(pNode); } else//否则舍弃m节点 { free(m); } } else//其他情况,将m加入到OPEN表中 { g_pOpen=AddToOpen(m,g_pOpen); } } } } //如果OPEN表空了,还没有找到目标节点,则搜索以失败结束, //返回NULL returnNULL; } voidmain(void) { structNODE*s; s=NewNode(M,C,1);//设置初始节点 s=A_Star(s);//A*搜索 if(s)PrintPath(s);//如果找到问题的解,则输出解路径 elseprintf("找不到问题的解! /n"); FreeList(g_pOpen);//释放动态节点 FreeList(g_pClosed); } 六、结果显示
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 野人 传教士 问题 算法