A*算法求解最短路径

-个人觉得是BFS的优化版本，在效率和空间上要比BFS高效很多，尤其是点很多的时候
参考链接https://blog.csdn.net/qq_36946274/article/details/81982691

• 求解主要公式 F=G+H

  其中，F：为当前点总的移动耗费；
     G：为当前点到起点的移动耗费；
     H：为当前点到目标点的移动耗费;(此处选择的是曼哈顿距离）
  通过不断选择出F最小的格子，并加入其相邻的格子，直到当前的格子为目标点。

• 具体的算法

  1、把起点加入到open list（开放列表）
  2、重复以下的过程：
  a.遍历open list，查找F值最小的节点，把它作为当前要处理的节点。
  b.把这个点移动到close list（关闭列表）。
  c.对当前的方格的4个相邻方格的每一个方格：
  .如果它是障碍物或者越界或者它在close list中，忽略它，否则做以下操作：
  .如果她不在open list中，把它加入到open list，并且把当前格子设置为它的父亲，记录该方格的F,G,H
  .如果它已经在open list中，检查这条路径（即经由当前方格到达它这里）G值是否更小。如果是，则把它的父亲设置为当前方格，并重新计算它的G和F值。open list按值排序，取F最小的放在最前面
  d.停止的条件：
  .把终点加入到了open list当中，此时的路径已经找到了，或者
  .查找终点失败，并且open list是空的，此时没有路径
  3、保存路径。从终点开始，每个方格沿着父节点移动至起点，这就是你的路径。

• 代码

  #include<iostream>
  #include<vector>
  #include<algorithm>
  using namespace std;
  //创建节点
  struct Grid
  {
     int x, y;
     Grid() : x(0), y(0) {}
  
     Grid(int x, int y) {
         this->x = x;
         this->y = y;
     }
  
     void setValue(int x, int y) {
         this->x = x;
         this->y = y;
     }
  };
  class Node {
  public:
     Node() : status(-1), x(-1), y(-1), fCost(INT32_MAX), gCost(0), parent(nullptr) {}
  
     void setValue(Grid a, int g_cost, int h_cost, Node* b) {
         x = a.x;
         y = a.y;
         fCost = g_cost + h_cost;
         gCost = g_cost;
  
         parent = b;
     }
  
     int status;  // -1 初始状态， 0 加入openlist 1 加入closelist
     int x, y;
     int fCost, gCost;
  
     Node* parent;
  
     static bool compare(const Node* a, const Node* b) { return a->fCost > b->fCost; }
  };
  //曼哈顿距离
  int getHeu(const Grid &start, const Grid &target)
  {
     return (int)(abs(start.x - target.x) + abs(start.y - target.y));
  }
  //是否越界
  bool isOutBound(Grid g, int width, int height)
  {
     return (g.x >= width || g.y >= height || g.x < 0 || g.y < 0);
  }
  //获取关闭列表索引值
  int getIndex(Grid g, int width)
  {
     return g.x + g.y*width;
  }
  //右  上   左    下
  int delta_xy[] = { 1, 0, 0,1,-1,0, 0,-1 };
  vector<Grid> getPath(vector<vector<int>> migong)
  {
     vector<Grid> paths;
     int height = migong.size();
     int width = migong[0].size();
     std::vector<Node*> open_list;//开放列表
     std::vector<Node> visit_list(width * height);//关闭列表
     Node* terminate_ptr = nullptr;
     Grid start(0, 0), target(width - 1, height - 1);
     Node* node_ptr = &visit_list[getIndex(start, width)];
     node_ptr->setValue(start, 0, getHeu(start, target), nullptr);
     open_list.push_back(node_ptr);
     Grid temp_grid(0, 0);
     while (!open_list.empty()) {
         node_ptr = open_list.front();
         std::pop_heap(open_list.begin(), open_list.end(), Node::compare);//将最小的元素放置到尾部弹出
         open_list.pop_back();
                 //找到目标节点
         if (node_ptr->x == target.x && node_ptr->y == target.y)
         {
             terminate_ptr = node_ptr;
             break;
         }
         for (int i = 0; i < 4; i++) 
         {
             // 计算下个点
             temp_grid.setValue(node_ptr->x + delta_xy[i * 2 + 0], node_ptr->y + delta_xy[i * 2 + 1]);
             if (isOutBound(temp_grid, width, height))
                 continue;
             Node* temp_node_ptr = &visit_list[getIndex(temp_grid, width)];
             // 非法越界，已经在closelist，有障碍物
             // 有可能机器人起点在沿边区域范围内的
             if (1 == temp_node_ptr->status || 1 == migong[temp_grid.y][temp_grid.x]) {
                 continue;
             }
             int base_cost = 10;
  
             // 计算新的代价值
             int new_g = node_ptr->gCost + base_cost;
             int new_h = getHeu(temp_grid, target);
             // 有理更小代价值，则更新
             if (temp_node_ptr->fCost > new_g + new_h) {
                 temp_node_ptr->setValue(temp_grid, new_g + new_h, new_h, node_ptr);
             }
                         //加入到开放列表
             if (-1 == temp_node_ptr->status) {
                 temp_node_ptr->status = 0;
                 open_list.push_back(temp_node_ptr);
                 std::push_heap(open_list.begin(), open_list.end(), Node::compare);
             }
         }
  
         node_ptr->status = 1;  // closed加入到关闭列表
     }
     if (terminate_ptr != nullptr) {
         while (terminate_ptr) {
             Grid tmp(terminate_ptr->x,terminate_ptr->y);
             paths.emplace_back(tmp);
             terminate_ptr = terminate_ptr->parent;
         }
         std::reverse(paths.begin(), paths.end());
     }
     return paths;
  }
  int main()
  {
     int N, M;
     while (cin >> N >> M)
     {
         vector<Grid> path;
         vector<vector<int>> migong(N, vector<int>(M, 0));
         for (int i = 0; i < N; i++)
         {
             for (int j = 0; j < M; j++)
             {
                 cin >> migong[i][j];
             }
         }
         path = getPath(migong);
         for (auto g : path)
         {
             cout << "(" << g.y << "," << g.x << ")" << endl;
         }
     }
     return 0;
  }