MATLAB算法实战应用案例精讲-【优化算法】A*算法

前言

A*算法最早于1964年在IEEE Transactions on Systems Science and Cybernetics中的论文《A Formal Basis for the Heuristic Determination of Minimum Cost Paths》中首次提出。

其属于一种经典的启发式搜索方法，所谓启发式搜索，就在于当前搜索结点往下选择下一步结点时，可以通过一个启发函数来进行选择，选择代价最少的结点作为下一步搜索结点而跳转其上。

传统的算法中，深度优先搜索(DFS)和广度优先搜索(BFS)在展开子结点时均属于盲目型搜索，也就是说，它不会选择哪个结点在下一次搜索中更优而去跳转到该结点进行下一步的搜索。

在运气不好的情形中，均需要试探完整个解集空间, 显然，只能适用于问题规模不大的搜索问题中。

而与DFS,BFS不同的是，一个经过仔细设计的启发函数，往往在很快的时间内就可得到一个搜索问题的最优解。

几个高频面试题目

Dijkstra与A* 对比

相同点：

两者都是以寻找最短路径为目的的算法。

不同点：

Dijkstra算法遍历的时候是对4周平等对待，没有区分的盲目进行遍历。

A* 算法是在迪杰斯特拉算法的基础上进行改进的一种算法。

与之不同的是，A* 算法是一种启发式搜索，不会像dijkstra算法一样对整个地图都进行遍历，A* 算法是有方向的遍历。

它会对周围各点进行评估，然后再进行搜索。

算法原理

A*（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法。