最短路径算法the_short_path.pdf

据 Drew 所知最短路经算法现在重要的应用有计算机网络路由算法,机器人探路,交 通路线导航,人工智能,游戏设计等等。美国火星探测器核心的寻路算法就是采用的D*(D Star)算法。 最短路经计算分静态最短路计算和动态最短路计算。 静态路径最短路径算法是外界环境不变,计算最短路径。主要有Dijkstra算法,A*(A Star)算法。 动态路径最短路是外界环境不断发生变化,即不能计算预测的情况下计算最短路。如在 游戏中敌人或障碍物不断移动的情况下。典型的有D*算法。