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;
}

迷宫问题-A*算法求最短路径

A*算法求解最短路径

求解主要公式 F=G+H

具体的算法

代码