九宫格的启发式搜索.doc

九宫格的启发式搜索
班级：计算机一班
姓名：覃荣锦
学号：1240023
目录
一、 7,8,0};
int k=rand()%10+30;
int j,l,temp;
while(k>=0)
{
for(l=0;l<9;l++)
if(a[l]==0) break;
j=rand()%4;
k--;
if(check[l][j]!=9)
{
temp=a[check[l][j]];
a[check[l][j]]=a[l];
a[l]=temp;
}
}
for(j=0;j<9;j++)
data[j]=a[j];
}
void Init(int data[9])
{
for(int i=0;i<9;i++)
open[opentop].data[i]=data[i];
open[opentop].parent=-1;
open[opentop].value=GetValue(open[opentop].data);
opentop++;
}
判断目标节点算法如下：
bool Checkwin(int data[9])
{
for(int i=0;i<8;i++)
if(data[i]!=i+1) return 0;
return 1;
}
拓展节点
拓展节点的思路为：
对于当前节点，利用上面介绍的辅助矩阵求出其接下来移动后可能生成的2~4个局面。
判断每个局面是否合法。方法是检查open表和closed表，判断该局面是否出现过，若出现过，则不合法，反之合法。
得到新局面后，如果是局部择优，则将局面按从大到小排序，然后插入open表尾部（或从小到大排序，插入open表头部）；如果是全局择优。则先放入open表，然后将open表从大到小排序。
算法如下：
void QuanjuMakeMove(int data[9],int parentvalue,int parent)//全局择优的拓展
{
int i=0,j,k;
while(data[i]!=0) i++;
for(j=0;j<4&&check[i][j]!=9;j++)
{
for(k=0;k<9;k++)
{
if(k==i) open[opentop].data[k]=data[check[i][j]];
else if(k==check[i][j]) open[opentop].data[k]=data[i];
else open[opentop].data[k]=data[k];
}
// if(状态合法) opentop++;open[..].value=..
if(!IsExist(open[opentop].data))
{
open[opentop].value=parentvalue+GetValue(open[opentop].data);
open[opentop].parent=parent;
opentop++;
}
}
//排序整个open表从小到大此处用选择排序法
Data temp;
if(opentop==0) return;
for(i=0;i<opentop-1;i++)
{
k=i;//设第i个是最大的
for(j=i+1;j<opentop;j++)//选择出第i个之后的节点中最大的
if(open[j].value>open[k].value) k=j;
//与第i个交换
temp=open[k];
open[k]=open[i];
open[i]=temp;
}
}
void JubuMakeMove(int data[9],int parentvalue,int parent)//局部择优的拓展
{
int i=0,j,k,m;
m=opentop;
while(data[i]!=0) i++;
for(j=0;j<4&&check[i][j]!=9;j++)
{
for(k=0;k<9;k++)
{
if(k==i) open[opentop].data[k]=data[check[i][j]];
else if(k==check[i][j]) open[opentop].data[k]=data[i];
else open[opentop].data[k]=data[