Invisible <voi### [at] devnull> wrote:
> > This approach often may *not* give you the optimal route. However, given that it
> > will only very rarely be significantly worse than the optimal one, it is
> > definitely good enough.
>
> Depends on your definition of "optimal". (E.g., total distance, verses
> estimated travel time, any tolls that have to be paid for certain
> routes, traffic volume, etc.)

Well, it actually depends on *your* definition of "optimal": You as the user
assign a certain abstract "cost" to any of these parameters (typically by
choosing from a limited set of predefined factors), e.g.: A km of distance = 7
points, a minute estimated travel time = 10 points, a dollar of toll = 30
points, 40 miles of bad road = 80 points, ...

These abstract "cost" factors are then used to assign a cost to each road
section. The algorithm will then try to come up with a "cheap" route according
to these factors.

So from this perspective, the "optimum" is always well-defined: Lowest abstract
"cost". But even to these standards, the algorithm will only very seldom pick
the optimal route - because it would by any means not be efficient to do so.
After all, it doesn't make much sense to have your navigator spend 3 days
finding the optimal route, if within 30 seconds it can come up with one that is
at most 5 minutes longer :P

Post a reply to this message