//启发规则:评价函数是f(n)=d(n)+w(n)
//其中d(n)是结点深度,w(n)是牌不在目标的个数
//目标棋局定为:1 2 3
// 8 4
// 7 6 5
//本程序中以0作为空格结点的值
#include<iostream>
#include<vector>
using namespace std;
struct point
{
int a[3][3];
int w;//不在位将牌数
int d;//接点深度
int f;//评价函数
};
vector<point*> close;//已扩展节点
vector<point*> open;//待扩展节点
int aim[3][3]={1,2,3,8,0,4,7,6,5};//目标棋局
int Cout(point *&s)//计算牌不在目标的个数
{
s->w=0;
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
if(s->a[i][j]!=aim[i][j])
s->w++;
}
}
return s->w;
}
bool init(point * &s)//初始化接点
{
s=(point *)malloc(sizeof(point));
if(!s)
return false;
s->d=1;
s->w=0;
s->a[0][0]=2;
s->a[0][1]=8;
s->a[0][2]=3;
s->a[1][0]=1;
s->a[1][1]=0;
s->a[1][2]=4;
s->a[2][0]=7;
s->a[2][1]=6;
s->a[2][2]=5;
Cout(s);
s->f=s->d+s->w;
return true;
}
int sort()//将open表中接点按评价函数排序,返回评价函数值最小的节点在队列中的位置
{
if(open.size()!=0)
{
int min=0;
int temp=open.at(0)->f;
for(int i=0;i<open.size();i++)
{
if(open[i]->f<temp)
{
temp=open[i]->f;
min=i;
}
}
return min;
}
return -1;
}
bool compare(point *s)//比较可扩展接点与colse表中接点是否重复,true:不重复 false:重复
{
vector<point*>::iterator it;
for(it=close.begin();
it!=close.end();it++)
{
int n=0;
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
if(s->a[i][j]!=(*it)->a[i][j])
{
n++;
break;
}
}
}
if(n==0)
return false;
}
return true;
}
void expand(point *s)//扩展接点
{
int a,b;
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
if(s->a[i][j]==0)
{
a=i;
b=j;
break;
}
}
}//确定空格位置
for(i=0;i<4;i++)//四个方向探测--0:上 1:下 2:左 3:右
{ int n=0;
point *p=(point *)malloc (sizeof(point));
for(int c=0;c<3;c++)
{
for(int z=0;z<3;z++)
p->a[c][z]=s->a[c][z];
}
if(i==0&&b-1>=0)//左可行,交换
{
int temp=p->a[a][b-1];
p->a[a][b-1]=p->a[a][b];
p->a[a][b]=temp;
n++;
}
else if(i==1&&a+1<=3)//下可行,交换
{
int temp=p->a[a+1][b];
p->a[a+1][b]=p->a[a][b];
p->a[a][b]=temp;
n++;
}
else if(i==2&&a-1>=0)//上可行,交换
{
int temp=p->a[a-1][b];
p->a[a-1][b]=p->a[a][b];
p->a[a][b]=temp;
n++;
}
else if(i==3&&b+1<=3)//右可行,交换
{
int temp=p->a[a][b+1];
p->a[a][b+1]=p->a[a][b];
p->a[a][b]=temp;
n++;
}
if(n==0)//此方向不可行,试探下一个方向
continue;
p->d=s->d+1;
p->w=0;
Cout(p);
p->f=p->d+p->w;
if(compare(p))//与已扩展节点相比无重复则加入open表
open.insert(open.begin(),p);
}
}
void print()//输出搜索路径
{
vector<point*>::iterator it;
for(it=close.begin();it!=close.end();it++)
{
for(int i=0;i<3;i++)
{
cout<<endl;
cout<<(*it)->a[i][0]<<" "<<(*it)->a[i][1]<<" "<<(*it)->a[i][2]<<endl;
}
if(it!=close.end()-1)
{
cout<<" |"<<endl;
cout<<" |"<<endl;
cout<<" \\/"<<endl;
}
}
}
void Num()
{
point *s; init(s);
open.push_back(s);
while(open.size()!=0)
{
int min=sort();
point *ex=open.at(min);
if(min!=-1)
{
if(close.size()!=0)//若open表中评价函数最小值节点的层数小于close表中层数,说明该路径非最优,
{ //退回,删除close表中与最小值节点同层和下层节点
vector<point*>::iterator it=close.end()-1;
while(open.at(min)->d<=(*it)->d)
{
close.pop_back();
}
}
close.push_back(open.at(min));//最小值节点入close
open.erase(open.begin()+min);//同时删除open表中相应节点
if(Cout(ex)==0)//若不在位节点数为0,则打印输出最优路径
{
print();
return;
} expand(ex);//若非目标棋局,则扩展节点
}
}
}
int main()
{
Num();
return 0;
}