A 算法

文章结构概述

• A* 算法
  • Dijkstra 算法
  • 贪婪最佳优先搜索算法
  • 启发式函数
  • A* 算法的编程实现

A* 算法

A* 算法是用于寻找最短路径问题的一种方法，除此之外，还有诸如 Dijkstra 算法、Bellman-ford 算法、SPFA 算法以及 Floyd 算法等多种解决方案。

既然已有如此多的算法可供使用，为何还需要专门设计 A* 算法呢？
A* 算法与其他方法的主要区别在于其采用了启发式 搜索机制，而大多数传统算法则依赖于直接搜索方式。
相较于直接搜索方式，启发式 搜索显然具有一定的优势。直接搜索方式需要遍历所有可能到达目标的路径，并在最终比较后确定最短路径，在此过程中并不对任何路径进行筛选或处理。
而启发式搜索则通过引入特定的启发函数，在搜索过程中优先选择最有希望的路径，从而有效缩小了搜索范围，显著提升了整体效率。

A* 算法融合了 Dijkstra 算法与 Greed-Best-First-Search 算法的特点

Dijkstra算法原理与应用

Dijkstra算法是当前较为广泛应用于最短路径计算的经典方法。在该算法中，会维护一个dis[]数组，用于记录源节点至各个节点的最短距离。例如，若源节点设定为0号节点，则dis[i]所表示的即为从0