本文主要是介绍Astar算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这里主要介绍A*算法的实现：八数码问题
题目参见：HDU 1043 ，POJ 1077 Eight
#include<stdio.h>
#include<queue>
#include<string>
#include<iostream>
#include<algorithm>using namespace std;
const int MAXN=1000000;
int fac[]={1,1,2,6,24,120,720,5040,40320,362880};//康拖展开判重
// 0!1!2!3! 4! 5! 6! 7! 8! 9!bool vis[MAXN];//标记
string path;//记录最终的路径
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};//方向向量
char indexs[5]="udlr";//正向搜索
struct Node
{int data[9];int f,g,h;int loc;//“0”的位置,把“x"当0int status;//康拖展开的hash值string path;//路径bool operator==(const Node &t){return status==t.status;}bool operator<(const Node &t)const{return f>t.f;}
}start,goal;//起始和终止点int Cantor(int s[])//康拖展开求该序列的hash值
{int sum=0;for(int i=0;i<9;i++){int num=0;for(int j=i+1;j<9;j++)if(s[j]<s[i])num++;sum+=(num*fac[9-i-1]);}return sum+1;
}
int ABS(int x){return x<0?(-x):x;}
int Distance(Node suc, Node goal, int i) {//计算方格的错位距离 int h1,h2; //h1表示suc中i所处位置，h2表示goal中i所处的位置for(int k = 0; k < 9; k++) { if(suc.data[k] == i)h1 = k; if(goal.data[k] == i)h2 = k; } return ABS(h1/3 - h2/3) + ABS(h1%3 - h2%3);
}
int Fvalue(Node suc, Node goal, float speed) {//计算 f 值 int h = 0; for(int i = 1; i <= 8; i++) h = h + Distance(suc, goal, i); return h*speed + suc.g; //f = h + g（speed 值增加时搜索过程以找到目标为优先因此可能 不会返回最优解）
} bool Astar()
{memset(vis,false,sizeof(vis));Node cur,next;priority_queue<Node> q;q.push(start);while(!q.empty()){cur=q.top();q.pop();if(cur==goal){path=cur.path;return true;}int x=cur.loc/3;int y=cur.loc%3;for(int i=0;i<4;i++){int tx=x+dir[i][0];int ty=y+dir[i][1];if(tx<0||tx>2||ty<0||ty>2)continue;next=cur;next.loc=tx*3+ty;next.data[cur.loc]=next.data[next.loc];next.data[next.loc]=0;next.status=Cantor(next.data);if(!vis[next.status]){vis[next.status]=true;next.path=next.path+indexs[i];if(next==goal){path=next.path;return true;}next.g++;//g值next.f=Fvalue(next,goal,1);//f值q.push(next);}}}return false;
}
int main()
{freopen("C:\\in.txt","r",stdin);char ch;//目的节点初始化startfor(int i=0;i<8;i++)goal.data[i]=i+1;goal.data[8]=0;goal.status=46234;//123456780对应的康拖展开的hash值//endwhile(cin>>ch){//起始节点初始化startif(ch=='x') {start.data[0]=0;start.loc=0;}else start.data[0]=ch-'0';for(int i=1;i<9;i++){cin>>ch;if(ch=='x'){start.data[i]=0;start.loc=i;}else start.data[i]=ch-'0';}start.status=Cantor(start.data);//康拖hash值start.g=0;start.f=Fvalue(start,goal,1);//计算f值//endif(Astar()){cout<<path<<endl;}else cout<<"unsolvable"<<endl;}return 0;
}这篇关于Astar算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
