人工智能实验报告知识表示方法.docx
《人工智能实验报告知识表示方法.docx》由会员分享,可在线阅读,更多相关《人工智能实验报告知识表示方法.docx(36页珍藏版)》请在冰点文库上搜索。
人工智能实验报告知识表示方法
江苏科技大学
实验报告
(2012/2013学年第2学期)
课程名称:
人工智能
学生姓名:
学生学号:
院系:
数理学院
专业:
信息与计算科学
2013年5月18日
实验一:
知识表示方法
一、实验目的
状态空间表示法是人工智能领域最基本的知识表示方法之一,也是进一步学习状态空间搜索策略的基础,本实验通过牧师与野人渡河的问题,强化学生对知识表示的了解和应用,为人工智能后续环节的课程奠定基础。
二、问题描述
有n个牧师和n个野人准备渡河,但只有一条能容纳c个人的小船,为了防止野人侵犯牧师,要求无论在何处,牧师的人数不得少于野人的人数(除非牧师人数为0),且假定野人与牧师都会划船,试设计一个算法,确定他们能否渡过河去,若能,则给出小船来回次数最少的最佳方案。
三、基本要求
输入:
牧师人数(即野人人数):
n;小船一次最多载人量:
c。
输出:
若问题无解,则显示Failed,否则,显示Successed输出一组最佳方案。
用三元组(X1,X2,X3)表示渡河过程中的状态。
并用箭头连接相邻状态以表示迁移过程:
初始状态->中间状态->目标状态。
例:
当输入n=2,c=2时,输出:
221->110->211->010->021->000
其中:
X1表示起始岸上的牧师人数;X2表示起始岸上的野人人数;X3表示小船现在位置(1表示起始岸,0表示目的岸)。
要求:
写出算法的设计思想和源程序,并以图形用户界面实现人机交互,进行输入和输出结果,如:
Pleaseinputn:
2Pleaseinputc:
2
SuccessedorFailed?
:
Successed
OptimalProcedure:
221->110->211->010->021->000
四、实验组织运行要求
本实验采用集中授课形式,每个同学独立完成上述实验要求。
五、实验条件
每人一台计算机独立完成实验。
六、实验代码
Main.cpp
#include
#include"RiverCrossing.h"
usingnamespacestd;
//主函数
voidmain()
{
RiverCrossing:
:
ShowInfo();
intn,c;
cout<<"Pleaseinputn:
";
cin>>n;
cout<<"Pleaseinputc:
";
cin>>c;
RiverCrossingriverCrossing(n,c);
riverCrossing.solve();
system("pause");
}
RiverCrossing.h
#pragmaonce
#include
//船
classBoat
{
public:
staticintc;
intpastor;//牧师
intsavage;//野人
Boat(intpastor,intsavage);
};
//河岸状态
classState
{
public:
staticintn;
intiPastor;//牧师数量
intiSavage;//野人数量
intiBoatAtSide;//船所在河岸
State*pPrevious;//前一个状态
State(intpastor,intsavage,intboatAtSide);
intgetTotalCount();//获得此岸总人数
boolcheck();//检查人数是否符合实际
boolisSafe();//检查是否安全
Stateoperator+(Boat&boat);
Stateoperator-(Boat&boat);
booloperator==(State&state);
};
//过河问题
classRiverCrossing
{
private:
std:
:
listopenList,closeList;
StateendState;
boolmove(State*nowState,Boat*boat);//进行一次决策
State*findInList(std:
:
list&listToCheck,State&state);//检查某状态节点是否在列表中
voidprint(State*endState);//打印结果
public:
staticvoidShowInfo();
RiverCrossing(intn,intc);
boolsolve();//求解问题
};
RiverCrossing.cpp
#include"RiverCrossing.h"
#include
#include
#include
usingnamespacestd;
//类静态变量定义
intState:
:
n=0;
intBoat:
:
c=0;
/*=========================Methodsforclass"Boat"=========================*/
Boat:
:
Boat(intpastor,intsavage)
{
this->pastor=pastor;
this->savage=savage;
}
/*=========================Methodsforclass"State"=========================*/
//构造函数
State:
:
State(intpastor,intsavage,intboatAtSide)
{
this->iPastor=pastor;
this->iSavage=savage;
this->iBoatAtSide=boatAtSide;
this->pPrevious=NULL;
}
//获取此岸总人数
intState:
:
getTotalCount()
{
returniPastor+iSavage;
}
//检查人数是否在0到n之间
boolState:
:
check()
{
return(iPastor>=0&&iPastor<=n&&iSavage>=0&&iSavage<=n);
}
//按照规则检查牧师得否安全
boolState:
:
isSafe()
{
//此岸的安全:
x1==0||x1>=x2
//彼岸的安全:
(n-x1)==0||(n-x1)>=(n-x2)
//将上述条件联立后得到如下条件
return(iPastor==0||iPastor==n||iPastor==iSavage);
}
//重载+符号,表示船开到此岸
StateState:
:
operator+(Boat&boat)
{
Stateret(iPastor+boat.pastor,iSavage+boat.savage,iBoatAtSide+1);
ret.pPrevious=this;
returnret;
}
//重载-符号,表示船从此岸开走
StateState:
:
operator-(Boat&boat)
{
Stateret(iPastor-boat.pastor,iSavage-boat.savage,iBoatAtSide-1);
ret.pPrevious=this;
returnret;
}
//重载==符号,比较两个节点是否是相同的状态
boolState:
:
operator==(State&state)
{
return(this->iPastor==state.iPastor&&this->iSavage==state.iSavage&&this->iBoatAtSide==state.iBoatAtSide);
}
/*=======================Methodsforclass"RiverCrossing"=======================*/
//显示信息
voidRiverCrossing:
:
ShowInfo()
{
cout<<"************************************************"<cout<<"牧师与野人过河问题求解"<cout<<"by1040501211陈嘉生"<cout<<"************************************************"<}
//构造函数
RiverCrossing:
:
RiverCrossing(intn,intc)
:
endState(0,0,0)
{
State:
:
n=n;
Boat:
:
c=c;
}
//解决问题
boolRiverCrossing:
:
solve()
{
openList.push_back(newState(State:
:
n,State:
:
n,1));
while(!
openList.empty()){
//获取一个状态为当前状态
State*nowState=openList.front();
openList.pop_front();
closeList.push_back(nowState);
//从当前状态开始决策
if(nowState->iBoatAtSide==1){//船在此岸
//过河的人越多越好,且野人优先
intcount=nowState->getTotalCount();
count=(Boat:
:
c>=count?
count:
Boat:
:
c);
for(intcapticy=count;capticy>=1;--capticy){
for(inti=0;i<=capticy;++i){
Boatboat(i,capticy-i);
if(move(nowState,&boat))
returntrue;
}
}
}elseif(nowState->iBoatAtSide==0){//船在彼岸
//把船开回来的人要最少,且牧师优先
for(intcapticy=1;capticy<=Boat:
:
c;++capticy){
for(inti=0;i<=capticy;++i){
Boatboat(capticy-i,i);
if(move(nowState,&boat))
returntrue;
}
}
}
}
print(NULL);
returnfalse;
}
//实施一步决策,将得到的新状态添加到列表,返回是否达到目标状态
boolRiverCrossing:
:
move(State*nowState,Boat*boat)
{
//获得下一个状态
State*destState;
if(nowState->iBoatAtSide==1){
destState=newState(*nowState-*boat);//船离开此岸
}elseif(nowState->iBoatAtSide==0){
destState=newState(*nowState+*boat);//船开到此岸
}
if(destState->check()){//检查人数
if(*destState==endState){//是否达到目标状态
closeList.push_back(destState);
print(destState);
returntrue;//找到结果
}elseif(destState->isSafe()){//检查是否安全
if(!
findInList(openList,*destState)&&!
findInList(closeList,*destState)){//检查是否在表中
//添加没出现过的状态节点到open表
openList.push_back(destState);
returnfalse;
}
}
}
deletedestState;
returnfalse;
}
//检查给定状态是否存在于列表中
State*RiverCrossing:
:
findInList(list&listToCheck,State&state)
{
for(list:
:
iteratorite=listToCheck.begin();ite!
=listToCheck.end();++ite){
if(**ite==state)
return*ite;
}
returnNULL;
}
//根据达到的目标状态,回溯打印出求解过程
voidRiverCrossing:
:
print(State*endState)
{
cout<<"================================================"<if(!
endState){
cout<<"Searchfailed!
"<}else{
cout<<"Searchsuccessed!
"<cout<<"OptimalProcedure:
"<State*pState=endState;
stackst;//用栈将链表逆序,以便输出
while(pState){
st.push(pState);
pState=pState->pPrevious;
}
intcount=0;
while(!
st.empty()){
pState=st.top();
st.pop();
cout<iPastor<<","<iSavage<<","<iBoatAtSide;
if(st.size()>0)
cout<<"->";
if(++count%5==0)//每五个步骤换行
cout<}
cout<cout<<"Totalmove:
"<}
cout<<"================================================"<}
七、实验结果
实验二:
九宫重排
一、实验目的
A*算法是人工智能领域最重要的启发式搜索算法之一,本实验通过九宫重排问题,强化学生对A*算法的理解与应用,为人工智能后续环节的课程奠定基础。
二、问题描述
给定九宫格的初始状态,要求在有限步的操作内,使其转化为目标状态,且所得到的解是代价最小解(即移动的步数最少)。
如:
三、基本要求
输入:
九宫格的初始状态和目标状态
输出:
重排的过程,即途径的状态
四、实验组织运行要求
本实验采用集中授课形式,每个同学独立完成上述实验要求。
五、实验条件
每人一台计算机独立完成实验。
六、实验代码
Main.cpp
#include
#include"NineGrid.h"
usingnamespacestd;
//主函数
voidmain()
{
NineGrid:
:
ShowInfo();
stringstart,end;
cout<<"Pleaseinputtheinitialstate:
(ex:
134706582)"<cin>>start;
cout<<"Pleaseinputthetargetstate:
(ex:
123804765)"<cin>>end;
NineGridnineGrid(start,end);
nineGrid.solve();
system("pause");
}
NineGrid.h
#pragmaonce
#include
#include
#include
usingnamespacestd;
#defineSPACE'0'
#defineAT(s,x,y)(s)[(x)*3+(y)]
enumMove{
UP=0,DOWN=1,LEFT=2,RIGHT=3
};
//九宫格状态
classState
{
public:
staticState*pEndState;//指向目标状态,用于评价h的值
stringgrid;//用字符串保存当前棋盘状态
intx,y;//空格所在位置
intmoves;//到此状态的移动次数
intvalue;//价值
State*pPrevious;//前一个状态
State(string&grid,State*pPrevious=NULL);
intgetReversedCount();//获取逆序数
voidevaluate();//评价函数
boolcheck(Movemove);//检查是否可以移动
StatetakeMove(Movemove);//实施移动,生成子状态
//重载==运算符,判断两个状态是否相等
inlinebooloperator==(State&state){returngrid==state.grid;}
};
//九宫重排问题
classNineGrid
{
private:
vectoropenList,closeList;
StatestartState,endState;
clock_tstartTime;
boolcompareReversed();//比较逆序数奇偶性是否相同
booltakeMove(State*nowState,Movemove);//进行一次决策
State*findInList(vector&listToCheck,State&State);//检查某状态节点是否在列表中
voidprint(State*endState);//打印结果
//用于排序
staticboolgreater_than(constState*state1,constState*state2);
public:
staticvoidShowInfo();//显示信息
NineGrid(string&start,string&dest);
boolsolve();//求解问题
};
NineGrid.cpp
#include"NineGrid.h"
#include
#include
#include
usingnamespacestd;
State*State:
:
pEndState=NULL;
/*=======================Methodsforclass"State"=======================*/
//构造函数
State:
:
State(string&grid,State*pPrevious)
{
this->grid=grid;
this->pPrevious=pPrevious;
if(this->pPrevious)
this->moves=pPrevious->moves+1;
else
this->moves=0;
this->value=0;
evaluate();
for(inti=0;i<3;++i){
for(intj=0;j<3;++j){
if(AT(grid,i,j)==SPACE){
x=i;
y=j;
return;
}
}
}
}
boolState:
:
check(Movemove)
{
switch(move){
caseUP:
if(x-1<0)
returnfalse;
break;
caseDOWN:
if(x+1>=3)
returnfalse;
break;
caseLEFT:
if(y-1<0)
returnfalse;
break;
caseRIGHT:
if(y+1>=3)
returnfalse;
break;
}
returntrue;
}
StateState:
:
takeMove(Movemove)
{
intdestX,destY;
switch(move){
caseUP:
destX=x-1;
destY=y;
break;
caseDOWN:
destX=x+1;
destY=y;
break;
caseLEFT:
destX=x;
destY=y-1;
break;
caseRIGHT:
destX=x;
destY=y+1;
break;
}
stringtGrid=grid;
chart=AT(tGrid,destX,destY);
AT(tGrid,destX,destY)=AT(tGrid,x,y);
AT(tGrid,x,y)=t;
returnState(tGrid,this);
}
voidState:
:
evaluate()
{
if(!
pEndState)
ret