大工20春《人工智能》大作业题目及要求Word文件下载.docx
《大工20春《人工智能》大作业题目及要求Word文件下载.docx》由会员分享，可在线阅读，更多相关《大工20春《人工智能》大作业题目及要求Word文件下载.docx（36页珍藏版）》请在冰点文库上搜索。
constintROW=3;
//行数
constintCOL=3;
//列数
constintMAXDISTANCE=10000;
//最多可以有的表的数目
constintMAXNUM=10000;
typedefstruct_Node{
intdigit[ROW][COL];
intdist;
//一个表和目的表的距离
intdep;
//t深度
intindex;
//节点的位置
}Node;
Nodesrc,dest;
//父节表目的表
vector<
Node>
node_v;
//存储节点
boolisEmptyOfOPEN（）//open表是否为空
{
for（inti=0;
i<
node_v.size（）;
i++）{
if（node_v[i].dist!
=MAXNUM）
returnfalse;
}
returntrue;
boolisEqual（intindex,intdigit[][COL]）//判断这个最优的节点是否和目的节点一样
ROW;
i++）
for（intj=0;
j<
COL;
j++）{
if（node_v[index].digit[i][j]!
=digit[i][j]）
ostream&
operator<
<
（ostream&
os,Node&
node）
j++）
os<
node.digit[i][j]<
'
;
endl;
returnos;
voidPrintSteps（intindex,vector<
&
rstep_v）//输出每一个遍历的节点深度遍历
rstep_v.push_back（node_v[index]）;
index=node_v[index].index;
while（index!
=0）
for（inti=rstep_v.size（）-1;
i>
=0;
i--）//输出每一步的探索过程
cout<
"
Step"
<
rstep_v.size（）-i
endl<
rstep_v[i]<
voidSwap（int&
a,int&
b）
intt;
t=a;
a=b;
b=t;
voidAssign（Node&
node,intindex）
node.digit[i][j]=node_v[index].digit[i][j];
intGetMinNode（）//找到最小的节点的位置即最优节点
intdist=MAXNUM;
intloc;
//thelocationofminimizenode
if（node_v[i].dist==MAXNUM）
continue;
elseif（（node_v[i].dist+node_v[i].dep）<
dist）{
loc=i;
dist=node_v[i].dist+node_v[i].dep;
returnloc;
boolisExpandable（Node&
if（isEqual（i,node.digit））
intDistance（Node&
node,intdigit[][COL]）
intdistance=0;
boolflag=false;
for（inti=0;
for（intk=0;
k<
k++）{
for（intl=0;
l<
l++）{
if（node.digit[i][j]==digit[k][l]）{
distance+=abs（i-k）+abs（j-l）;
flag=true;
break;
else
flag=false;
if（flag）
returndistance;
intMinDistance（inta,intb）
return（a<
b?
a:
b）;
voidProcessNode（intindex）
intx,y;
boolflag;
if（node_v[index].digit[i][j]==0）
x=i;
y=j;
elseflag=false;
if（flag）
Nodenode_up;
Assign（node_up,index）;
//向上扩展的节点
intdist_up=MAXDISTANCE;
if（x>
0）
Swap（node_up.digit[x][y],node_up.digit[x-1][y]）;
if（isExpandable（node_up））
dist_up=Distance（node_up,dest.digit）;
node_up.index=index;
node_up.dist=dist_up;
node_up.dep=node_v[index].dep+1;
node_v.push_back（node_up）;
Nodenode_down;
Assign（node_down,index）;
//向下扩展的节点
intdist_down=MAXDISTANCE;
if（x<
2）
Swap（node_down.digit[x][y],node_down.digit[x+
1][y]）;
if（isExpandable（node_down））
dist_down=Distance（node_down,dest.digit）;
node_down.index=index;
node_down.dist=dist_down;
node_down.dep=node_v[index].dep+1;
node_v.push_back（node_down）;
Nodenode_left;
Assign（node_left,index）;
//向左扩展的节点
intdist_left=MAXDISTANCE;
if（y>
Swap（node_left.digit[x][y],node_left.digit[x][y-1]）;
if（isExpandable（node_left））
dist_left=Distance（node_left,dest.digit）;
node_left.index=index;
node_left.dist=dist_left;
node_left.dep=node_v[index].dep+1;
node_v.push_back（node_left）;
Nodenode_right;
Assign（node_right,index）;
//向右扩展的节点
intdist_right=MAXDISTANCE;
if（y<
Swap（node_right.digit[x][y],node_right.digit[x][y+1]）;
if（isExpandable（node_right））
dist_right=Distance（node_right,dest.digit）;
node_right.index=index;
node_right.dist=dist_right;
node_right.dep=node_v[index].dep+1;
node_v.push_back（node_right）;
node_v[index].dist=MAXNUM;
intmain（）//主函数
intnumber;
Inputsource:
"
i++）//输入初始的表
cin>
>
number;
src.digit[i][j]=number;
src.index=0;
src.dep=1;
Inputdestination:
//输入目的表
for（intm=0;
m<
m++）
for（intn=0;
n<
n++）{
dest.digit[m][n]=number;
node_v.push_back（src）;
//在容器的尾部加一个数据
Search..."
clock_tstart=clock（）;
while
（1）
if（isEmptyOfOPEN（））
Cann'
tsolvethisstatement!
return-1;
//thelocationoftheminimizenode最优节点的位置
loc=GetMinNode（）;
if（isEqual（loc,dest.digit））
rstep_v;
Source:
src<
PrintSteps（loc,rstep_v）;
Successful!
Using"
（clock（）-start）/CLOCKS_PER_SEC
seconds."
ProcessNode（loc）;
return0;
四、程序运行效果图
2
8
3
1
6
4
7
5
（初始状态）
（结束状态）
五、对于重排九宫问题的启发式函数
给定九宫格的初始状态，要求在有限步的操作内，使其转化为目标状态，且所得到的解是代价最小解（即移动的步数最少）。
如：
初始格局
目标状态
#include"
iostream.h"
time.h>
stdio.h>
dos.h>
conio.h>
staticinttarget[9]={1,2,3,8,0,4,7,6,5};
//classdefinition
classeight_num
private:
intnum[9];
intnot_in_position_num;
intdeapth;
inteva_function;
public:
eight_num*parent;
eight_num*leaf_next;
eight_num*leaf_pre;
eight_num（intinit_num[9]）;
eight_num（intnum1,intnum2,intnum3,intnum4,int
num5,intnum6,intnum7,intnum8,intnum9）
num[0]=num1;
num[1]=num2;
num[2]=num3;
num[3]=num4;
num[4]=num5;
num[5]=num6;
num[6]=num7;
num[7]=num8;
num[8]=num9;
eight_num（void）
for（inti=0;
i<
9;
i++）
num[i]=i;
voidcul_para（void）;
voidget_numbers_to（intother_num[9]）;
intget_nipn（void）
{returnnot_in_position_num;
intget_deapth（void）
{returndeapth;
intget_evafun（void）
{returneva_function;
voidset_num（intother_num[9]）;
voidshow（void）;
eight_num&
operator=（eight_num&
）;
operator=（intother_num[9]）;
intoperator==（eight_num&
intoperator==（intother_num[9]）;
};
//计算启发函数g（n）的值
voideight_num:
:
cul_para（void）
inti;
inttemp_nipn=0;
for（i=0;
if（num[i]!
=target[i]）
temp_nipn++;
not_in_position_num=temp_nipn;
if（this->
parent==NULL）
deapth=0;
deapth=this->
parent->
deapth+1;
eva_function=not_in_position_num+deapth;
//构造函数1
eight_num:
eight_num（intinit_num[9]）
num[i]=init_num[i];
//显示当前节点的状态
show（）
cout<
num[0];
num[1];
num[2];
\n"
num[3];
num[4];
num[5];
num[6];
num[7];
num[8];
//复制当前节点状态到一个另数组中
get_numbers_to（intother_num[9]）
other_num[i]=num[i];
//设置当前节点状态（欲设置的状态记录的other数组中）
set_num（intother_num[9]）
num[i]=other_num[i];
eight_num:
operator=（eight_num&
another_8num）
num[i]=another_8num.num[i];
not_in_position_num=another_8num.not_in_position_num;
deapth=another_8num.deapth+1;
return*this;
operator=（intother_num[9]）
inteight_num:
operator==（eight_num&
intmatch=1;
if（num[i]!
=another_8num.num[i]）
match=0;
if（match==0）
return1;
operator==（intother_num[9]）
=other_num[i]）
//classdefinitionover
//空格向上移
intmove_up（intnum[9]）
if（num[i]==0）
if（i<
3）
num[i]=num[i-3];
num[i-3]=0;
//空格向下移
intmove_down（intnum[9]）
if（i>
5）
num[i]=num[i+3];
num[i+3]=0;
//空格向左移
intmove_left（intnum[9]）
if（i==0||i==3||i==6）
num[i]=num[i-1];
num[i-1]=0;
//空格向右移
intmove_right（intnum[9]）
if（i==2||i==5||i==8）
num[i]=num[i+1];
num[i+1]=0;
//判断可否解出
inticansolve（intnum[9],inttarget[9]）
inti,j;
intcount_num,count_target;
for（j=0;
j<
i;
j++）
if（num[j]<
num[i]&
num[j]!
=0）
count_num++;
if（target[j]<
target[i]&
target[j]!
count_target++;
if（（count_num+count_target）%2==0）
升级会员 