A星：启发式实现多个目标

让我们考虑一个简单的网格，其中任意点最多与四个其他点（北-东-西-南邻域）相连。

我必须编写程序，该程序计算从选定的初始点到连接的目标点的最小路径（存在由两个目标之间的目标点组成的路径）。当然，网格上可能会有障碍。

我的解决方案非常简单：我正在使用具有可变启发式函数h（x）的A *算法-

从x到最近目标点的曼哈顿距离。要找到最近的目标点，我必须进行线性搜索（在O（n）中，其中n-

目标点数）。这是我的问题：有没有更有效的解决方案（启发式函数）来动态查找最近的目标点（时间<O（n））？

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

有几千个目标？如果十数条行之有效，如果成千上万种，那么最近的邻居搜索将为您提供设置数据以快速搜索的想法。

权衡是显而易见的，在空间上组织数据以进行搜索将需要时间，而在小型集合上，蛮力将更易于维护。由于您一直在进行评估，因此我认为在很少的情况下构造数据是值得的。

另一种执行此操作的方法是修改后的洪水填充算法，该算法一旦在洪水期间到达目的地点就会停止。