Pages: [1] :: one page |
|
Author |
Thread Statistics | Show CCP posts - 0 post(s) |
Etien Aldragoran
DarkStar 1 GoonSwarm
|
Posted - 2009.02.03 19:43:00 -
[1]
If you try to optimize a course with 12 or more waypoints, you get the following message:
Quote:
You have 13 waypoints set. It can take ridiculous amount of time to calculate the optimal route when waypoints are more than 12.
Are you sure you want to continue?
Thinking this was as artifact from the Pentium III era of processing I proceeded with trying to optimize a course with 19 waypoints. That was about ten minutes ago and both cores on my CPU have been rather busy since then and my client is non-responsive. I understand the math needed to find the quickest route but I cant quite understand why it's this time intensive considering how quickly EVE determines single point-to-point routes. |
pod saleswoman
|
Posted - 2009.02.03 19:57:00 -
[2]
Edited by: pod saleswoman on 03/02/2009 19:57:17 They probably use a brute force approach which would be ~O(n!). If they invest a great deal of space to solving the problem, they can't beat O(2^n). In the former case, finding the best route through 13 systems takes ~13x longer than finding the best route through 12 systems. In the latter case, finding the best route through 13 systems takes ~2x as long as finding the best route through 12 systems. In either case, a process that takes 1 second for 1 route would take hours (or longer) for a 13-stop route. |
Tzar'rim
|
Posted - 2009.02.03 21:10:00 -
[3]
Traveling Salesman Problem |
Grarr Dexx
Amarr Divinity's Edge
|
Posted - 2009.02.03 21:36:00 -
[4]
Originally by: Tzar'rim Traveling Salesman Problem
Good read.
|
Kagura Nikon
Minmatar The Black Dawn Gang
|
Posted - 2009.02.04 00:10:00 -
[5]
The traveling salesman problem became outdated since E-Bay. Why woudl I travel to sale stuff If i can put it on internet? duuuhhh ------------------------------------------------- If brute force doesn't solve your problem... you are not using enough
|
Rakshasa Taisab
Caldari Sane Industries Inc. Ursa Stellar Initiative
|
Posted - 2009.02.04 05:43:00 -
[6]
/ME eyes his telephone-book thick Algorithms and Datastructures book.
Oh yes... Bad CCP for having been lazy! And here there is no specific need for searching for the absolutely shortest path either, you can go with something that is close enough to shortest. The remote chance that there's a route that saves you one or two jumps for a 20-waypoint route is not worth an extra 5 hours of calculation. |
Ki Tarra
Caldari Ki Tech Industries
|
Posted - 2009.02.04 17:04:00 -
[7]
Originally by: Rakshasa Taisab Oh yes... Bad CCP for having been lazy!
This!
If you want to plot longer courses try using something like Grismar's navigator.
Mean while CCP could improve their auto-pilot TSM algorithm, or they can make us new content. I vote for the latter.
|
Bronson Hughes
ADVANCED Combat and Engineering
|
Posted - 2009.02.04 17:19:00 -
[8]
This isn't really even an example of the Travelling Salesman problem. In the TSP you're solving for the shortest path between a set of points by choosing the order of the points you visit but in EvE, the order of the waypoints is fixed so you should just have n sets of point-to-point paths. Mind you, that's not necessarily an easy problem, but it's not strictly a TSP.
Now, if you're feeling really brave, try reading up on this. |
Gaogan
Gallente Solar Storm Sev3rance
|
Posted - 2009.02.04 19:22:00 -
[9]
Originally by: Bronson Hughes This isn't really even an example of the Travelling Salesman problem. In the TSP you're solving for the shortest path between a set of points by choosing the order of the points you visit but in EvE, the order of the waypoints is fixed so you should just have n sets of point-to-point paths. Mind you, that's not necessarily an easy problem, but it's not strictly a TSP.
Now, if you're feeling really brave, try reading up on this.
Ummm.... no, they are not fixed. When you click optimize route, you are asking it to reorder the waypoints to minimize the distance.
The problem is the same reason that sorting a croweded overview is so laggy... they use a poor algorithm in a scripting language interpreter ( python ) instead of doing it right.
|
An Anarchyyt
Gallente Battlestars GoonSwarm
|
Posted - 2009.02.04 21:48:00 -
[10]
You even had the word "ridiculous" right in front of you and you still couldn't spell it.
:ds1:
Originally by: CCP Wrangler Second, a gentile is a non jewish person
|
|
Xianthar
STK Scientific The Initiative.
|
Posted - 2009.02.05 06:16:00 -
[11]
this isn't a case of the TSP, TSP involves the edges of the graph having weights, plotting a route in eve does not involves weights, simply the number of edges (thus number of jumps). Plotting routes in eve is much simpler (not saying much as the TSP is NP-complete)
it would be cool if they actually took the distance in AU between gates into account, now that would take some processing time....
as to why it takes so long, an ugly aproach to the problem could easily create an O(n!) complexity...i.e. it takes a lot of cycles really fast as the number of waypoints grows.
most of the out of game tools use the A* algorithm which is normally poly-nomial in complexity, but it eats memory in its standard incarnation and thus may not have been acceptable for use in game.
cheers,
x
|
Kagura Nikon
Minmatar The Black Dawn Gang
|
Posted - 2009.02.05 23:07:00 -
[12]
Originally by: Xianthar this isn't a case of the TSP, TSP involves the edges of the graph having weights, plotting a route in eve does not involves weights, simply the number of edges (thus number of jumps). Plotting routes in eve is much simpler (not saying much as the TSP is NP-complete)
it would be cool if they actually took the distance in AU between gates into account, now that would take some processing time....
as to why it takes so long, an ugly aproach to the problem could easily create an O(n!) complexity...i.e. it takes a lot of cycles really fast as the number of waypoints grows.
most of the out of game tools use the A* algorithm which is normally poly-nomial in complexity, but it eats memory in its standard incarnation and thus may not have been acceptable for use in game.
cheers,
x
It does involve weights yes. System takes into account the security ratting as in a 1 or 0 weight if you have asked to stay in high sec. And also takes into account traffic control (they do try to avoid systems with traffic control when the detiour is SHORT.
Not a very complex TSP but still valid proposition of a basic TSP |
|
|
|
Pages: [1] :: one page |
First page | Previous page | Next page | Last page |