本文对八数码问题 启发式搜索 （C++）做了一点点修改
//fn=gn+hn #include<iostream>
#include<queue>
#include<stack> using namespace std; #define num 9 struct node
{
int state[];//当前状态
struct node* parent;//父节点
int value;//值
int depth;//在树中的深度
friend bool operator < (node A, node B) //按照value值小的方案构造优先级队列
{
return A.value > B.value;
}
}; priority_queue<node> openTable; //open表
queue<node> closeTable; //close表
stack<node> Path; //最终路径 void init(node& s,node& g)
{//初始化
s.parent=NULL;
s.depth=;
s.value=;
g.parent=NULL;
g.depth=;
g.value=; cout<<"please input the init status"<<endl;
for(int i=;i<num;i++)
{
cin>>s.state[i];
} cout<<"please input the target status"<<endl;
for(int i=;i<num;i++)
{
cin>>g.state[i];
} } bool isreachable(node s,node g)
{//判断目标是否可达。若2个状态的逆序奇偶性相同则可达，不相同则不可达。
int count1=;
int count2=;
for(int i=;i<=num-;i++)
{
for(int j=i+;j<num;j++)
{
if(s.state[i]>s.state[j]&&s.state[i]*s.state[j]!=)
{
count1++;
}
}
} for(int i=;i<=num-;i++)
{
for(int j=i+;j<num;j++)
{
if(g.state[i]>g.state[j]&&g.state[i]*g.state[j]!=)
{
count2++;
}
}
} if(count1%!=count2%)
{
return false;
}
return true; } int value(node a,node g)
{//hn
int count=;
for(int i=;i<num;i++)
{
if(a.state[i]==)
{
continue;
}
else if(a.state[i]!=g.state[i])
{
for(int j=;j<num;j++)
{
if(a.state[i]==g.state[j])
{
count+=abs(i/-j/)+abs(i%-j%);
}
}
}
}
return count+a.depth;
} bool isequal(node a,node g)
{//当前节点是否是目标
for(int i=;i<num;i++)
{
if(a.state[i]!=g.state[i])
{
return false;
}
}
return true;
} bool createNode(node& a,node g)
{//产生新节点，加入open表
bool flag=true;
/* 计算原状态下,空格所在的行列数，从而判断空格可以往哪个方向移动 */
int blank;//定义空格下标
for(blank=;blank<num;blank++)
{
if(a.state[blank]==)
{
break;
}
}
if(blank==num)return false;
int x=blank/,y=blank%;//获取空格所在行列编号
/*找到S扩展的子节点，加入open表中*/
for(int d=;d<;d++)
{
int newx=x,newy=y;//新空白格坐标
node tempnode;//临时节点，子节点 /*移动空格*/
switch (d)
{
case ://向上
newx--;
if(newx<)continue;
break;
case ://向左
newy--;
if(newy<)continue;
break;
case ://向下
newx++;
if(newx>)continue;
break;
case ://向右
newy++;
if(newy>)continue;
break; default:
break;
} /*交换新旧空白格的内容*/
int newblank=newx*+newy;//新空格下标 if (newx >= && newx < && newy >= && newy < )
{
tempnode=a;
tempnode.state[blank]=tempnode.state[newblank];
tempnode.state[newblank]=;
if(a.parent!=NULL&&(*a.parent).state[newblank]==)
{//如果新节点和爷爷节点一样，舍弃该节点
continue;
} /*把子节点都加入open表中*/
tempnode.parent=&a;
tempnode.value=value(tempnode,g);
tempnode.depth=a.depth+;
openTable.push(tempnode);
}
}
return flag;
} bool findpath(node s,node g)
{//s->g
bool flag=true;
/*find path*/
openTable.push(s);
while(true)
{
closeTable.push(openTable.top());
openTable.pop();
if(!isequal(closeTable.back(),g))
{
flag=createNode(closeTable.back(),g);
}
else
{
break;
} }
/*make path*/
node tempnode;
tempnode=closeTable.back();
while(tempnode.parent!=NULL)
{
Path.push(tempnode);
tempnode=*(tempnode.parent);
}
Path.push(tempnode);
return flag;
} void printpath()
{//print path s -> g
cout<<"move "<<Path.size()-<<" step"<<endl;
while(Path.size()!=)
{
for(int i=;i<num;i++)
{
cout<<Path.top().state[i]<<" ";
if((i+)%==)cout<<endl;
}
Path.pop();
cout<<endl;
}
} int main()
{
node s,g;
init(s,g);
if(!isreachable(s,g))
{
cout<<"cannot reach"<<endl;
system("pause");
return ;
}
else if (!findpath(s,g))
{
cout<<"findpath error"<<endl;
system("pause");
return ;
}
else
{
printpath();
cout<<"done"<<endl;
}
system("pause");
return ;
}