【学习笔记】A*

简介

A*算法是一种在图形平面上，有多个路径中寻找一条从起点到终点的最短遍历路径，属于启发式搜索，因为它使用启发式的方法来计算图中的节点，从而减少实际的计算量，提高搜索效率。

原理

A*算法结合Dijkstra和Best-First-Search算法的特点 (不是BFS)。它用一个估价函数$f(n)=g(n)+h(n)$，估算从起点到终点的总代价，$g(n)$表示起点到当前节点的代价，$h(n)$是当前节点到终点的启发式估价。

A*通过扩展路径代价最小的节点来寻找目标点，它保证如果$h(n)$的估计值是准确的，那么找到的路径也是最短的。相较于Dijkstra算法一直遍历距离较近的点，在A*的算法中增加启发式函数$h(n)$会减少收录的数量，加快算法到终点的速度。

流程

例题

八数码难题

后记

因为k短路有些实力，先咕着