EVE Search - I'm faster than the route optimizer!!!!

Check My IP Information

All Channels

EVE General Discussion

I'm faster than the route optimizer!!!!

» Click here to find additional results for this topic using Google

Monitor this thread via RSS [?]

Pages: [1] 2 3 :: one page

Author	Thread Statistics \| Show CCP posts - 1 post(s)
nardaq	Posted - 2006.09.09 03:36:00 - [1] you want to visit some systems. You set some waypoints You get a big mess @ waypoint. 239 jumps You using the al mighty "optimize" button You get a warming: ---- You have 13 waypoints set. It can take ridiculous amount of time to calculate the optimal route when waypoints are more than 10. Are you sure you want to continue? ----- 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 whoho!! I do namual optimize I was able to get it to 114 in just 15 min Great Job CCP, it seems the client has the speed of a computer from the year 1964, i think even slower!
Lala Ru Gallente Quasar Industries	Posted - 2006.09.09 05:01:00 - [2] The Traveling Salesman problem is NP-Complete. In plain English, these problems take a LONG time to solve.
President Hours	Posted - 2006.09.09 05:05:00 - [3] EVE has upwards 3,000 solar systems... each with their own planets moons, players, stations, scripts...so excuse the slowness. Find me a game that compares...
Hllaxiu Shiva Morsus Mihi	Posted - 2006.09.09 05:06:00 - [4] If you figure out a way to do this in linear time, tell me first, I'd like my name on that paper. --- Our greatest glory is not in never failing, but in rising up every time we fail. - Emerson
Lala Ru Gallente Quasar Industries	Posted - 2006.09.09 05:10:00 - [5] For the curious, educate yourself.
Anti Protagonist Gallente Archron Dusyfe Industries	Posted - 2006.09.09 05:10:00 - [6] see: Traveling Salesman Problem
Toki Asturias	Posted - 2006.09.09 05:20:00 - [7] Thanks Lala Ru that was an interesting read. Heres a little snippet for the OP An exact solution for 15,112 German cities from TSPLIB was found in 2001. The computations were performed on a network of 110 processors located at Rice University and Princeton University. The total computation time was equivalent to 22.6 years on a single 500 MHz Alpha processor.
Lazuran	Posted - 2006.09.09 09:16:00 - [8] Edited by: Lazuran on 09/09/2006 09:16:31 LOL @ the fanbois with their NP-complete traveling salesman problem. Guys, have you ever seen a car navigation system? these things run on low-power embedded CPUs and do a great job, they can even calculate a new route on the fly within 1-2 seconds while they get a traffic warning. First of all, the traveling salesman problem finds a path that visits all points (vertices) exactly once and returns to the starting point. Second, even for this problem, there are practical solutions for such small data sets as the ~5000(?) solar systems in EVE, as well as very fast heuristics that can find very good (often optimal) solutions within a very short time. Third, the actual problem for AP in EVE is not the traveling salesman problem, but the one the Dijkstra's algorihm solves efficiently and perfectly and runs in O(N¦) in the worst case: http://en.wikipedia.org/wiki/Dijkstra's_algorithm But hey, with your arrogance and ignorance, you made my day. ;-) "The whole of NYC is not 1.0. Some back alley in the Bronx is deep 0.0, while right outside NYPD headquarters is 1.0." -- Slaaght Bana
MysticNZ Solstice Systems Development Concourse	Posted - 2006.09.09 09:28:00 - [9] Just thinking about this myself for a bit and i'd be hard pressed to come up with code right away that could do something similar... it really depends... No idea how they are doing it, but, I remember when the highways were updated the auto pilot wasen't, which leads me to belive they have a seperate table somewhere for calculating the best route. -=====- Xorus is teh nub :D I heard that beats player with big stick now be a good carebear and mine me some veldspar - Xorus
MysticNZ Solstice Systems Development Concourse	Posted - 2006.09.09 09:32:00 - [10] Originally by: Lazuran Edited by: Lazuran on 09/09/2006 09:16:31 LOL @ the fanbois with their NP-complete traveling salesman problem. Guys, have you ever seen a car navigation system? these things run on low-power embedded CPUs and do a great job, they can even calculate a new route on the fly within 1-2 seconds while they get a traffic warning. First of all, the traveling salesman problem finds a path that visits all points (vertices) exactly once and returns to the starting point. Second, even for this problem, there are practical solutions for such small data sets as the ~5000(?) solar systems in EVE, as well as very fast heuristics that can find very good (often optimal) solutions within a very short time. Third, the actual problem for AP in EVE is not the traveling salesman problem, but the one the Dijkstra's algorihm solves efficiently and perfectly and runs in O(N¦) in the worst case: http://en.wikipedia.org/wiki/Dijkstra's_algorithm But hey, with your arrogance and ignorance, you made my day. ;-) Nice -=====- Xorus is teh nub :D I heard that beats player with big stick now be a good carebear and mine me some veldspar - Xorus

spurious signal Caldari Brainiacs	Posted - 2006.09.09 09:35:00 - [11] Originally by: Lazuran Edited by: Lazuran on 09/09/2006 09:16:31 LOL @ the fanbois with their NP-complete traveling salesman problem. Guys, have you ever seen a car navigation system? these things run on low-power embedded CPUs and do a great job, they can even calculate a new route on the fly within 1-2 seconds while they get a traffic warning. First of all, the traveling salesman problem finds a path that visits all points (vertices) exactly once and returns to the starting point. Second, even for this problem, there are practical solutions for such small data sets as the ~5000(?) solar systems in EVE, as well as very fast heuristics that can find very good (often optimal) solutions within a very short time. Third, the actual problem for AP in EVE is not the traveling salesman problem, but the one the Dijkstra's algorihm solves efficiently and perfectly and runs in O(N¦) in the worst case: http://en.wikipedia.org/wiki/Dijkstra's_algorithm But hey, with your arrogance and ignorance, you made my day. ;-) Heh, pwned So, CCP, why is your route optimiser so slow?
qrac Caldari Shiva Morsus Mihi	Posted - 2006.09.09 09:40:00 - [12] Originally by: Lazuran Edited by: Lazuran on 09/09/2006 09:16:31 LOL @ the fanbois with their NP-complete traveling salesman problem. Guys, have you ever seen a car navigation system? these things run on low-power embedded CPUs and do a great job, they can even calculate a new route on the fly within 1-2 seconds while they get a traffic warning. First of all, the traveling salesman problem finds a path that visits all points (vertices) exactly once and returns to the starting point. Second, even for this problem, there are practical solutions for such small data sets as the ~5000(?) solar systems in EVE, as well as very fast heuristics that can find very good (often optimal) solutions within a very short time. Third, the actual problem for AP in EVE is not the traveling salesman problem, but the one the Dijkstra's algorihm solves efficiently and perfectly and runs in O(N¦) in the worst case: http://en.wikipedia.org/wiki/Dijkstra's_algorithm But hey, with your arrogance and ignorance, you made my day. ;-) I think you're wrong in this. Dijkstra's algorithm can be used for calculating the route when you do a "set destination" but optimising a route with several waypoints is something different. -------------------------------------------
Kweel Nakashyn Minmatar Aeden	Posted - 2006.09.09 09:41:00 - [13] Originally by: Lazuran (...) these things run on low-power embedded CPUs (...) No. Most of GPS CPU are sized to handle more calculation than EVE client at the moment it were released. THey also can catch very high frequency/energy microwave. Don't even think you decypher something if you pulse slower than these. Second, GPS don't have to calculate a video game running backward. Third, actually a friend n my corp use Dijkstra's for the very same problem and the result he had were slower than in game. He's a doctor in informatics so don't even think he can't code :) Originally by: Lazuran (...) But hey, with your arrogance and ignorance, you made my day. ;-) You're welcome in our club :)
MysticNZ Solstice Systems Development Concourse	Posted - 2006.09.09 09:48:00 - [14] This sorta stuff really makes me wish I did better at maths. So hard at being a coder when you suck at maths -=====- Xorus is teh nub :D I heard that beats player with big stick now be a good carebear and mine me some veldspar - Xorus
Telorian Shoran	Posted - 2006.09.09 10:22:00 - [15] Edited by: Telorian Shoran on 09/09/2006 10:23:22 5000 systems in eve are really not that big. for example: i wrote a little python script that computed every p2p optimal route and saved it. with no otpimizing it didnt take longer than 5 minutes and i dont even think thats anywhere near fast. i guess writing the pickled routes back was some good chunk of time. also be aware that the eve universe has some unique structure that can be exploited. branching is usually quite low for example.
Lazuran	Posted - 2006.09.09 10:27:00 - [16] Originally by: Kweel Nakashyn No. Most of GPS CPU are sized to handle more calculation than EVE client at the moment it were released. LOL. Quote: THey also can catch very high frequency/energy microwave. Yeah right, the CPU. Jeeez... All GPS transmission is handled by special hardware, i.e. GPS chips with their own processor and transmission hardware which do nothing else than output the current coordinates and some other data on a serial or other interface. The route calculation is done by the "general purpose" CPU of the navigation systems, which is usually something like what current PDAs have. Quote: Third, actually a friend n my corp use Dijkstra's for the very same problem and the result he had were slower than in game. He's a doctor in informatics so don't even think he can't code :) As a former assistant professor of CS I can assure you, that you can find ignorant people and graduates who can't code at all levels. ;-) Quote: Edit : the forth point is just search GPS + CPU on google, you'll see some cpu specs. (I didn't linked them because I don't know CCP's policy against other compagny commercial links). Consider these CPU are designed to specifically run route optimisation between two to five points (and no 13 waypoints like in this example) and voila :) Again, you have no idea what you are talking about. The typical navigation systems today contain CPUs like Intel's Xscale, MIPS, ARM, SH3 etc., which are commonly found in PDAs everywhere and are NOT designed to run route optimization of any kind. They're general-purpose, low-power processors for embedded systems and mobile devices and run MUCH slower than the x86 CPU in your PC. "The whole of NYC is not 1.0. Some back alley in the Bronx is deep 0.0, while right outside NYPD headquarters is 1.0." -- Slaaght Bana
Commoner Caldari The Foundation of Free Traders The Core Collective	Posted - 2006.09.09 10:28:00 - [17] Originally by: Lazuran Edited by: Lazuran on 09/09/2006 09:16:31 LOL @ the fanbois with their NP-complete traveling salesman problem. Guys, have you ever seen a car navigation system? these things run on low-power embedded CPUs and do a great job, they can even calculate a new route on the fly within 1-2 seconds while they get a traffic warning. First of all, the traveling salesman problem finds a path that visits all points (vertices) exactly once and returns to the starting point. Second, even for this problem, there are practical solutions for such small data sets as the ~5000(?) solar systems in EVE, as well as very fast heuristics that can find very good (often optimal) solutions within a very short time. Third, the actual problem for AP in EVE is not the traveling salesman problem, but the one the Dijkstra's algorihm solves efficiently and perfectly and runs in O(N¦) in the worst case: http://en.wikipedia.org/wiki/Dijkstra's_algorithm But hey, with your arrogance and ignorance, you made my day. ;-) You'll often find embedded systems which are alot faster at a specific task. If you program an FPGA to do it's task by writing the hardware in VHDL you can get some serious speeds outta it. Just look at the dedicated AES encryption coprocessor on the VIA processors, this thing, despite being dog ass slow in everything, is more than 10 times faster to encrypt than your regular CPU without a piece of dedicated hardware. Point is, a CPU has to loads of stuff, most of it is done via the extensive software you write, compared to most embedded systems where the hardware is specifically designed to do a single task.
Raquel Smith Ferengi Commerce Authority	Posted - 2006.09.09 10:28:00 - [18] Edited by: Raquel Smith on 09/09/2006 10:30:45 Originally by: President Hours EVE has upwards 3,000 solar systems... each with their own planets moons, players, stations, scripts...so excuse the slowness. Find me a game that compares... There is in excess of 5000 systems, 60 regions, and 800 constellations and well over 14,000 jumps between those 5000 systems. Don't forget that it's (likely) optimising to avoid low security systems. ninja edit: Incidentally my A*/Djikstra's algorithm in Ruby using the t20 DB dump is pretty quick, but not as accurate as Eve's algorithm since I don't know their heuristic scoring method.
qrac Caldari Shiva Morsus Mihi	Posted - 2006.09.09 10:55:00 - [19] Originally by: Telorian Shoran Edited by: Telorian Shoran on 09/09/2006 10:27:29 Edited by: Telorian Shoran on 09/09/2006 10:23:22 5000 systems in eve are really not that big. for example: i wrote a little python script that computed every p2p optimal route and saved it. with no otpimizing it didnt take longer than 5 minutes and i dont even think thats anywhere near fast. i guess writing the pickled routes back was some good chunk of time. How big was the output-file? -------------------------------------------
Lazuran	Posted - 2006.09.09 10:55:00 - [20] Originally by: Commoner You'll often find embedded systems which are alot faster at a specific task. Yes. Quote: If you program an FPGA to do it's task by writing the hardware in VHDL you can get some serious speeds outta it. True, but please point me to consumer-level navigation systems which use FPGAs to speed up the routing. Quote: Just look at the dedicated AES encryption coprocessor on the VIA processors, this thing, despite being dog ass slow in everything, is more than 10 times faster to encrypt than your regular CPU without a piece of dedicated hardware. The VIA CPUs you mean are neither specifically built for embedded systems, nor are such functions rare in general-purpose CPUs (only under-used). All those SSE/MMX instruction set enhancements were also added to mainstream CPUs to speed up particular common algorithms. Quote: Point is, a CPU has to loads of stuff, most of it is done via the extensive software you write, compared to most embedded systems where the hardware is specifically designed to do a single task. Still, nothing in common navigation systems is specifically added to make the routing faster. They just use carefully coded algorithms. You can also see this if you just purchase a navigation software package with GPS receiver for your PDA or even for your smart phone. Neither the receiver, nor the PDA were specifically built for fast routing and still it works very well. ;-) "The whole of NYC is not 1.0. Some back alley in the Bronx is deep 0.0, while right outside NYPD headquarters is 1.0." -- Slaaght Bana

Tachy	Posted - 2006.09.09 11:18:00 - [21] Route finding programs use weighted routes. Main routes are hard coded for speeding up calculations for travel between larger cities. This helps for ignoring all the currently uninteresting pieces of information. Since EVE lost the highways, all jumps are of equal importance. And the routes often are done in respect to regions. That's the reason why you often find a shorter route when you're optimizing your trip manually. --==*-- Even with nougat, you can have a perfect moment.
Shiraz Merlot Octavian Vanguard RAZOR Alliance	Posted - 2006.09.09 11:25:00 - [22] Originally by: Lazuran Third, the actual problem for AP in EVE is not the traveling salesman problem, but the one the Dijkstra's algorihm solves efficiently and perfectly and runs in O(N¦) in the worst case: http://en.wikipedia.org/wiki/Dijkstra's_algorithm But hey, with your arrogance and ignorance, you made my day. ;-) You post too soon and are hoist by your own petard (trying to be too clever, ending up being wrong) ... the problem is the Traveling Salesman. Dijkstra won't give you the shortest route visiting multiple points, just the shortest route between two of them. Back to school!
evistin Multiverse Corporation	Posted - 2006.09.09 11:55:00 - [23] Dijkstra still remains a realtivly slow proccess to caculate. If anyone can find a soultion to the NP complete problem in maths, its probably will net you about 200 to 300 million dollars for the patent for it and I would think the guy is trying to cheat you still. What about the dual algorithm used in Cisco IGRP and EIGRP routers. Hop base metric with the ability to adjust for up to 5 other mertics. Would it be possible to modify it to say, quene count, mean number of players through on the route...etc..etc... ------------------- Management and Leadership û The Eve-online Guide
Lazuran	Posted - 2006.09.09 12:25:00 - [24] Originally by: Shiraz Merlot You post too soon and are hoist by your own petard (trying to be too clever, ending up being wrong) ... the problem is the Traveling Salesman. Dijkstra won't give you the shortest route visiting multiple points, just the shortest route between two of them. Back to school! If you read carefully, you will see that I did not address route optimization with multiple waypoints at all, only the AP in general, which is solveable by Dijkstra's. But then again, route optimization was the subject (so I was ignorant there) and that is NP-hard (though not identical to the TS problem), but depending on the number of waypoints and not solarsystems. So, what I said was valid, although I should have paid more attention to the OP ;-). "The whole of NYC is not 1.0. Some back alley in the Bronx is deep 0.0, while right outside NYPD headquarters is 1.0." -- Slaaght Bana
Macdeth Ephemeral Misgivings	Posted - 2006.09.09 12:51:00 - [25] 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.
Matthew Caldari BloodStar Technologies	Posted - 2006.09.09 13:23:00 - [26] 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.

Redundancy	Posted - 2006.09.09 14:07:00 - [27] There's the pathfinder, which uses an incredibly simple algorithm, but is written in C++ and draws most of its efficiency from calculating the shortest routes to all systems accessible on the map in one go and caching the result (since pathfinding from your current location is the most common operation required of it by far), and there's the brute force TSP algorithm, which is written in python, is not optimised in any way for the sort of map Eve has, and thrashes the aforementioned pathfinder cache, because it predates us having a semi-decent pathfinder and is almost a verbatim conversion of pseudo-code you could find in any first year CS textbook. As an intellectual challenge, it would be enticing to write something more efficient, better tuned to the spacial properties of the Eve map, and perhaps that relaxed the requirement of optimality or had a better chance of providing a near-optimal solution early in the search and feedback, allowing you to stop it when it had reached a sufficiently good solution for you... but these are the sorts of things I used to do in my spare time, before Eve consumed that as well (why am I at work on a Saturday?) and pragmatically, the TSP probably isn't worth the effort compared to all the other things that could do with improving and fixing.

Macdeth Ephemeral Misgivings	Posted - 2006.09.09 14:46:00 - [28] Markov chains, per whatever academic paper I skimmed, would do it to almost perfection for hundreds of waypoints pretty cheaply computational resource-wise, but aren't worth the programmer effort, like Matthew and you both say, for something so trivial unless an easily-applied algorithm was essentially handed to you.
DHU InMe Gallente JUSTICE Inc.	Posted - 2006.09.09 15:06:00 - [29] In short, for people with 9 waypoint and less, compuetr beat your ass. Over 9 waypoint, better thinking up your route ! And setting it up manually. For all the other people that think it easy as hell and blablabla. Dichtra etc... Becomme a programmer, and see what the real world problem in computer science technologie are. Technique DONE Finishing my BAC 4 month-- __ Eve Links Got a new idea ? (Last updated 9 Mai 06)
Dark Shikari Caldari Imperium Technologies Firmus Ixion	Posted - 2006.09.09 15:30:00 - [30] It is the travelling salesman problem, as you are visiting a list of vertices once each (your waypoints) and each has a distance between it and each of the other vertices. --[23] Member-- Originally by: DB Preacher The only time BoB's backs are to the wall is when Backdoor Bandit is in local.



Pages: [1] 2 3 :: one page
First page \| Previous page \| Next page \| Last page

COPYRIGHT NOTICE
EVE Online, the EVE logo, EVE and all associated logos and designs are the intellectual property of CCP hf. All artwork, screenshots, characters, vehicles, storylines, world facts or other recognizable features of the intellectual property relating to these trademarks are likewise the intellectual property of CCP hf. EVE Online and the EVE logo are the registered trademarks of CCP hf. All rights are reserved worldwide. All other trademarks are the property of their respective owners. CCP hf. has granted permission to EVE-Search.com to use EVE Online and all associated logos and designs for promotional and information purposes on its website but does not endorse, and is not in any way affiliated with, EVE-Search.com. CCP is in no way responsible for the content on or functioning of this website, nor can it be liable for any damage arising from the use of this website.