algorithm - A-star:多个目标的启发式

Question

让我们考虑一个简单的网格，其中任何点最多与其他 4 个点相连(东北-西-南邻域)。

我必须编写程序，计算从选定的初始点到连接的任何目标点的最小路线(任意两个目标之间有一条由目标点组成的路线)。当然，网格上可能会有障碍。

我的解决方案非常简单:我使用具有可变启发式函数 h(x) - 从 x 到最近目标点的曼哈顿距离的 A* 算法。为了找到最近的目标点，我必须进行线性搜索(在 O(n) 中，其中 n - 目标点数)。这是我的问题:是否有更有效的解决方案(启发式函数)来动态找到最近的目标点(时间 < O(n))？

或者也许 A* 不是解决该问题的好方法？

Answer 1

有多少个目标，几十个还是几千个？如果你的方式是几十个就可以了，如果是几千那么nearest neighbor search将为您提供有关设置数据以快速搜索的想法。

权衡是显而易见的，在空间上组织您的数据以进行搜索将需要时间，并且在小型数据集上，蛮力将更易于维护。由于您一直在评估，我认为在非常低的点数上构建数据是值得的。

另一种方法是修改洪水填充算法，一旦它在洪水期间到达目的地点就会停止。