| Pages: [1] :: one page |
|
|
| Author |
Thread Statistics | Show CCP posts - 0 post(s) |
Syds Sinclair
   |
Posted - 2010.03.06 02:27:00 -
[1]
..When I try to optimize a 17 waypoint route, I get a message saying that anything above 12 waypoints will take an extremely long time. I was just wondering does anyone have any experience with optimizing a 12 waypoint route, and also if anyone has ever done a 13+ route? About how long did each take to optimize? Thanks folks!
|
Boltorano
Fourth Circle
Total Comfort
|
Posted - 2010.03.06 02:32:00 -
[2]
I'm no expert on pathfinding logic, but I'd imagine that the number of possible routes between your specific waypoint would matter significantly in addition to the number of waypoints.
|
Lance Fighter
Amarr
|
Posted - 2010.03.06 02:44:00 -
[3]
assuming a=start
b=waypoint2.. etc
optimizing one system: No time..
2: distance from A-b-c less than a-c-b
3: distance from a-b-c-d, a-c-d-b, a-d-c-b, a-c-b-d a-d-b-c, a-b-d-c
1, 2, 6.. looks like a factorial.
and.. 12! is 479,001,600.
13! = 6,227,020,800
I think you get the picture.
OHGODS BELOW THIS LINE IS MY SIG !!!! SRSLY!
Blane Xero > Lance is at -0.9 sec status with a 1 million bounty. Lance is also amarrian. Thats 3 evil points |
Liang Nuren
The Aduro Protocol
Talon Alliance
|
Posted - 2010.03.06 02:51:00 -
[4]
Edited by: Liang Nuren on 06/03/2010 02:51:42
 Originally by: Lance Fighter
1, 2, 6.. looks like a factorial.
http://en.wikipedia.org/wiki/A _search_algorithm
-Liang
Ed: It breaks the forumz. Try this one: http://bit.ly/C71BQ
--
Liang Nuren - Eve Forum ***** Extraordinaire |
Boltorano
Fourth Circle
Total Comfort
|
Posted - 2010.03.06 02:53:00 -
[5]
Originally by: Lance Fighter
all the speculative math I was too lazy to come up with myself
Exactly what I was thinking, thanks!
|
Taedrin
Gallente
The Green Cross
DEFI4NT
|
Posted - 2010.03.06 02:57:00 -
[6]
Good day to you, Syds Sinclair. Have you met my good friend, Mr. Traveling Salesman? You two should have a good chat together some time.
----------
Originally by: Dr Fighter
"how do you know when youve had a repro accident"
Theres modules missing and morphite in your mineral pile.
|
Syds Sinclair
|
Posted - 2010.03.06 03:10:00 -
[7]
..Thanks for the math folks. I'll stick to 12 max as I optimized with 12 and it calculated the path within seconds. One more questions, when you use waypoints and auto pilot, when you get to a system that you have as a waypoint, will the auto pilot disable until you start it up again? Thanks all!
|
Liang Nuren
The Aduro Protocol
Talon Alliance
|
Posted - 2010.03.06 03:14:00 -
[8]
Originally by: Taedrin
Good day to you, Syds Sinclair. Have you met my good friend, Mr. Traveling Salesman? You two should have a good chat together some time.
http://en.wikipedia.org/wiki/Travelling_salesman_problem
Pay special attention to the parts about "heuristics" and "approximation". I think for something like Eve, an approximation would be fine.
-Liang
--
Liang Nuren - Eve Forum ***** Extraordinaire |
Syds Sinclair
|
Posted - 2010.03.06 03:35:00 -
[9]
..Ah nice. Great read. Thanks for sharing that. Just to say that Eve has some things going for it, the waypoint optimization turned my 105 jump, 12 waypoint route into a 38 jump route =D Bad thing is, I'm traveling in a freighter >.> Thanks for all of your replies people!
|
Kyra Felann
Gallente
|
Posted - 2010.03.06 03:46:00 -
[10]
Originally by: Syds Sinclair
..Thanks for the math folks. I'll stick to 12 max as I optimized with 12 and it calculated the path within seconds. One more questions, when you use waypoints and auto pilot, when you get to a system that you have as a waypoint, will the auto pilot disable until you start it up again? Thanks all!
There is an option for this, but by default, yes.
|
|
|
Taedrin
Gallente
The Green Cross
DEFI4NT
|
Posted - 2010.03.06 04:09:00 -
[11]
Edited by: Taedrin on 06/03/2010 04:12:18
Originally by: Liang Nuren
Originally by: Taedrin
Good day to you, Syds Sinclair. Have you met my good friend, Mr. Traveling Salesman? You two should have a good chat together some time.
http://en.wikipedia.org/wiki/Travelling_salesman_problem
Pay special attention to the parts about "heuristics" and "approximation". I think for something like Eve, an approximation would be fine.
-Liang
To be frank, they probably threw in waypoint optimization because Djikstra's algorithm (or whatever the one is you use for TSP) is easy to implement and is fine for most players. How often do you need to find the shortest route between more than two or three waypoints, anyways?
I'm not that experienced with traversing a graph, but I bet that it's a pain to translate the heuristics that humans use subconsciously when solving the TSP to a computer language.
----------
Originally by: Dr Fighter
"how do you know when youve had a repro accident"
Theres modules missing and morphite in your mineral pile.
|
Liang Nuren
The Aduro Protocol
Talon Alliance
|
Posted - 2010.03.06 04:20:00 -
[12]
Originally by: Taedrin
How often do you need to find the shortest route between more than two or three waypoints, anyways?
Every single day. For me, anyway.
-Liang
--
Liang Nuren - Eve Forum ***** Extraordinaire |
Callista Sincera
Amarr
|
Posted - 2010.03.06 09:05:00 -
[13]
Slightly offtopic: Would be nice if we could set regions as destinations and have the AP travel to the closest system in that region.
-
In simplistic terms it has been said that there is enough Zero Point Energy in the volume the size of a coffee cup to boil away EarthÆs oceans. |
Vossejongk
Caldari
Bendebeukers
Green Rhino
|
Posted - 2010.03.06 09:17:00 -
[14]
I use this alot and it can take a minute or 3/4/5 to calculate more then 15, but when i'm waiting I just do something else like read my e-mail or a news website or w/e (eve windowed mode and dual screens)
But then again I cant really approve of any of this because this is my signature |
Lance Fighter
Amarr
|
Posted - 2010.03.06 09:22:00 -
[15]
Originally by: Liang Nuren
Edited by: Liang Nuren on 06/03/2010 02:51:42
Originally by: Lance Fighter
1, 2, 6.. looks like a factorial.
http://en.wikipedia.org/wiki/A _search_algorithm
-Liang
Ed: It breaks the forumz. Try this one: http://bit.ly/C71BQ
So was i right?
OHGODS BELOW THIS LINE IS MY SIG !!!! SRSLY!
Blane Xero > Lance is at -0.9 sec status with a 1 million bounty. Lance is also amarrian. Thats 3 evil points |
Liang Nuren
The Aduro Protocol
Talon Alliance
|
Posted - 2010.03.06 09:30:00 -
[16]
Originally by: Lance Fighter
So was i right?
There's ways to eliminate branches of the search path so that it doesn't scale quite like you would think.
-Liang
--
Liang Nuren - Eve Forum ***** Extraordinaire |
Alchemist's Alt
Gallente
Hysteria Nexus
|
Posted - 2010.03.06 09:34:00 -
[17]
Originally by: Lance Fighter
Originally by: Liang Nuren
Edited by: Liang Nuren on 06/03/2010 02:51:42
Originally by: Lance Fighter
1, 2, 6.. looks like a factorial.
http://en.wikipedia.org/wiki/A _search_algorithm
-Liang
Ed: It breaks the forumz. Try this one: http://bit.ly/C71BQ
So was i right?
Ofc you were but I bet they got confused with how n! works ;)
FIRST!! |
Marchocias
Silent Ninja's
|
Posted - 2010.03.06 13:23:00 -
[18]
This mathematical problem is well known to be NP-complete.
What this means, is that there is no known method of calculating the solution in less than polynomial time (think of that as meaning "a reasonable length of time").
Once you go past about 20 or so search locations for the salesman to travel to (probably less in fact), the time it takes to complete starts to hit age-of-the-solar-system proportions (assuming, of course, you are not approximating with heuristics, etc).
Your best bet is not to bother trying.
----
I belong to Silent Ninja (Hopefully that should cover it). |
|
|
| |
|
| Pages: [1] :: one page |
| First page | Previous page | Next page | Last page |