A-star: heuristic for several purposes

Question

Consider a simple grid where any point is connected to no more than four other points (the North-East-West-South region).

I need to write a program that calculates the minimum route from the selected starting point to any target points that are connected (there is a route consisting of target points between any two targets). Of course, there may be obstacles on the grid.

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

Or maybe A * is not the best way to solve this problem?

Answer 1

How many goals, tens or thousands? If your dozens will work fine, if thousands, then finding your nearest neighbor will give you tips on quickly setting up your data.

The tradeoffs are obvious, the spatial organization of your search data will take time, and on small sets brute force will be easier to maintain. Since you are constantly evaluating, I think that data structuring will cost a very low score.

An alternative way to do this would be to modify the fill fill algorithm, which stops when it reaches its destination during the flood.

Answer 2

First decide if you need to optimize, because any optimization will complicate your code and for a small number of purposes, your current solution is probably great for simple heuristics such as Manhattan distance.

Before you take the first step, calculate a heuristic for each target. Remember the closest target as the selected target and move towards it, but subtract the maximum possible progress in relation to any target from all other distances. You can consider this second meaning "metaheuristic"; it is an optimistic assessment of heuristics for other purposes.

In the next steps, calculate the heuristic for the current target and any goals with a "metaheuristic" that is less than or equal to the heuristic. Other goals cannot be better than heuristics, so you do not need to calculate them. The immediate goal will be the new current goal; move to it, subtracting the maximum possible progress from others. Repeat until you reach your goal.

Answer 3

Use the Dijkstra algorithm, which has the lowest cost for all reachable points. Then you simply select the target points from the exit.