A-star

KO | EN

gitlite — search

#hacktoberfest #react #ai #typescript #go #golang #rust #deep-learning #macos #windows #kubernetes #vue #mcp #ios

(★ 10)

Implementation of A* in Matlab and Python

A-star Latest Version Download

Download Latest Version (.zip)

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# A*算法

> A*算法最初发表于1968年《A Formal Basis for the Heuristic Determination of Minimum Cost Paths》，由Stanford研究院的Peter Hart, Nils Nilsson以及Bertram Raphael发表。它可以被认为是Dijkstra算法的扩展：在 Dijkstra 的基础上加入了启发函数

$$F(n) = G(n) +H(n)$$

F(n)是节点n的综合距离。当我们选择下一个要遍历的节点时，我们总会选取综合优距离最小的节点。  
G(n)是节点n到源点的距离。  
H(n)是节点n到终点的预估距离，这也就是A*算法的**启发函数**。

### 启发函数
  - 如果H(n)始终小于等于节点n到终点的距离，则A*算法**保证一定能够找到最短路径**。但是当H(n)的值越小，算法将遍历越多的节点，也就导致**算法越慢**。  
  - 在极端情况下，当启发函数H(n)始终为0，则将由G(n)决定节点的优先级，此时算法就退化成了`Dijkstra算法`。  
  - 如果H(n)完全等于节点n到终点的距离，则A*算法将**找到最佳路径，并且速度很快**。可惜的是，并非所有场景下都能做到这一点。因为在没有达到终点之前，我们很难确切算出距离终点还有多远。  
  - 如果H(n)的值比节点n到终点的距离要大，则A*算法**不能保证找到最短路径，不过此时会很快**。  
  - 在另外一个极端情况下，如果H(n)相较于G(n)大很多，则此时只有H(n)产生效果，这也就变成了**最佳优先搜索**。

由上面这些信息我们可以知道，通过**调节启发函数**我们可以控制算法的速度和精确度。因为在一些情况，我们可能未必需要最短路径，而是希望能够尽快找到一个路径即可。这也是A*算法比较灵活的地方。

## 1. A*算法的基本步骤

### 解释1 （参考：[路径规划之 A* 算法](https://paul.pub/a-star-algorithm/)）

* 初始化open_set和close_set；
* 将起点加入open_set中，并设置优先级为0（优先级最高）；
* 如果open_set不为空，则从open_set中选取优先级最高的节点n：
    * 如果节点n为终点，则：
        * 从终点开始逐步追踪parent节点，一直达到起点；
        * 返回找到的结果路径，算法结束；
    * 如果节点n不是终点，则：
        * 将节点n从open_set中删除，并加入close_set中；
        * 遍历节点n所有的邻近节点：
            * 如果邻近节点m在close_set中，则：
                * 跳过，选取下一个邻近节点
            * 如果邻近节点m也不在open_set中，则：
                * 设置节点m的parent为节点n
                * 计算节点m的优先级
                * 将节点m加入open_set中
            * 如果邻近节点m已经在open_set中，则
                * 检查这条路径是否更优，也就是说经由节点n到达节点m是否具有更小的 G 值。如果没有，不做任何操作。有则设置节点m的parent为节点n并计算节点m的优先级。

### 解释2 （参考：[A星算法详解](https://blog.csdn.net/hitwhylz/article/details/23089415)）
* A. 把起点加入 open list 。
* B. 重复如下过程：
    * a. 遍历 open list ，查找 F 值最小的节点，把它作为当前要处理的节点。
    * b. 把这个节点移到 close list 。
    * c. 对当前方格的 8 个相邻方格的每一个方格？
       * 如果它是不可抵达的或者它在 close list 中，忽略它。否则，做如下操作。
       * 如果它不在 open list 中，把它加入 open list ，并且把当前方格设置为它的父亲，记录该方格的 F ， G 和 H 值。
       * 如果它已经在 open list 中，检查这条路径 ( 即经由当前方格到达它那里 ) 是否更好，用 G 值作参考。更小的 G 值表示这是更好的路径。如果是这样，把它的父亲设置为当前方格，并重新计算它的 G 和 F 值， H 值不变。如果你的 open list 是按 F 值排序的话，改变后你可能需要重新排序。
    * d. 停止，当你
       * 把终点加入到了 open list 中，此时路径已经找到了，或者
       * 查找终点失败，并且 open list 是空的，此时没有路径。
* C. 保存路径。从终点开始，每个方格沿着父节点移动直至起点，这就是你的路径。

### 特点：  
- 根据启发函数的特点，A*算法**不一定具备最优性**
- 适用范围：适用于静态环境和低维度路径规划，特别适用于事先已知部分环境的场景，例如车辆拥有部分道路信息时，A算法可以利用启发式来减少不必要的状态遍历

## 2. A*算法和Dijkstra算法对比

- 两种算法均为**静态规划算法**(外界环境不变，计算最短路径)。
- Dijkstra算法计算源点到**其他所有点**的最短路径长度，A*关注源点到终点的最短路径。
- Dijkstra算法建立在较为**抽象的图论层面**，A*算法可以更轻松地用在诸如游戏地图寻路中。
- Dijkstra算法的实质是**广度优先搜索**(因为在搜索到目标点之前，搜索了所有可能的点)，是一种发散式的搜索，所以空间复杂度和时间复杂度都比较高。对路径上的当前点，A*算法不但记录其到源点的代价，还计算当前点到目标点的期望代价，是一种启发式算法，也可以认为是一种深度优先的算法。
- 由第一点，当目标点很多时，A*算法会带入大量重复数据和复杂的估价函数，所以如果不要求获得具体路径而只比较路径长度时，Dijkstra算法会成为更好的选择。  
————————————————  
版权声明：本文为CSDN博主「hopeping128」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。  
原文链接：https://blog.csdn.net/hopeping128/article/details/78960326 （链接中含动图说明）

## 文件说明
|--A_star_Matlab 基于栅格地图的A_star算法的Matlab实现  
参考：[B站 小黎的Ally：路径规划与轨迹跟踪系列算法学习_第4讲_A*算法](https://www.bilibili.com/video/BV1Jt4y1z7Ry?spm_id_from=333.788.recommend_more_video.2&vd_source=be5bd51fafff7d21180e251563899e5e%3E)  
|--- A_star_python.ipynb 基于栅格地图的A_star算法的python实现(将原作者的python文件转为ipynb)  
参考：[Github: zhm-real/PathPlanning](https://github.com/zhm-real/PathPlanning)  
## 其他参考

A-star

A-star Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

A-star

A-star Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

Download README