A*算法解决八数码问题
程序员文章站
2023-12-24 15:13:33
...
#include <iostream>
#include <stdio.h>
#include <queue>
#include <vector>
#include <stack>
using namespace std;
struct board
{
pair<int,int> number[9];
int f;
int g;
int h;
board* father;
};
struct cmp
{
bool operator()(board a,board b)
{
if(a.g==b.g)
return a.h>b.h;
else
return a.g>b.g;
}
};
board start,over;
pair<int,int> direct[4];
priority_queue<board, vector<board>, cmp> open,close;
vector<board> visited;
int abs(int a,int b)
{
if(a>b)
return a-b;
else
return b-a;
}
int geth(board a,int flag)
{
int ret=0;
switch (flag)
{
case 0:
{
ret=0;
return ret;
}
case 1:
{
for(int i=1;i<9;i++)
if((a.number[i].first!=over.number[i].first)||(a.number[i].second!=over.number[i].second))
ret++;
return ret;
}
case 2:
{
for(int i=1;i<9;i++)
ret=ret+abs(a.number[i].first,over.number[i].first)+abs(a.number[i].second,over.number[i].second);
return ret;
}
}
}
int compare(board a,board b)
{
int ret=1;
for(int i=0;i<9;i++)
if((a.number[i].first!=b.number[i].first)||(a.number[i].second!=b.number[i].second))
{
ret=0;
break;
}
return ret;
}
void writeboard(board a)
{
int out[3][3];
for(int j=0;j<9;j++)
out[a.number[j].first][a.number[j].second]=j;
for(int j=0;j<3;j++)
{
for(int k=0;k<3;k++)
cout<<out[j][k];
cout<<endl;
}
cout<<"g:"<<a.g<<" "<<"h:"<<a.h<<endl;
cout<<endl;
}
void writepath(board a)
{
if(a.father!=NULL)
{
board temp=*(a.father);
writepath(temp);
writeboard(a);
}
else
writeboard(a);
return;
}
void input()
{
freopen("in.txt","r",stdin);
for(int i=0;i<9;i++)
{
int n;
cin>>n;
start.number[n].first=i/3;
start.number[n].second=i%3;
}
for(int i=0;i<9;i++)
{
int n;
cin>>n;
over.number[n].first=i/3;
over.number[n].second=i%3;
}
}
void init(int flag)
{
direct[0]=make_pair(0,-1);
direct[1]=make_pair(-1,0);
direct[2]=make_pair(0,1);
direct[3]=make_pair(1,0);
start.f=0;
start.g=0;
start.h=geth(start,flag);
start.father=NULL;
while(!open.empty())
open.pop();
while(!close.empty())
close.pop();
visited.clear();
}
void AStar(int flag)
{
int getans=0;
int extend=0,born=0;
open.push(start);
visited.push_back(start);
while(!open.empty())
{
board bes=open.top();
open.pop();
extend++;
close.push(bes);
visited.push_back(bes);
//cout<<"out:"<<endl;
//writeboard(bes);
for(int i=0;i<4;i++)
{
board suc=bes;
if((bes.number[0].first+direct[i].first>=0)&&(bes.number[0].first+direct[i].first<=2)
&&(bes.number[0].second+direct[i].second>=0)&&(bes.number[0].second+direct[i].second<=2))
{
suc.number[0].first=bes.number[0].first+direct[i].first;
suc.number[0].second=bes.number[0].second+direct[i].second;
for(int j=1;j<9;j++)
if((suc.number[j].first==bes.number[0].first+direct[i].first)
&&(suc.number[j].second==bes.number[0].second+direct[i].second))
{
suc.number[j].first=bes.number[0].first;
suc.number[j].second=bes.number[0].second;
}
}
if(compare(suc,over))
{
getans=1;
//writepath(suc);
break;
}
suc.h=geth(suc,flag);
suc.g=bes.g+1;
suc.f=suc.g+suc.h;
suc.father=&bes;
int used=0;
for(int i=0;i<visited.size();i++)
{
board temp=visited[i];
if(compare(temp,suc))
used=1;
}
if(!used)
{
open.push(suc);
visited.push_back(suc);
born++;
//cout<<"in:"<<endl;
//writeboard(suc);
}
}
if(getans==1)
break;
}
if(getans)
{
cout<<"生成节点数:"<<born<<endl;
cout<<"拓展节点数:"<<extend<<endl;
}
else
cout<<"No solution!"<<endl;
}
int main()
{
input();
for(int t=0;t<3;t++)
{
init(t);
AStar(t);
cout<<endl;
}
return 0;
}