A star search: a lot of nodes and a "slow" CheckLink between nodes... any suggestions?

Question

I'm facing an optimization problem:

I've a graph with a lot of nodes (10^5) that represents points on a plane surface.

I need to find the shortest path on the graph in order to reach the "end node", starting from the "start node".

any pair of nodes can be connected or not. Checking if they are connected is a very costly operation. If they are connected, the weight associated to the link is the euclidean distance between the two nodes.

At the moment I'm only checking all links from the "current node" to every other node, in order to fill the "open list" for A*. I chose A*, beacuse it seems the best algorithm in pathfinding and I've a fast, admissible and easy heuristic H for a node J (H = distance to the goal) but I'm not sure it's good for my problem.

Building the graph up front is unmanageable, N^2 links needs to be checked, it's too slow. At the moment (almst) the entire graph is built only if there's no solution, no path from the beginning to the end.

I'd like a hint for a better solution... thank you!

Answer 1

This is really two problems in one. I'm not familiar with the Bresenham algorithm, so I can only suggest you check out the optimization given in the Wikipedia and the links there.

As for A*: it building almost the entire graph is, as I said before, nearly unavoidable. You could experiment with variants such as recursive best-first search or IDA* (Russell & Norvig, chapter 4 in the 2nd ed.) to save some memory and maybe some time, if your memory is slow..

Depending on your graph structure, it might also be worthwhile to implement a bidirectional search. The simplest bidir algorithm would run A* search from A to B in one thread and from B to A in another, until either of them finds a solution or finds out that it is stuck. The other thread can then be killed. (One problem with this is that if there is a solution, you've wasted a lot of time, so it's only useful if you have a spare processor core that would otherwise be idle.)

A more sophisticated algo would also check if the two find the same point in the graph, then kill the threads and combine their results. This can be implemented by interleaving the steps in the two searches; a parallel version might be quite complicated.