A-star:针对多个目标的启发式 [英] A-star: heuristic for multiple goals

问题描述

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

Let's consider a simple grid, where any point is connected with at most 4 other points (North-East-West-South neighborhood).

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

I have to write program, that computes minimal route from selected initial point to any of goal points, which are connected (there is route consisting of goal points between any two goals). Of course there can be obstacles on grid.

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

My solution is quite simple: I'm using A* algorithm with variable heuristic function h(x) - manhattan distance from x to nearest goal point. To find nearest goal point I have to do linear search (in O(n), where n - number of goal points). Here is my question: is there any more efficient solution (heuristic function) to dynamically find nearest goal point (where time < O(n))?

也许 A* 不是解决这个问题的好方法?

Or maybe A* is not good way to solve that problem?

推荐答案

多少个目标，几十个还是几千个?如果十个你的方式工作正常，如果几千个然后最近邻搜索会给你设置的想法快速搜索您的数据.

How many goals, tens or thousands? If tens your way will work fine, if thousands then nearest neighbor search will give you ideas on setting up your data to search quickly.

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

The tradeoffs are obvious, spatially organizing your data to search will take time and on small sets brute force will be simpler to maintain. Since you're constantly evaluating I think that structuring the data will be worthwhile at very low numbers of points.

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

An alternate way to do this would be a modified flood fill algorithm that stops once it reaches a destination point during the flood.

这篇关于A-star:针对多个目标的启发式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！