Dijkstra(迪杰斯特拉)算法
A*(A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法,也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近,最终搜索速度越快。
会从起点开始,向上、下、左、右四个方向的网格探索,如果没有找到终点的话,又会在这四个网格的基础上继续朝着四周向外探索,被探索过的网格不会被重复探索,但是会留下一个回溯标记,它指向了该网格,是由哪一个网格探索而来,这个算法会一直往外扩散,直到搜索到终点后,根据每一个网格的回溯标记,找到最短路径,
缺点:但是这个算法的局限性也很明显,就是搜索的时候没有方向性,在最差的情况下,需要检测完所有的网格才能找到路径,当网络很多时,计算量会很大
路径规划、游戏开发等场景中十分常见的一种算法, A* 算法的不同之处在于,它在检索周围网格时,记录了三个不同的数据
当探索遇到障碍物时,则不会探索这个网格 下面这个点,不是总花费最少的点,因为总花费是由从起点到该点的实际路径,和该点到终点的直线距离之和 所以在起点下方的点,才是下一步要探索的点 但这并不影响找到最短路径,也是 A* 算法的巧妙之处
模拟地图导航,每个路口,当成一个点
https://www.bilibili.com/video/BV1894y1V75p
本文来自博客园,作者:VipSoft 转载请注明原文链接:https://www.cnblogs.com/vipsoft/p/17880122.html
原文链接:https://www.cnblogs.com/vipsoft/p/17880122.html
本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728