我正在寻找一种最佳路径算法,该算法可以找到从任何开始节点到最近退出节点的最佳路径。
在这种情况下,图形是一个正方形网格,相邻平方的所有成本均为 1。使用这些限制进行任何优化都可以。
基本上,您从随机选择的入口进入方形网格,现在您要找到最接近任何给定出口的路径。
到目前为止,我正在多次进行BFS,每次退出一次并结合结果。虽然我怀疑这是最有效率的方式。
你从所有出口开始做BFS。 当您发现一个新正方形时,它到最近出口的距离是前一个正方形的距离 +1,路径方向是朝向前一个正方形。
由于任何(距离,方向)元组都不取决于您输入的位置,因此您可以一次预先计算所有正方形的这些值,因此如果您从新入口重新开始,则不必重新进行搜索。