本文转载自雷锋网。如需转载，请到雷锋网官网申请授权。广度优先搜索、Dijkstra和A*是图上三种典型的路径规划算法。两者都可以用于图搜索，区别在于queue和heuristicfunction两个参数。该项目探索并可视化不同算法如何根据所选参数执行图形搜索。该算法的一般原理如下：将边界初始化为包含起始节点的队列。当边界队列不为空时，“访问”并从队列中移除一个“当前”节点，同时将被访问节点的每个邻居节点加入队列，其成本为到达当前节点的成本加上成本从当前节点访问邻居的代价，加上邻居节点和目标节点的启发函数值。其中启发式函数是对两个节点之间路径成本的估计。存储访问路径（通常存储在cameFrom图中），用于后续重建路径。如果邻居节点已经在列表中并且新路径的成本较低，则更改其成本。当找到目标路径（提前退出）或列表为空时停止算法。BFS使用先进先出队列实现BFS。这样的队列忽略路径中链路的开销，并根据跳数缩放，因此可以保证找到与跳数无关的最短路径。启发式函数的选择是任意的，因为它在这个过程中不起作用。使用数组允许先进先出，其中元素附加到末尾并从开头删除。BFS演示动画。注意边界节点（黄色）如何扩展为网格中的正方形。在这里，正方形是一组具有相同“跳跃距离”的节点。Dijkstra算法是通过使用优先级队列和在图上始终返回0的启发式函数获得的。与BFS相比，Dijkstra最大的不同在于它考虑了成本。使用此算法，可以根据节点到节点的成本找到最短路径。优先级队列是使用数组实现的，在每次插入新节点后对数组进行排序。尽管还有其他更有效的方法来实现优先级队列，但在我们的例子中，数组足够快且易于实现。Dijkstra展示动画，注意此时的边界是一个圆。A*为了实现A*算法，需要传递一个实际的启发式函数，比如两个节点之间的欧氏距离。节点由“节点成本”+“从节点到目标节点的估计成本”加权，以通过优先搜索更可能的节点来加速搜索。借助启发式算法，A*可以比Dijkstra或BFS更快地找到正确的路径。非可采纳启发式函数A*只能通过应用可采纳启发式函数找到最短路径，这也意味着该算法永远不会高估实际路径长度。由于欧几里德距离是两点之间的最短距离/路径，因此永远不会超过欧几里得距离。但是，如果将它乘以常数k>0会怎样？这高估了距离，使其成为不可接受的启发式算法。k值越大，算法越容易达到目标，但同时精度下降，导致生成的路径并不总是最短的。算法实现本项目通过Javascript实现，读者可以在Web上访问。此外，我使用react来渲染UI，并使用react-konva来渲染图形。路径查找意味着接受队列类型和启发式函数，并返回另一个函数，即真正的路径查找（称为柯里化）。这样，每次用户更改设置时，都会创建一个带有特定参数的新路径发现函数，并用于图形搜索。为了可视化路径发现的步骤，我使用了javascript生成器，这意味着该函数返回一个迭代器，而不仅仅是一个值。因此，在每一步，访问者都可以生成算法的完整状态，将其保存到数组中，然后通过页面顶部的滑块显示特定状态。此链接进入交互演示页面：https://interactive-pathfinding.netlify.com/
