原来粗略的考虑，h函数选各个数码离目标位置的最短距离的和，原则上是可行的，但启发性不大，举个简单例子：
{2,1,3,
8,0,4,
7,6,5}
和目标状态只差1和2的位置交换一下就对了，h函数给出的估计值只有2，实际上却差得太远，如果你小时候有玩过这样的‘数字拼盘’游戏，就会知道，像这样的是没有解的，至少那时候的感觉是这样，就算有解，也需要移很多次。
基于这样的h函数，感觉启发性不够，在海量搜索的时候效果不是很好，像有的CASE，搜到OPEN表+CLOSE表共好几万的结点了还在不停的搜。可见八数码问题有难有易，虽然9!只有三十多万，也比较难搜。
今天写的程序：
#include <iostream.h>
struct Snode
{
int key;
int map[9];
int g,f;
int last;
public:
Snode(){key=0;}
void TransformIn(const int *d);
void TransformOut(int *d);
};
void Snode::TransformIn(const int *d)
{
key=0;
for(int i=0;i<9;++i)
key=key*9+(map[i]=d[i]);
}
void Snode::TransformOut(int *d)
{
for(int i=0;i<9;++i)
{
d[i]=map[i];
}
}
int spath[9][9]=
{{0},
{0,1,2,1,2,3,2,3,4},
{1,0,1,2,1,2,3,2,3},
{2,1,0,3,2,1,4,3,2},
{3,2,1,2,1,0,3,2,1},
{4,3,2,3,2,1,2,1,0},
{3,2,3,2,1,2,1,0,1},
{2,3,4,1,2,3,0,1,2},
{1,2,3,0,1,2,1,2,3}
};
#define MAX_OPEN_LEN 50000
#define MAX_CLOSE_LEN 50000
Snode OPEN[MAX_OPEN_LEN];
int op=0;
Snode CLOSE[MAX_CLOSE_LEN];
int cp=0;
int hFunction(const Snode &node)
{
int h=0;
for(int i=0;i<9;++i)
{
h+=spath[node.map[i]][i];
}
return h;
}
inline void swapn(int &a,int &b)
{
int tmp=a;
a=b;
b=tmp;
}
int Astar(const int *d)
{
static int dp[4]={-3,-1,1,3};
//int data[9];
op=1;
cp=0;
OPEN[0].TransformIn(d);
OPEN[0].g=0;
OPEN[0].f=hFunction(OPEN[0]);
OPEN[0].last=-1;//root node
while(op>0)//OPEN Table not empty
{
int i,min,zero,pos,j;
for(min=0,i=1;i<op;++i)//Choose a best
{
if(OPEN[i].f<OPEN[min].f)
min=i;
}
if(OPEN[min].key==54682916)
{
CLOSE[cp++]=OPEN[min];
return 1;
}
//OPEN[min].TransformOut(data);
for(zero=0;zero<9;++zero)
{
if(OPEN[min].map[zero]==0)
break;
}
for(i=0;i<4;++i)
{
if((zero==3 || zero==6) && i==1)
continue;
if((zero==2 || zero==5) && i==2)
continue;
pos=zero+dp[i];
if(pos<0 || pos>8)
continue;
swapn(OPEN[min].map[zero],OPEN[min].map[pos]);
Snode child;
child.TransformIn(OPEN[min].map);
child.g=OPEN[min].g+1;
child.f=child.g+hFunction(child);
child.last=OPEN[min].key;
for(j=0;j<cp;++j)
{
if(CLOSE[j].key==child.key)
break;
}
if(j==cp)//got a new node
{
OPEN[op++]=child;
}
swapn(OPEN[min].map[zero],OPEN[min].map[pos]);
}
CLOSE[cp++]=OPEN[min];// Insert to CLOSE Table
ostream& operator<<(ostream& out,Snode &node);
//cout<<OPEN[min];
cout<<endl<<op<<" "<<cp<<endl;
OPEN[min]=OPEN[--op]; // Delete from OPEN Table
}
return 0;
}
ostream& operator<<(ostream& out,Snode &node)
{
int data[9];
node.TransformOut(data);
for(int i=0;i<3;++i)
{
for(int j=0;j<3;++j)
out<<data[i*3+j];
out<<endl;
}
out<<"g="<<node.g<<endl
<<"f="<<node.f<<endl<<endl;
return out;
}
void OutputSolution()
{
cout<<"Succeed!\n";
}
int main(void)
{
int map[9]={ 2, 8, 3, 1, 0, 4, 7, 6, 5 };//{1,3,4,2,8,6,5,7,0};//{6,4,7,8,5,0,3,2,1};//{1,2,3,4,5,6,7,8,0};//{2,8,3,1,0,4,7,6,5};//{1,3,4,0,6,2,8,7,5};
if(Astar(map))
OutputSolution();
else
cout<<"no solution!\n";
return 0;
}
现在想到的改进的地方就是把CLOSE表做成哈希表，因为当CLOSE表很大的时候花在它身上的查找会很费时，h函数还要改进。
另外今天找到一篇文章，讲如何判定‘八数码问题’是否有解的一个简单方法，非常巧妙，源处不能复制，无法转载。
判别方法是：
将八数码的一个结点表示成一个数组a[9]，空格用0表示，设函数p(x)定义为：x数所在位置前面的数比x小的数的个数，其中0空格不算在之内，那设目标状态为b[9]，那r=sigma(p(x)) sigma()表示取所有的x:1-8并求和，那对于初始状态a[9]，t=sigma(p(x))，如果r和t同为奇数或者同为偶数，那么该状态有解，否则无解。
具体证明我不写了，是考虑到四种移动方法对sigma(p(x))的影响，左移和右移是不会影响它的值的，更不会影响奇偶性，如果是上移或者下移就会影响：
上移，一次上移会使一个元素向前跳两个数字的位置，设这两个数字为a1,a2，不妨设a1<a2，移的这个数字设为a0，那无非只有以下三次情况：
1，a0<a1<a2，考虑它们三者的p(x)值，p(a0)不变，p(a1)++，p(a2)++，总体增加了2
2，a1<a0<a2，p(a0)--,p(a1)不变,p(a2)++，总体不变
3，a1<a2<a0，p(a0)-=2,p(a1),p(a2)不变，总体减小了2
综合起来的结论就是不会影响sigma(p(x))的奇偶性。
评论