本文转自雷锋网，如需转载请至雷锋网官网请求授权。

广度优先查找、Dijkstra和A*是图上的三种典型途径规划算法。它们都可用于图查找，不同之处在于行列和启发式函数两个参数。

本项目探究并可视化不同算法怎么依据挑选参数进行图查找。

算法的一般性原理如下：

将鸿沟初始化为包括开始节点的行列。

当鸿沟行列不为空时，从行列中“拜访”并删去一个“当时”节点，一起将拜访节点的每个街坊节点添加到行列，其本钱是抵达当时节点的本钱加上从当时节点拜访街坊的本钱再加上街坊节点和方针节点的启发式函数值。其间，启发式函数是对两个节点的途径本钱的估量。

存储拜访途径（一般存储在cameFrom图中），以便后续重建途径。假如街坊节点已经在列表中，一起新途径的本钱较低，那么更改其本钱。

找到方针途径（提早退出）或列表为空时，中止算法。

BFS

运用先进先出行列完成BFS。这种行列会疏忽途径中链接的开支，并依据跳数进行扩展，因而能够保证找到最短途径的跳数，而跳数相关的本钱。启发式函数的挑选是恣意的，因为在这个过程中其并不起作用。

运用数组可完成先进先出，行将元素附加到结尾并从头删去。

BFS演示动图。留意鸿沟节点（黄色）是怎么在网格中扩展为正方形的。在这里，正方形是相同“跳距”的节点集。

Dijkstra

在图上运用优先级行列和一直回来0的启发式函数，便得到Dijkstra算法。

比较于BFS，Dijkstra最大的不同在于考虑了本钱。经过该算法，能够依据节点到节点的本钱找到最短途径。

优先级行列运用数组完成，在每次刺进新节点后对该数组进行排序。虽然完成优先级行列还有其他更高效的办法，但在咱们的场景中，数组是足够快的，并且完成起来也简略。

Dijkstra展现动画，留意此刻的鸿沟是一个圆。

A*

为完成A*算法，需求传递一个实践启发式函数，例如两个节点之间的欧式间隔。经过“节点本钱”+“节点到方针节点的预算本钱”对节点进行加权，经过优先查找更大或许的节点加速查找速度。

凭借启发式办法，A*能够比Dijkstra或BFS更快地找到正确途径。

非答应的启发式函数

只要运用可答应启发式函数，A*才干找到最短途径，这也意味着算法永久不会高估实践途径长度。因为欧氏间隔是两点之间的最短间隔/途径，因而欧氏间隔绝不会超出。

但假如将其乘以常数k>0会怎样呢？这样会高估间隔，成为非答应的启发式函数。

k值越大，算法越简单抵达方针，但一起准确性下降，导致生成的途径并非总是最短的。

算法完成

本项目经过Javascript完成，以便读者在Web上进行拜访。别的，我运用react烘托UI，运用react-konva烘托图形。

途径发现是指承受行列类型和启发式函数，并回来另一个函数，即实在途径发现（称为currying）。

这样，用户每次更改设置后，都会运用确认参数创立一个新的途径发现函数，并将之用于图查找。

为可视化途径发现的过程，我运用javascript生成器，这意味着函数回来一个迭代器，而不仅仅是一个值。因而，访客在每一步都能够生成算法的整个状况，并将其保存到数组，然后经过页面顶部的滑块显现特定状况。

此链接进入交互演示页面：https://interactive-pathfinding.netlify.com/