首页 > 代码库 > A star 搜索入门
A star 搜索入门
终于学习了传说中的A*搜索~...
先通俗的说一下A*搜索的原理，然后用代码实现~
A*搜索是在基于广搜的基础上的一种启发式搜索方式（我也不知道启发式是什么意思），可以大大降低搜索时间，找出相对正确的最优路径。
这里用到了特殊的存储结构---优先队列，可以优化将查找的复杂度从O(n)有化成O(logn);
1、首先我们从原点开始进行A*搜索，把原点入队列，然后标记为已访问
2.接收优先队列队列第一个元素并pop掉，判断第一个元素相邻的八个位置，如果其中有的位置是障碍物或者超出地图范围或者已经访问过，则排除，其他位置入栈，并用pre指针指向父节点
3.找出其中相对h+g最优的解（可用优先队列实现），重复2步骤，直到找到终点;
代码实现
#include <iostream>#include <cstdio>#include <queue>#include <cmath>using namespace std;int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};struct node{ bool visit; int x,y; double hx,gx;//核心 char ch; node *pre; node() { visit = 0; pre = NULL; } }map[51][51],start,end;bool judge(int x, int y){ if(x>=0 && x<=50 && y>=0 && y<=50) return true; else return false;}double Euclidean_dis(int sx,int sy,int ex,int ey){//欧几里德 double nn; nn=sqrt((sx-ex)*(sx-ex)+(sy-ey)*(sy-ey)); return nn;}double Chebyshev_dis(int sx,int sy,int ex,int ey){//切比雪夫 double nn; nn=max(abs(sx-ex),abs(sy-ey)); return nn;}double jiaquan_Manhattan(int sx,int sy,int ex,int ey){//加权曼哈顿 //better double nn,dx,dy; dx=abs(sx-ex); dy=abs(sy-ey); if(dx>dy) nn=10*dx+6*dy; else nn=6*dx+10*dy; return nn;}//重载运算符 bool operator<(node a, node b){ return a.gx + a.hx > b.gx + b.hx;}//寻找路径 void viewback(){ node *p; p = map[end.x][end.y].pre; while(p) { if(p->pre) { p->ch = ‘v‘; } p = p->pre; } return;}void Astar(){ priority_queue<node> q; q.push(start); int xx,yy; int i; while(!q.empty()) { node now = q.top(); q.pop(); if(now.x==end.x&&now.y == end.y) { break; } for(int i=0; i<4; i++) { xx = now.x + dir[i][0]; yy = now.y + dir[i][1]; if(!judge(xx, yy)||map[xx][yy].ch == ‘x‘ || map[xx][yy].visit == 1) { continue; } map[xx][yy].visit = 1; map[xx][yy].pre = &map[now.x][now.y]; map[xx][yy].hx = jiaquan_Manhattan(xx, yy, end.x, end.y); map[xx][yy].gx = now.gx + 1; q.push(map[xx][yy]); } } return ;}int main(){ freopen("t.txt", "r", stdin); int i,j,visi_num=0; for(i=0;i<50;i++){ for(j=0;j<50;j++){ cin>>map[i][j].ch; map[i][j].x=i; map[i][j].y=j; if(map[i][j].ch==‘s‘){ map[i][j].gx=0; map[i][j].visit=1; start=map[i][j]; } if(map[i][j].ch==‘e‘) end=map[i][j]; } getchar(); } cout<<"结果---------------------------------------------------"<<endl; Astar(); viewback(); for(i=0;i<50;i++){ for(j=0;j<50;j++){ visi_num+=map[i][j].visit; if(map[i][j].ch==‘v‘ || map[i][j].ch==‘e‘ || map[i][j].ch==‘s‘) printf("%c",map[i][j].ch); else if(map[i][j].visit) printf("%d",map[i][j].visit); else printf("%c",map[i][j].ch); } cout<<"\n"; } printf("\n遍历节点 %d 个\n",visi_num); return 0;}
这个代码写的很好，我从网上好不容易找到的~...
A star 搜索入门
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。