3 ms·
I had an idea when I took my algo class to overlay a small graph of "highways" on a map and computer all pairs shortest path to that sub graph. Then when you do
by sand500 10y ago
I had an idea when I took my algo class to overlay a small graph of "highways" on a map and computer all pairs shortest path to that sub graph. Then when you do your search, you do BFS from both the start and goal till you reach a *highway node" and then you have a short but not optimal path between two points without too much computation.
- mcguire 10y agoSure, accepting a sub-optimal result often makes an infeasible problem easy. Extra credit if you can bound the sub-optimality.
- TillE 10y agoSomething like that is an essential optimization when pathfinding over long distances. You often need to answer the question can I go from A->B->C long before you need to say how exactly you do it.