让我们考虑一个简单的网格,其中任何点与最多4个其他点(东北 - 西 - 南邻域)相连.
我必须编写程序,计算从所选初始点到任何目标点的最小路线,这些目标点是连接的(在任何两个目标之间存在由目标点组成的路线).当然网格上可能存在障碍.
我的解决方案很简单:我使用的是具有可变启发函数h(x)的A*算法 - 从x到最近的目标点的曼哈顿距离.为了找到最接近的目标点,我必须进行线性搜索(在O(n)中,其中n - 目标点数).这是我的问题:是否有更有效的解决方案(启发式函数)来动态找到最近的目标点(时间<O(n))？
或者A*不是解决这个问题的好方法吗？