启发式搜索算法.docx

人工智能基础实验报告
实验名称：八数码问题
姓名：张俊
学号：2220092333
指导老师：邓安生
启发式搜索算法
.实验内容：
使用启发式搜索算法求解 8数码问题。
编制程序实现求解 8数码问题A算法，采用估价函数
{
if(num[j]==i)h1=j;
if(target[j]==i)h2=j;
}
qifa+=(int)(fabs((double)(h1/3 - h2/3)) + fabs((double)(h1%3 - h2%3)));
}
qifa=3*qifa;
break;
}
default :break;
}
f=qifa;
if(this->parent==NULL) deap=0;
else deap=this->parent->deap+1;
evalfun=deap+f;
int EightNum二Canspread(int n)
{〃判断空格"0"可否移动
int i,flag = 0;
for(i = 0;i < 9;i++)
if(this->num[i] == 0)break;
switch(n)
{
if(i/3 != 0)flag = 1;break;
if(i/3 != 2)flag = 1;break;
if(i%3 != 0)flag = 1;break;
if(i%3 != 2)flag = 1;break;
default:break;
}
return flag ;
}
void EightNum::Spreadchild(int n)
{〃扩展child节点的子节点
int i,loc,qifa;
for(i = 0;i < 9;i++)
this->num[i] = this->parent->num[i];
for(i = 0;i < 9;i++)
if(this->num[i] == 0)break;
if(n==0)
loc = i%3+(i/3 - 1)*3;
else if(n==1)
loc = i%3+(i/3 + 1)*3;
else if(n==2)
else
loc = i%3+1+(i/3)*3;
qifa = this->num[loc];
this->num[i] = qifa;
this->num[loc] = 0;
}
void EightNum::getnum(int num1[9]){
for(int i=0;i<9;i++)
num1[i]=num[i];
}
void EightNum::setnum(int num1[9]){
for(int i=0;i<9;i++)
num[i]=num1[i];
}
void EightNum::show(){// 输出函数
for(int i=0;i<9;i++){ cout<<num[i]<<" ";
if((i+1)%3==0)
cout<<"\n";
}
cout<<" ";
}
int EightNum::Shownum()
if(this == NULL)return 0;
else
(
int n = this->parent->Shownum();
this->show();
cout<<endl;
return n+1;
}
}
int EightNum::operator ==(EightNum& NewEightN){
int compere=1;
for(int i=0;i<9;i++)
if(num[i]!=[i]){
compere=0;
break;
}
if(compere==0) return 0;
else return 1;
}
// 以下为分函数的定义 //
〃判断是否有解的函数
int solve(int num[9],int target[9]){
int i,j;
int num_con=0,tar_con=0;
for(i=0;i<9;i++)
for(j=0;j<i;j++){
if(num[j]<num[i] && num[j]!=0)
num_con++;
if(target[j]<target[i] && target[j]!=0)
tar_con++;
}
num_con=num_con%2;
tar_con=tar_con%2;
if((num_con==0 && tar_con==0)||(num_con==1 && tar_con==1))
return 1;
else
r