路径规划之 A* 算法

  1. 云栖社区>
  2. 博客>
  3. 正文

路径规划之 A* 算法

paulquei 2019-01-09 11:40:15 浏览4049
展开阅读全文

算法介绍

A*(念做:A Star)算法是一种很常用的路径查找和图形遍历算法。它有较好的性能和准确度。本文在讲解算法的同时也会提供Python语言的代码实现,并会借助matplotlib库动态的展示算法的运算过程。

A*算法最初发表于1968年,由Stanford研究院的Peter Hart, Nils Nilsson以及Bertram Raphael发表。它可以被认为是Dijkstra算法的扩展。

由于借助启发函数的引导,A*算法通常拥有更好的性能。

广度优先搜索

为了更好的理解A*算法,我们首先从广度优先(Breadth First)算法讲起。

正如其名称所示,广度优先搜索以广度做为优先级进行搜索。

从起点开始,首先遍历起点周围邻近的点,然后再遍历已经遍历过的点邻近的点,逐步的向外扩散,直到找到终点。

这种算法就像洪水(Flood fill)

网友评论

登录后评论
0/500
评论
paulquei
+ 关注