I ran into an optimization problem:
I have a graph with many nodes (10 ^ 5) that represents points on a flat surface.
I need to find the shortest path on the chart in order to reach the "end node", starting with the "start node".
any pair of nodes can be connected or not. Testing their connection is a very expensive operation. If they are connected, the weight associated with the link is the Euclidean distance between the two nodes.
Currently, I am checking all links from the "current node" to all other nodes to fill in the "open list" for A *. I chose A *, as this is the best path-finding algorithm, and I have a fast, valid and simple heuristic H for node J (H = distance to the target), but I'm not sure if this is good for my problem.
Plotting ahead is impossible, you need to check N ^ 2 links, it's too slow. At the moment (almst) the entire graph is built only if there is no solution, there is no way from beginning to end.
I would like to give a hint for a better solution ... thanks!
source
share