Matthew
Caldari
BloodStar Technologies
   |
Posted - 2006.09.09 13:23:00 -
[1]
 Originally by: Macdeth
Edited by: Macdeth on 09/09/2006 12:55:34
Given how the number of waypoints that the game completely melts down on is around 10-12, the algorithm used for route optimization is almost certainly O(n!), and on the fairly small data set of 5,334 vertices (solar systems) and 6,994 edges (jumps, since all are two-way) one can do far better than that.
The question is whether you want to take a programmer off something else for the time it would take them to read up on the better ways and devise an implementation for the eve client.
Originally by: nardaq
You are pressing OK and do someting els.
You getting back behind eve and find out that eve is still "optimizing". 1 hour passed! (99% cpu)
I quit game (its freeking STUCK)
I start EVE again
I see that the route is still there, buts its 233 now Very Happy whoho!!
I do namual optimize
I was able to get it to 114 in just 15 min
When you interrupt it mid-way through a search, you're basically playing a probability game. It will probably be running the most basic form of optimiser - draw up every single combination of waypoint ordering, and work out the number of jumps for each, always remembering the shortest one seen so far. Now, you could get lucky, and find a really short one on the first one you try. If you interrupted it in that situation, you'd get a really good result and you'd never beat it by hand. Or you could be unlucky, and the short ones are the last ones you try, in which case you could probably beat it by hand due to having the advantage of human judgement to summarily dismiss a lot of combinations.
That's one of the clever tricks you can use to speed up the solving of such problems, if you're willing to accept a "sufficiently good" answer, instead of wanting the perfect answer. Methods exist for defining a lower bound on the number of jumps the optimal route will have, without having to find that route (note that in fact such an "optimal" route may not actually exist, but no route shorter than that lower bound will exist). As you then go through testing routes, you can use that lower bound to generate a probability of finding a route shorter than your current shortest known route, and know the maximum number of jumps you can save by doing further optimising. You can therefore draw up a measure of at what point it's likely to be quicker just starting along your known route, rather than waiting for the results of more optimisation. After all, there's usually no point waiting 2 hours for optimisations if it's only going to save you 2 minutes of travel time.
That does still leave you exposed to chance to some extent, there will be some formulations of the input problem for which the cleverness won't help at all. But it will help in the average case.
-------
There is no magic Wand of Fixing, and it is not powered by forum whines. |