Python Programming Contest
Tom Anderson
twic at urchin.earth.li
Sat Jul 16 11:21:25 CEST 2005
On Sat, 16 Jul 2005, Joseph Garvin wrote:
> Someone correct me if I'm wrong -- but isn't this the Shortest Path problem?
Dang! I was just about to point that out.
> I don't foresee anyone getting a more efficient solution than what they
> can find in hundreds of algorithms textbooks. If this is indeed the case
> it should just come down to whoever can pull the narliest tricks to
> create a fast python implementation of the algorithm.
I guess part of the challenge is seeing through the description to the
underlying problem - in this case, seeing that this can be cast as
shortest-path. Not everyone would necessarily realise that! In particular,
the fact that the available flights, and their prices, can be different on
different days could well throw people.
But yes, this is basically about who can write the fastest implementation
of Dijkstra's algorithm. I've got one somewhere - i have a half-finished
journey planner for the London Underground! - so maybe i should enter ...
Hmm. Actually, Dijkstra's algorithm isn't always the fastest way to find
the shortest path. The thing is, it's fully general, so it works on
absolutely any graph; if the graph you're traversing has particular
properties, you might be able to leverage those to find a solution faster.
For instance, if your graph is a road network, you can put a lower bound
on the distance from any vertex to the goal (being the straight-line
distance between them - no path over actual roads can be any shorter than
that), which allows you to do an A* search, which is a lot faster than
Dijkstra. My own journey planner is also a case of this - i exploit
various obvious properties of tube trains to avoid examining a large
number of possible but daft travel plans.
I can't immediately see any properties of this network that could be
exploited, but that doesn't mean there aren't any.
tom
--
taxidermy, high tide marks, sabotage, markets, folklore, subverting, .
More information about the Python-list
mailing list