实验二：九宫重排
一、实验目的
A*算法是人工智能领域最重要的启发式搜索算法之一，本实验通过九宫重排问题，强化学生对A*算法的理解与应用，为人工智能后续环节的课程奠定基础。
二、问题描述
给定九宫格的初始状态，要求在有限步的操作内，使其转化为目标状态，且所得到的解是代价最小解(即移动的步数最少)。如：
三、实验原理
如果使一般搜索过程满足如下限制，则它就称为A*算法：
1、把OPEN表中的节点按估价函数f(x)=g(x)+h(x)的值从小至大进行排序（一般搜索过程的第7步）。
2、g(x)是对g*(x)的估计，g(x)>0。
3、h(x)是h*(x)的下界，即对所有的x均有：h(x)≤h*(x)
其中，g*(x)是从初始节点S0到节点x的最小代价；h*(x)是从节点x到目标节点的最小代价，若有多个目标节点，则为其中最小的一个。
四、基本要求
输入：九宫格的初始状态和目标状态
输出：重排的过程，即途径的状态以及所用步数！
四、实验程序
#include "iostream.h"
#include <time.h>
#include <stdio.h>
#include <dos.h>
#include <conio.h>
static int target[9];
//class definition
class eight_num
{
private:
int num[9];
int not_in_position_num;
int deapth;
int eva_function;
public:
eight_num* parent;
eight_num* leaf_next;
eight_num* leaf_pre;
eight_num(int init_num[9]);
eight_num(int num1,int num2,int num3,int num4,int num5,int num6,int num7,int num8,int num9)
{
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 (int i=0;i<9;i++)
num[i]=i;
}
void cul_para(void);
void get_numbers_to(int other_num[9]);
int get_nipn(void)
{return not_in_position_num;}
int get_deapth(void)
{return deapth;}
int get_evafun(void)
{return eva_function;}
void set_num(int other_num[9]);
void show(void);
eight_num& operator=(eight_num&);
eight_num& operator=(int other_num[9]);
int operator==(eight_num&);
int operator==(int other_num[9]);
};
//计算启发函数g(n)的值
void eight_num::cul_para(void)
{
int i;
int temp_nipn=0;
for (i=0;i<9;i++)
if (num[i]!=target[i])
temp_nipn++;
not_in_position_num=temp_nipn;
if (this->parent==NULL)
deapth=0;
else
deapth=this->parent->deapth+1;
eva_function=not_in_position_num+deapth;
}
//构造函数1
eight_num::eight_num(int init_num[9])
{
for (int i=0;i<9;i++)
num[i]=init_num[i];
}
//显示当前节点的状态
void eight_num::show()
{
cout<<num[0];
cout<<" ";
cout<<num[1];
cout<<" ";
cout<<num[2];
cout<<"\n";
cout<<num[3];
cout<<" ";
cout<<num[4];
cout<<" ";
cout<<num[5];
cout<<"\n";
cout<<num[6];
cout<<" ";
cout<<num[7];
cout<<" ";
cout<<num[8];
cout<<"\n";
}
//复制当前节点状态到一个另数组中
void eight_num::get_numbers_to(int other_num[9])
{
for (int i=0;i<9;i++)
other_num[i]=num[i];
}
//设置当前节点状态(欲设置的状态记录的other数组中)
void eight_num::set_num(int other_num[9])
{
for (int i=0;i<9;i++)
num[i]=other_num[i];
}
eight_num& eight_num::operator=(eight_num& another_8num)
{
for (int i=0;i<9;i++)
num[i]=another_8num.num[i];
not_in_position_num=another_8num.not_in_position_num;
deapth=another_8num.deapth+1;
eva_function=not_in_position_num+deapth;
return *this;
}
eight_num& eight_num::operator=(int other_num[9])
{
for (int i=0;i<9;i++)
num[i]=other_num[i];
return *this;
}
int eight_num::operator==(eight_num& another_8num)
{
int match=1;
for (int i=0;i<9;i++)
if(num[i]!=another_8num.num[i])
{
match=0;
break;
}
if (match==0)
return 0;
else
return 1;
}
int eight_num::operator==(int other_num[9])
{
int match=1;
for (int i=0;i<9;i++)
if(num[i]!=other_num[i])
{
match=0;
break;
}
if (match==0)
return 0;
else
return 1;
}
//class definition over
//空格向上移
int move_up(int num[9])
{
for (int i=0;i<9;i++)
if (num[i]==0)
break;
if (i<3)
return 0;
else
{
num[i]=num[i-3];
num[i-3]=0;
return 1;
}
}
//空格向下移
int move_down(int num[9])
{
for (int i=0;i<9;i++)
if (num[i]==0)
break;
if (i>5)
return 0;
else
{
num[i]=num[i+3];
num[i+3]=0;
return 1;
}
}
//空格向左移
int move_left(int num[9])
{
for (int i=0;i<9;i++)
if (num[i]==0)
break;
if (i==0||i==3||i==6)
return 0;
else
{
num[i]=num[i-1];
num[i-1]=0;
return 1;
}
}
//空格向右移
int move_right(int num[9])
{
for (int i=0;i<9;i++)
if (num[i]==0)
break;
if (i==2||i==5||i==8)
return 0;
else
{
num[i]=num[i+1];
num[i+1]=0;
return 1;
}
}
//判断可否解出
int icansolve(int num[9],int target[9])
{
int i,j;
int count_num,count_target;
for (i=0;i<9;i++)
for (j=0;j<i;j++)
{
if(num[j]<num[i]&&num[j]!=0)
count_num++;
if(target[j]<target[i]&&target[j]!=0)
count_target++;
}
if((count_num+count_target)%2 == 0)
return 1;
else
return 0;
}
//判断有无重复
int existed(int num[9],eight_num *where)
{
eight_num *p;
for(p=where;p!=NULL;p=p->parent)
if(*p==num)
return 1;
return 0;
}
//寻找估价函数最小的叶子节点
eight_num* find_OK_leaf(eight_num* start)
{
eight_num *p,*OK;
p=OK=start;
int min=start->get_evafun();
for(p=start;p!=NULL;p=p->leaf_next)
if(min>p->get_evafun())
{
OK=p;
min=p->get_evafun();
}
return OK;
}
//主函数开始
int main(void)
{
int memery_used=0,step=0;
int num[9];
int flag=0;//是否输入错误标志，1表示输入错误
int bingo=0;//是否查找成功标志，1表示成功
int i,j;
cout<<"Please input the initial matrix(0 for the blank):\n";
for (i=0;i<9;i++)
{
flag=0;
cin>>num[i];
for(j=0;j<i;j++)
if(num[i]==num[j])
flag=1;
if (num[i]<0||num[i]>8||flag==1)
{
i--;
cout<<"Illegle number!\tReinput!\n";
}
}
cout<<"Please input the target matrix(0 for the blank):\n";
for (i=0;i<9;i++)
{
flag=0;
cin>>target[i];
for(j=0;j<i;j++)
if(target[i]==target[j])
flag=1;
if (target[i]<0||target[i]>8||flag==1)
{
i--;
cout<<"Illegle number!\tReinput!\n";
}
}
eight_num S(num),Target(target);
S.parent=S.leaf_next=S.leaf_pre=NULL;
S.cul_para();
memery_used++;
cout<<"Now the initial numbers are:\n";
S.show();
cout<<"And the Target is:\n";
Target.show();
if(!icansolve(num,target))
{
cout<<"No one can solve it!\n";
cin>>i;
return 1;
}
eight_num *OK_leaf=&S,*leaf_start=&S,*new_8num,*p;
while(OK_leaf!=NULL&&bingo!=1)
{
OK_leaf=find_OK_leaf(leaf_start);
if(*OK_leaf==Target)
{
bingo=1;
break;
}
p=OK_leaf->leaf_pre;
OK_leaf->get_numbers_to(num);
if(move_up(num)&&!existed(num,OK_leaf))
{
new_8num=new eight_num;
new_8num->set_num(num);
new_8num->parent=OK_leaf;
new_8num->cul_para();
new_8num->leaf_pre=p;
if(p==NULL)
leaf_start=new_8num;
else
p->leaf_next=new_8num;
p=new_8num;
memery_used++;
}
OK_leaf->get_numbers_to(num);
if(move_down(num)&&!existed(num,OK_leaf))
{
new_8num=new eight_num;
new_8num->set_num(num);
new_8num->parent=OK_leaf;
new_8num->cul_para();
new_8num->leaf_pre=p;
if(p==NULL)
leaf_start=new_8num;
else
p->leaf_next=new_8num;
p=new_8num;
memery_used++;
}
OK_leaf->get_numbers_to(num);
if(move_left(num)&&!existed(num,OK_leaf))
{
new_8num=new eight_num;
new_8num->set_num(num);
new_8num->parent=OK_leaf;
new_8num->cul_para();
new_8num->leaf_pre=p;
if(p==NULL)
leaf_start=new_8num;
else
p->leaf_next=new_8num;
p=new_8num;
memery_used++;
}
OK_leaf->get_numbers_to(num);
if(move_right(num)&&!existed(num,OK_leaf))
{
new_8num=new eight_num;
new_8num->set_num(num);
new_8num->parent=OK_leaf;
new_8num->cul_para();
new_8num->leaf_pre=p;
if(p==NULL)
leaf_start=new_8num;
else
p->leaf_next=new_8num;
p=new_8num;
memery_used++;
}
p->leaf_next=OK_leaf->leaf_next;
if(OK_leaf->leaf_next!=NULL)
OK_leaf->leaf_next->leaf_pre=p;
OK_leaf->leaf_next=OK_leaf->leaf_pre=NULL;
}
if(bingo==1)
{
for (p=OK_leaf->parent;p!=NULL;p=p->parent)
{
cout<<" ^\n";
p->show();
step++;
}
cout<<"The final steps are:";
cout<<step;
cout<<"\n";
}
else
cout<<"Fail to find!";
return 0;
}
实验结果：
六、实验心得
本次实验使我发现了自己的许多不足之处，例如进行编写C++编程语言程序的能力不是非常强，考虑该问题时会大意与马虎，所以此次实验让我感觉很吃力，但是经过老师同学的提点，我相信自己以后会做的更好。