A* 算法

A* 算法是求解最短路径的算法之一，其他的求解算法还有Dijkstra 算法、Bellman-ford 算法、SPFA 算法、Floyd算法等。

既然有了上面的那么多的算法，为什么还要设计A* 算法呢？

A* 算法较其他算法的不同就是它采用了启发式搜索的方式，一般算法采用的是直接搜索的方式。

相比与直接搜索方式启发式搜索肯定具备一定的优点，直接搜索方式是找到到达目的的所有路径，然后比较得出最短的路径。在搜索的过程中不做任何路径的处理。

而启发式搜索根据特定的启发函数，在搜索的过程中选择最优最优的路径，使得搜索的范围尽可能的小，这样就提高了搜索过程的效率。

A *算法基于 Dijkstra 算法和 Greed-Best-First-Search 算法

Dijkstra 算法

dilkstra 算法是比较常用的最短路径的求解算法。在该算法中维护着一个dis[]数组，表示愿节点到各个节点的最短距离。例如,假设源节点为0号节点，则dis[i] 解表示0号节点到 i 号节点的最短距离，还有一个open表和close 表。

其中open表中存放的是已经找到最短路径的节点，close 表中存放的是未找到最短路径的节点。初始时open表中只有源节点。

1、在close 表中找一个节点距离源节点最近的节点 k （即在close的所有节点中 dis[k] 的值最小）将 k 节点加入到open 表中。

2、更新close 表中的所有节点的dis[] 的值，如果通过k节点到达close中的节点的距离比原来的dis[]中的值小，就更新dis[]中的值，否则的话，不跟新。

3、重复1 、 2操作，直到close 表中的节点数为空为止。

上面就是Dijkstra算法的基本思想，Dijkstra算法只能求解没有负权边的图的最短路径，如果一个图的最短路径中存在负权边，则不能用Dijkstr算法求解，对于存在负权边的有向图的求解方法，可以用Bellman-ford 或 SPFA 算法求解

Greed-Best-First-Search算法

该算法是利用贪婪策略实现的一种算法，每次选择的下一个节点都是在当前节点所能到达的节点中距离终点最近的节点，

1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1假设这个是地图，求两点之间的最短距离最Greed-Best-First-Search 算法中，总是先计算四周的节点到终点的距离，哪个距离终点最近，就选择哪个节点，当然在没有障碍物的情况下，这种方法没有错误如果存在障碍物，则不一定能找到最短路径，例如下面的地图 2 表示障碍物 1 表示可以通行1 1 1 1 1 1 1 1 1 11 1 1 1 1 2 1 1 1 11 1 1 1 1 2 1 1 1 11 1 1 1 1 2 1 1 1 11 1 1 1 1 2 1 1 1 11 1 1 1 1 2 1 1 1 11 1 1 1 1 2 1 1 1 11 1 2 2 2 2 1 1 1 11 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1

Greed-Best-First-Search 计算到终点位置的最短距离公式这里采用了曼哈顿方法

//(x,y) 表示当前位置 （endx,endy）表示终点位置res = abs(x - ensx) + abs(y - endy);

启发函数

启发函数是结合上面的两种算法，这里先给出启发函数的形式

F(N) = G(N) + H(N);

这个函数的形式并不复杂，

G(N) 表示采用的Dijkstra 算法计算出的已经经过的路径的长度，

H(N) 表示采用 Greed-Best-First-Search 算法计算出的当前位置距离终点的最短距离

这两个数值的和就是起点到终点的最短距离，所以在选择路径的时候，时刻选择F(N)最小的位置

A*算法的代码实现

直接在代码中注释解释

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;#define TRAVERSE 2         //障碍物#define TRANSITABLE 1      //可通行的#define FOOT 3             //已经过的#define PATH 0             //路径//===================================================================================================================struct Node{
       Node(int x = 0,int y = 0):_x(x),_y(y),_prev(NULL){
   }    int _x;			//节点所在的行    int _y;			//节点所在的列    int _data;		//当前位置的状态 （可通行、障碍物、已经过）    int _mgn;    //dijkstra 计算出的G(N)值    int _mfn;    //F(n) = G(n) + H(n)    Node *_prev;   //前驱节点};//=================================================================================================================class compare{
   public:	//函数对象用于优先级队列中将f(n)最小的值放在堆顶    bool operator()(const Node& left,const Node &right)    {
           return left._mfn > right._mfn;    }};//=====================================================================================================================class CMap{
   public:	//获取地图    vector
       
        
          > &getMap() { return _map;} //设置地图 void setMap();private: vector
         
          
            > _map;};void CMap::setMap(){ cout << "输入地图的行数和列数:"; int row,col; cin >> row >> col; for(int i = 0; i < row; ++i) { vector
           
             tmp; for(int j = 0; j < col; ++j) { //根据键盘输入初始化地图 Node node; int data; cin >> data; node._x = i; node._y = j; node._data = data; tmp.push_back(node); } _map.push_back(tmp); tmp.clear(); }};//===================================================================================================================class A{ public: A() { //每个位置都有四个移动过方向 H V 表示节点的移动方向 H[0] = 1; V[0] = 0; H[1] = 0; V[1] = 1; H[2] = -1; V[2] = 0; H[3] = 0; V[3] = -1; } //获取H(n)的值 int getHn(int x,int y,int endx,int endy); //查找路径 void findPath(int startx,int starty,int endx,int endy); //打印路径 void display(int x,int y); //设置地图 void setMap() { _map.setMap();} private: CMap _map; //存放已遍历过节点 能够直接到达的节点 例如当前节点为 （1，1） //（1，1）能直接到达的节点为 (1,0)、(1,2)、(0,1)、(2,1)四个节点 priority_queue
            
             
              ,compare> _prioque; //优先级队列 int H[4]; int V[4]; //H 与 V用来存储四个方向};void A::display(int x,int y){ Node *node = &_map.getMap()[x][y]; while(node != NULL) { //将到达终点的路径改为PATH node->_data = PATH; node = node->_prev; } int row = _map.getMap().size(); for(int i = 0; i < row; i++) { int col = _map.getMap()[i].size(); for(int j = 0; j < col; j++) { cout << _map.getMap()[i][j]._data << " "; } cout << endl; }}//int A::getHn(int x,int y,int endx,int endy){ return fabs(x-endx) + fabs(y-endy);}void A::findPath(int startx,int starty,int endx,int endy){ if(startx == endx && starty == endy) { return ; } //将起点放入优先级队列中 _map.getMap()[startx][starty]._mgn = 0; _map.getMap()[startx][starty]._data = FOOT; _map.getMap()[startx][starty]._mfn = getHn(startx,starty,endx,endy); _prioque.push(_map.getMap()[startx][starty]); //如果队列不为空，取出队列的第一个元素，即F(N)最小的那个位置 while(!_prioque.empty()) { int x = _prioque.top()._x; int y = _prioque.top()._y; //如果找到最短路径 if(x == endx && y == endy) { //打印路径 display(x,y); return ; } _prioque.pop(); for(int i = 0; i < 4; i++) { //判断当前节点的四周是否都在地图中 if(x + H[i] >= 0 && x + H[i] < _map.getMap().size() && y + V[i] >= 0 && y + V[i] < _map.getMap()[x].size()) { //判断当前节点的下一个节点是否是可通行的 if(_map.getMap()[x+H[i]][y+V[i]]._data == TRANSITABLE) { //将下一个节点标记为FOOT _map.getMap()[x+H[i]][y+V[i]]._data = FOOT; //记录下一个节点的前驱节点 _map.getMap()[x+H[i]][y+V[i]]._prev = &_map.getMap()[x][y]; //计算下一个节点的G(N) _map.getMap()[x+H[i]][y+V[i]]._mgn = _map.getMap()[x][y]._mgn + 1; //计算下一个节点的F(N) _map.getMap()[x+H[i]][y+V[i]]._mfn = _map.getMap()[x+H[i]][y+V[i]]._mgn + getHn(x+H[i],y+V[i],endx,endy); //将下一个节点放入优先级队列 _prioque.push(_map.getMap()[x+H[i]][y+V[i]]); } } } } //如果队列为空，则输出无路径 cout << " 无路径 " << endl;}int main(){ A a; a.setMap(); int startx,starty,endx,endy; cout << "输入起始位置与终止位置:"; cin >> startx >> starty >> endx >> endy; a.findPath(startx,starty,endx,endy); return 0;}

测试：

1 表示可通行，

2 表示障碍物，

3 表示搜索的位置，

0表示最短路径，

转载地址：http://rtnwi.baihongyu.com/

你可能感兴趣的文章

glm 中数据类型与原始数据(c++ 数组)之间的转换