# About path finding(in Graphs)..

Show 80 post(s) from this thread on one page
Page 2 of 2 First 12
• 11-09-2011
Elysia
Quote:

Originally Posted by manasij7479
:Too much Calculation:
Though this can become ineffective if I try to manage subnets recursively....

I would think crunching numbers are faster than memory accesses. Anyway, don't throw the idea out the window before you actually see how it performs in real code.
• 11-09-2011
manasij7479
Quote:

Originally Posted by Elysia
I would think crunching numbers are faster than memory accesses. Anyway, don't throw the idea out the window before you actually see how it performs in real code.

Yes.. coupled with any algorithm, this gives a good advantage when I just want a good path..not analyze all the other possible ways to find the minimum 'tentative distance'...(And the first will typically be the one following the 'closest to straight' path )
• 11-09-2011
anduril462
I don't see much application for A* here, but if you're interested, take a look at A* search algorithm - Wikipedia, the free encyclopedia, particularly the Weighted A* section. That allows you to pick a heuristic that sometimes overestimates by a bit, resulting in faster but non-optimal paths. This shouldn't be a problem though, since you only need good enough. Your problem will be with devising a reasonable heuristic.

The IP address "distance" will not work as a heuristic for A*. For A* to be optimal, the heuristic must never overestimate the cost from any node to the goal. For spatial stuff, straight line is great, since it's the shortest possible distance between any two nodes. To do that, we require some sort of Cartesian coordinates for every node in the graph. We're looking the path with the shortest time, and there is no correlation between IP addresses and the latency between them. You would need something that guessed the fastest possible travel time between any node and the goal. That would have to account for the number of hops along the way, but the individual nodes don't know how far they are from the goal, so devising a valid heuristic is not really possible. We can't even make a reasonable guess as to how fast we can get from a node to the goal.

A little bit of Googling for "a algorithm for fastest times" (Google discards the *) turned up this paper, which might be a useful, if a little bit dry, read. It works with A*, so might have some useful heuristics to investigate.

EDIT: I judged that paper by the title and scanning the abstract, no idea how good it really is.
Show 80 post(s) from this thread on one page
Page 2 of 2 First 12