A级明星：启发式的多重目标 [英] 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.

我的解决办法很简单：我使用的是A *算法可变启发函数H（X） - 曼哈顿距离从x到最近的目标点。要找到最近的目标点我必须做线性搜索（在O（n），其中N - 目标点数）。这里是我的问题：有没有更有效的解决方案（启发式函数）来动态查找最近的目标点（其中一次与LT;为O（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级明星：启发式的多重目标的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！