【动手学运动规划】 4.5 A*算法

文章预览

我宁愿永远做我自己，也不愿成为别人，即使那个人比你更快乐。 —《成为简·奥斯汀》 🏰 代码及环境配置 ：请参考 环境配置和代码运行 ! 4.5.1 概述 Dijkstra算法是基于广度优先搜索策略来遍历空间内的所有节点，最终计算出全局最优的路径，其计算量非常大。而基于启发式的 贪婪最佳优先搜索 （greedy best first search，GBFS）速度快，但结果可能不是最优的。那么，如何将二者的优势结合呢，即在Dijkstra算法基础上，引入启发式策略。这就是A*算法。 🌟 Note： 最佳优先搜索算法是在广度优先搜索的基础上，用启发估价函数对将要被遍历到的点进行估价，然后选择代价小的进行遍历，直到找到目标节点或者遍历完所有点，算法结束。 4.5.2 算法详解 A*算法结合了GBFS算法和Dijkstra算法的优点，通过评估函数 来指导搜索过程， 定义为从起点到节点 n 的实 ………………………………