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.

The Wizz117	Posted - 2006.09.09 17:21:00 - [31] Originally by: Redundancy There's the pathfinder, which uses an incredibly simple algorithm, but is written in C++ and bla bla complicated text etc blabla. maybe we could find some volunteers who sit behind theyr computer all day learning the whole eve map out of theyr head and let them do the patfinding instead of the current patfinding system wich does not work. ------------------------------------------- That ccp created a universe doesen't mean they'r gods
FireFoxx80 Caldari E X O D U S Imperial Republic Of the North	Posted - 2006.09.09 17:24:00 - [32] I had A* working for my trading application (find safe routes without entering <=0.4. It ran like a pig on VB.NET. What I do the rest of the time - Vote for a Jita bypass!
Lala Ru Gallente Quasar Industries	Posted - 2006.09.09 18:24:00 - [33] Edited by: Lala Ru on 09/09/2006 18:25: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. The thing is, a car's navigation system doesn't need to prove that the route is the best possible route, and it probably has a lot of "cheats' built in so that it will automatically know to take the highways etc. In EVE, it's harder to do that because of all the filters you can put in. Originally by: Lazuran First of all, the traveling salesman problem finds a path that visits all points (vertices) exactly once and returns to the starting point. Which is the current waypoint problem plus one jump. Originally by: Lazuran 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. Such as . . . 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 Uh, that's "shortest path" which assumes a set start and end point.
Qutsemnie Caldari Deep Core Mining Inc.	Posted - 2006.09.09 21:13:00 - [34] Hmm despite the argument i spent a sec day dreaming when someone said you would make 200 to 300 million for a "fast solution" patent, ie P time, on the traveling salesman problem. First some background. There is NP and there is NP-Complete. The complete on the end refers to the fact that the problem has been shown to be the same as 1000s of other NP-Complete problems and if anyone of them are solved in P time then they are all solved in P-time. I couldnt patent it. Thats just to big. You arnt talking about changing one aspect of human societies ability to solve problems you are talking about revolutionizing human problem solving. I would have to go with the "belongs to humanity" approach and be content to be listed with famous figures of history that changed humanity with a thought. I would also be scared of getting assassinated if I didnt spread out the knowledge as fast as possible... Now for some background. NP stands for non-detirminstically polynomial unless my memory has failed. And beyond that NP-Complete refers to a family of problems that are all the same problem in desguise. But what is vexing about the NP stature is that it doesnt mean "not polynomial" it means "hasnt been shown to be not polynomial". And the most likely thing people expect to be proved is that all the NP-Complete problems will eventually be shown to be not polynomial. But currently years and years have gone by and nobody has made solid inroads on showing the NP-complete problems arnt polynomial. So in peoples magical fantasies they retain hope that NP-Complete could still be P problems. I mean you can see how much math is the NP-Complete. http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html http://en.wikipedia.org/wiki/List_of_NP-complete_problems Its important to emphasis that those are all the same problem in different forms. They all have been shown to translate into atleast one other from the same list. So if anyone of them go down then they are all solved. Not the least of which is: Non-trivial greatest common divisor Which is directly related to how military and commericial and private entities encrypt information. So thats where the NP-Complete gets most of its fascination. Not from its NP status but rather that so much human knowledge is lumped together in an ambigious state. Now beyond that there is NP. But NP is usually a problem waiting for some work. NP problems either have been show to not be in the complete set (ie they are shown to not translate into those other) or they are waiting for someone to show they are in the complete set by showing how they map onto one of the known complete problems. Typically someone with a phd in computer science says stuff like "its NP and I think it could be complete". That for most people is a warning that before you bet the ranch on solving it you should prolly check to see if you can map it to complete. Also every once and a while an NP problem gets shown to be P and those usually impressive people. Now i just read wiki after writing this and it says that if NP-Complete is P then all NP problems are P. Doesnt contradict anything I said but i was unaware of that fact =) As for eves efficiency. Ehhh popular games arnt known for spending weeks and weeks working out the fastest way to handle this =) Someone raised the idea of navigation software. First navigation software has a somewhat easier problem. Why? Heuristics. By roads how close you are to something is a pretty god damn good predicter of whether or not you are path closer to something. In eve that is NOT TRUE. That heuristic would fail. In eve you can be in the closest star system to something and have to go 6 jumps around to get to it. And worse if you are talking about weighting around safety then euclidean distance is about worthless sense people are unhappy with routes through low sec when a high sec route is available. Its... oops out of space. end of day dream
Qutsemnie Caldari Deep Core Mining Inc.	Posted - 2006.09.09 21:18:00 - [35] oh two more seconds of day dream. If you were trying to make money off a P solution to NP-Complete problems you wouldnt patent it. We have learned from encryption that the best algos arnt patented because by law you have to reveal it to patent it.
Plutoinum German Cyberdome Corp Veritas Immortalis	Posted - 2006.09.09 22:59:00 - [36] I'm sure you could use some charactericstics of the map to your advantage and use some precomputed values e.g. that all edges in this graph have the weight 1 and that there is a hierarchy like constellation, region etc., quite low amount of inter-region jumps etc. And if this wasn't enough to get the optimum solution for the waypoint optimizer in reasonable time, you should at least find a good solution quite fast ( O(n¦) or less ). I mean, if you do it manually, you can't guarantee that you always find the best solution for a large number of waypoints. You don't solve the TSP magically fast in your head, but you use some knowledge about the graph, like the map layout, to find a good solution. (Btw even quantum computers can't solve NP-complete problems like the TSP in polynomial time. A few years ago I had to give a seminar lecture about complexity theory in quantum computing and this is one of the few things I remember. Quite interesting. Ok, not for everyone maybe. )
Gungankllr Caldari Celestial Horizon Corp. Ascendant Frontier	Posted - 2006.09.09 23:03:00 - [37] Ask Daniel Jackson for the solution. No, the other one. Hidden in this signature is a secret message. I like pie.
Raquel Smith Ferengi Commerce Authority	Posted - 2006.09.10 00:10:00 - [38] Originally by: Qutsemnie In eve that is NOT TRUE. That heuristic would fail. In eve you can be in the closest star system to something and have to go 6 jumps around to get to it. And worse if you are talking about weighting around safety then euclidean distance is about worthless sense people are unhappy with routes through low sec when a high sec route is available. That's the problem I ran into with my algorithm. The simple spatial distance is a good indicator but that's it. For example I ran a path from the far south to the far north and my algorithm deviated from Eve's in that mine took a different route at a different system. For 25 jumps it was identical but at WH-JCA where Eve would go to W6VP-Y mine went to Q-CAB2, which is spatially closer but more jumps. Very strictly speaking the simple spatial heuristic works, just not very well. I plan on implementing an optimisation for my algorithm which will try and make the path a series of smaller jumps inside the same region (it's quite good at those). Maybe I'll make a post in the game mechanics forum about it.
Ezra Gallente Calista Industries	Posted - 2006.09.10 00:19:00 - [39] Originally by: Lazuran 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 ;-). Not only is it solvable by Dijkstra's, but the autopilot routefinder WAS solved by Dijkstra's. It probably still is, as with EVE's relatively small dataset, something like A* probably isn't much of an improvement. FYI, Dijkstra's algorithm, if not ended early, finds the shortest path from a given starting point to every other point in a graph. So the client only needs to run it once when you request one route from a given system to provide routes to any other system easily. From Redundancy's description, this is what CCP does, and it happens to coincide with what a friend who ran CCP's compiled Python bytecode through decompyle told me about the AP system before he quit the game. (In fact, he said that decompyle even spat out the comments in the code, and the autopilot code was straight out of ActiveState's Python Cookbook back in 2004 when he did this. No clue what it is like now.) ------------ Ezra Cornell pe0n, Calista Industries
Kweel Nakashyn Minmatar Aeden Tau Ceti Federation	Posted - 2006.10.20 23:01:00 - [40] Originally by: Lazuran 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. I like the "some serial" part... Why do you think GPS are soooooooo exepensive now ? Because hardware suxx and evil america use some zomgee$e licence on it ? High frequency/energy signals are NOT deciphered by slow chips that, btw, are designed to compute image theory used to en/decypher signals (About image apps, i won't teach you anything but look closer to your gpu temperature in your 400W personal computer, or try to phone my mother (who can hang you more than 3 hour on the phone) with your cell phone that is "just a mic afterall, with a little speaker that put 'some 1-dimentional data' in 'some serial'"). Transmission chips and those that encepher/decypher signal in modern electronic stuff are really underestimate in your informatic point of vue... Why do you think 80's battery could handle 10 hour of pacman in this electronic game and only 1 hour in modern cell phones ? Because of the battery themself ? Did you try to put game-n watch batteries in your cellphone ? You try to explain things from an informatic point of view, I speak from an electronic point of view, i think we can't understand as we are speaking different languages :) An ARM is a gameboy advance cpu by the way. It is not really the definition of a slow chip in my book :). Simulating an arm on a 400mhz pentium is a very bad idea. These chip I speak about are especially phone chip. They clock @ 10 GHz. Your CPU try to acheive 3.2MHz, think twice about it, that is not low-power :) Now GPS chips I can't tell really well, but... hmm... Is it in the 15/17GHz ? "Why my cpu clock @ 3 MHz and my phone clock @ 10 Ghz ? I want cpu clock at 10 GHz !" : if you can afford your electricity bill, alimentation and asking mister Intel/AMD/Motorola to stop using Silicium and start to rebuy all their producting enginery to switch to AsGa, go on... I won't :) ("what ? $20k the new pentium 12 ? wtf ?" :) )

Eilie Minmatar	Posted - 2006.10.20 23:03:00 - [41] Necro FTL!
Kweel Nakashyn Minmatar Aeden Tau Ceti Federation	Posted - 2006.10.20 23:14:00 - [42] Originally by: Qutsemnie (...) I wish I'd be better at both math, informatics and english to understand at 100% what you said :)
Kweel Nakashyn Minmatar Aeden Tau Ceti Federation	Posted - 2006.10.20 23:22:00 - [43] Edited by: Kweel Nakashyn on 20/10/2006 23:23:24 Originally by: Eilie Necro FTL! Mmm yes, I am doing necro atm, sorry for all :) Just discovered the magic "reread my stuff" button (I still miss the "put my cahracter head on the avatar" button, but i'll find it out) and missed a lot of interesting answers... I'll stop that, but here bounced a thread that was really cool :)
Futuri	Posted - 2006.10.20 23:25:00 - [44] Edited by: Futuri on 20/10/2006 23:26:14 Edited by: Futuri on 20/10/2006 23:25:28 GPS systems only have to find the shortest route between points A and B. It's a very easy problem that can be solved even on a slow computer. Waypoint optimization is the "travelling salesman" problem, which is NP complete. You have to find the shortest route that starts in point A and visits all other waypoints. But, there are very efficient approximate solutions (i.e. finding the shortest route is NP-hard but finding a route which is slightly longer than the shortest one is not). I think EVE uses the mindless algorithm "try every possible route and see which one is the shortest", which is obviously very slow. Please fix the waypoint optimizer. Edit - sorry for the necro :P
evistin Multiverse Corporation	Posted - 2006.10.21 00:05:00 - [45] Originally by: Futuri Please fix the waypoint optimizer. Honsetly, if you can fix this problem, the NP complete problem, you will be forever marked a maths God. This is how tough it is. I am suggesting using more metric in the caculation, such as queue lenght, system traffic, node load,etc,etc...via the DUAL alogrithem. ohh Nerco FTL. :P ----------- Management and Leadership û The Eve-online Guide
Futuri	Posted - 2006.10.21 00:20:00 - [46] Originally by: evistin Originally by: Futuri Please fix the waypoint optimizer. Honsetly, if you can fix this problem, the NP complete problem, you will be forever marked a maths God. This is how tough it is. I am suggesting using more metric in the caculation, such as queue lenght, system traffic, node load,etc,etc...via the DUAL alogrithem. ohh Nerco FTL. :P As I've already said, for all practical purposes this problem is already "fixed". AFAIK you can solve 1000+ waypoint TSPs on PCs with reasonable accuracy (a couple percent within the optimal).
Xenofur Di-Tron Heavy Industries	Posted - 2006.10.21 02:07:00 - [47] easiest solution: add a route cache server... face it: MANY routes that people are going to fly will almost always already be used by someone else. if there is some way to statically display the routes on the screen there is also one to store them. on route set, have client check server if it was already calc'd once, if so, dl, if not, calc new, then upload and save. additionally add a dinky little ghz box or something that continuously calculates new routes to help populate the cache more.
Futuri	Posted - 2006.10.21 02:31:00 - [48] Originally by: Xenofur easiest solution: add a route cache server... face it: MANY routes that people are going to fly will almost always already be used by someone else. if there is some way to statically display the routes on the screen there is also one to store them. on route set, have client check server if it was already calc'd once, if so, dl, if not, calc new, then upload and save. additionally add a dinky little ghz box or something that continuously calculates new routes to help populate the cache more. That suggestion is probably ~10x harder to implement than a proper algorithm on the client.
Taedrin Gallente Mercatoris Technologies	Posted - 2006.10.21 03:43:00 - [49] Necros ftl... Heuristic algorithms ftw! The Traveling Salesman Problem is an interesting one. It's very hard for computers to do it. Yet for some reason, it's very easy for a human to do it. One of the problems is that a computer usually gets hung up with finding the best solution. A human is usually just fine with finding one that is merely "good". Throw into there the fact that we also have a theoretetical peak computational performance of something like 10^16MHz. Anyways, there are a number of "heuristic algorithms" out there which attempt to find a "good" TSP solution in a reasonably small amount of time. Granted, since the algorithm is heuristic in nature, solutions are neither guaranteed to be good, nor be found quickly. These are probably what GPS products use. Now, these heuristic algorithms are awfully complicated to understand and implement. The "naive" implementation which searches for the shortest path that touches all waypoints, though incredibly computationally complex, is realitively straightforward to code. A simple matter of applying brute force, really. CCP probably decided that their time would be better spent on working on the game instead of spending a month nailing down a good implementation of a heuristic algorithm.
Mithrantir Ob'lontra Gallente Ixion Defence Systems The Cyrene Initiative	Posted - 2006.10.21 03:54:00 - [50] Originally by: Shiraz Merlot 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! QFT. Dikjstra's algorithm is used for calcullating the shortest feasible distance between 2 points and not for x number points. In order to achieve that with Dikjstra you have to run it everytime you reach a waypoint, and that would not be optimizing the route frankly. ------- Nobody can be exactly like me. Even I have trouble doing it.

Dred'Pirate Jesus Imperial Academy	Posted - 2006.10.21 04:06:00 - [51] Originally by: This Thread Nerd Speak I love it when Nerds quarrel.. its so damn cute.. [2:02:08] Dred'Pirate Jesus > I'm Mexican you dolt.. It's pronouced "hey zeus" not "gee zus"
FireFoxx80 Caldari E X O D U S Imperial Republic Of the North	Posted - 2006.10.21 09:17:00 - [52] heh. nerds. But in all seriousness. A math problem for you all (if you will). TSP in two guises: 1) Visiting all empire regions. 2) Visiting allregions. Think of it as a Eve X-prize; only the reward is 1m ISK, not 1m USD. And the above posters are correct Dijikistra (sp?) and A* are fine for finding efficient paths between two points; but find the most efficient path for n-nodes and you are screwed. What I do the rest of the time - Vote for a Jita bypass!
Roshan longshot Gallente Order of the Arrow	Posted - 2006.10.21 09:46:00 - [53] just plain old fashioned why would anyone want to try and figure this out? Gawd I have a headache now... Free-form Professions, ensure no limetations on professions. Be a trader, fighter, industialist, researcher, hunter *pirate* or mixture of them all. [i]As read from the original box.
James Lyrus Lyrus Associates Interstellar Starbase Syndicate	Posted - 2006.10.21 10:49:00 - [54] Originally by: Roshan longshot just plain old fashioned why would anyone want to try and figure this out? Gawd I have a headache now... Because if you solve the 'perfect route' algorithm, such that it's not NP complete the you suddenly become very rich and famous.
Azure Eyes	Posted - 2006.10.21 11:12:00 - [55] Edited by: Azure Eyes on 21/10/2006 11:13:13 Given that the universe we live in small and discrete, i.e. there's only about five thousand possible places to be and those places have static and well defined connections, there's a roundabout way to solve this. There exist algorithms that solve so-called All-Pairs path finding. That means that upon completion, the algorithm leaves you with optimal routes from every point in the graph to every other point in the graph. This algorithm must be run once each time the map changes, and the results can be disseminated to the clients as a large lookup table. Whenever route planning is to be done, the client simply selects a solution from the table. Elegant, right? On to optimization. In order to avoid talking about complexity classes and the different between problems that take take a century to solve vs. problems that are deemed hard, let's just look at the original post. He wanted an optimal path from a single source, through 13 different positions. That means that we need to perform 13 route planning jobs (from source to the first waypoint, first waypoint to the second waypoint, etc.) for every possible permutation of the 13 waypoints. How many ways can one sort 13 things? 13! of course, i.e. 131211...1 ways = 6.227.020.800 possible solutions for a grand total of 80.951.270.400 route planning actions in the most naive implementation. We can reduce that to just over six billion if we use some sort of caching, like the All-Pairs suggested above. If we want to reduce it further, we need to use fancy-pants solution-pruning, elite-solutions, meta-heuristics, blah, blah, blah. Frankly, I suspect CCP has its hands full with laggy databases, content hungry consumers, balancing issues and a host of other things to want to put much effort into something that works for the majority of uses. Now, in conclusion, route planning is simple, optimal route planning with multiple waypoints is not simple. That's why the Eve autopilot can find a way from the far south to the far north in seconds, but struggle once you press the optimize button. My advice is to lay off the optimization. And finally, necromancy wins the day :)
FireFoxx80 Caldari E X O D U S Imperial Republic Of the North	Posted - 2006.10.21 12:13:00 - [56] Well, if I wanted to check the market in 13 diff regions (forgetting alts for the moment), what's the msot efficient route? What I do the rest of the time - Vote for a Jita bypass!
KH Quickshot	Posted - 2006.10.21 12:23:00 - [57] its amazing, im studing theses algorthims, and i never thought eve would of used them before now, but ive just relised, lol
Azure Eyes	Posted - 2006.10.21 12:33:00 - [58] Originally by: FireFoxx80 Well, if I wanted to check the market in 13 diff regions (forgetting alts for the moment), what's the msot efficient route? Look at the map and plot a course yourself. :) Computers are not always for the win.
Rekless Revenge Deep Core Mining Inc.	Posted - 2006.10.21 12:49:00 - [59] A* ftw http://theory.stanford.edu/~amitp/GameProgramming/
Professional Troll	Posted - 2006.10.21 13:15:00 - [60] Originally by: Azure Eyes Edited by: Azure Eyes on 21/10/2006 11:13:13 Given that the universe we live in small and discrete, i.e. there's only about five thousand possible places to be and those places have static and well defined connections, there's a roundabout way to solve this. There exist algorithms that solve so-called All-Pairs path finding. That means that upon completion, the algorithm leaves you with optimal routes from every point in the graph to every other point in the graph. This algorithm must be run once each time the map changes, and the results can be disseminated to the clients as a large lookup table. Whenever route planning is to be done, the client simply selects a solution from the table. Elegant, right? Except that would give you a table with 5000^4999 (simplified, approximately 1.416+10^18,491) rows in order to get the shortest path from each of the 5,000 systems to all 4,999 other systems. In other words there is not enough storage space on all computers all around the world combined to store a look-up table that big. Look at me! Look at me! \|A\|T\|T\|E\|N\|T\|I\|O\|N\|-\|W\|H\|O\|R\|I\|N\|G\| My Anti-drug.

Azure Eyes	Posted - 2006.10.21 13:41:00 - [61] Originally by: Professional Troll Except that would give you a table with 5000^4999 (simplified, approximately 1.416+10^18,491) rows in order to get the shortest path from each of the 5,000 systems to all 4,999 other systems. In other words there is not enough storage space on all computers all around the world combined to store a look-up table that big. Sure? Remember if we have a route from A to B we don't need a route from B to A. The way I figure, you'd need to calculate the number of possible unordered combinations of two elements from a set of five thousand. That's 5000 choose 2 = 12 497 500, which isn't that large a table... Mind you, I'm not actually proposing CCP does it this way, I was merely musing at alternatives.
Rorix Whitecloud Caldari Eve Defence Force Ascendant Frontier	Posted - 2006.10.21 16:19:00 - [62] Originally by: Professional Troll Originally by: Azure Eyes Edited by: Azure Eyes on 21/10/2006 11:13:13 Given that the universe we live in small and discrete, i.e. there's only about five thousand possible places to be and those places have static and well defined connections, there's a roundabout way to solve this. There exist algorithms that solve so-called All-Pairs path finding. That means that upon completion, the algorithm leaves you with optimal routes from every point in the graph to every other point in the graph. This algorithm must be run once each time the map changes, and the results can be disseminated to the clients as a large lookup table. Whenever route planning is to be done, the client simply selects a solution from the table. Elegant, right? Except that would give you a table with 5000^4999 (simplified, approximately 1.416+10^18,491) rows in order to get the shortest path from each of the 5,000 systems to all 4,999 other systems. In other words there is not enough storage space on all computers all around the world combined to store a look-up table that big. Well, all that would do is give you the optimal route from point A to point B... what if you are at Point A, and you're going to B, C, D, E, but not necessarly in order? Point B might be closer to A than any other point, so your auto pilot will select A, B, etc etc... while in reality, the shortest path for the ENTIRE route would be, for example, A, C, E, B, D? This is also why the Dijkstra's algorithem probably wont work for this situation. Sig pic too old... and lost the template during reformatting (doh!) Goal: To blaster-fit every Caldari ship that has a turret slot. ~I don't remember. That's the second thing they teach you.
FireFoxx80 Caldari E X O D U S Imperial Republic Of the North	Posted - 2006.10.23 08:42:00 - [63] You can make it easier by ignoring all systems that don't have a station. What I do the rest of the time - Vote for a Jita bypass!
DeODokktor Caldari Dark Templars The Fonz Presidium	Posted - 2006.10.23 09:50:00 - [64] Edited by: DeODokktor on 23/10/2006 09:50:57 all you guy's who say it's the traveling salesman issue well, that's silly ccp just need to allocate some time for a new search to be coded, and probably somehow get it out of python. I used to play a game that had 20,000 systems each system might have from 1 -> 6 warps in/out with some of those being non-return warps. to calculate the most efficent paths I could do probably 300 a second. I dont know how indepth the path calulator is. if it try's to figgure total warp distance and cap usage to find a time based travel time (vs a jump based travel time) then I can see it taking a lot more cpu. It just needs some code luvvin and no effin descriptions of "traveling salesman" or other crap.
FireFoxx80 Caldari E X O D U S Imperial Republic Of the North	Posted - 2006.10.23 10:17:00 - [65] Its two problems though: Route from A > B: Is simply A* or Dijikstra (depending on whether you are weighting distance+security, or just distance). Which yes, depending on how complex it is, runs fairly quickly (although setting up routes like A > B but try to stay as close as poss to 0.5; tends to slow things down) TSP relates to multiple systems, with no fixed order. So the most efficient route between systems A, B, C, D, E. What I do the rest of the time - Vote for a Jita bypass!
Shiraz Merlot Octavian Vanguard RAZOR Alliance	Posted - 2006.10.23 10:34:00 - [66] Originally by: DeODokktor It just needs some code luvvin and no effin descriptions of "traveling salesman" or other crap. I know a manager like you.
Spanker	Posted - 2006.10.23 10:38:00 - [67] This is very cool stuff. Where can I download a data set of the eve map? - Shpank
Shiraz Merlot Octavian Vanguard RAZOR Alliance	Posted - 2006.10.23 10:41:00 - [68] Originally by: evistin Honsetly, if you can fix this problem, the NP complete problem, you will be forever marked a maths God. This is how tough it is. I am suggesting using more metric in the caculation, such as queue lenght, system traffic, node load,etc,etc...via the DUAL alogrithem. DUAL is patented and afaik is licensed only to Cisco for use in their EIGRP routing protocol. The inventor of DUAL (Prof. J.J. Garcia-Luna-Aceves, now at UCSC) has (along with his grad students) in recent years done some amazing research work with ad-hoc routing and multicasting. None of it, alas, geared towards solving a high-order TS problem. /sm
Shiraz Merlot Octavian Vanguard RAZOR Alliance	Posted - 2006.10.23 13:22:00 - [69] Originally by: Spanker This is very cool stuff. Where can I download a data set of the eve map? Linky
Jessica May	Posted - 2006.10.23 14:12:00 - [70] Originally by: Kweel Nakashyn Edited by: Kweel Nakashyn on 09/09/2006 09:52:03 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. Also AsGA Asics are no way near of any of my definitions of low-energy CPU. 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 :) 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 :) Originally by: Lazuran (...) But hey, with your arrogance and ignorance, you made my day. ;-) You're welcome in our club :) So a Laptop running a game with Microsoft Auto Route in the background with a USB Sat Nav arial wouldn't be able to compute a route? (Think caurefully, you might be talking to someone who has tried this).

Kweel Nakashyn Minmatar Aeden Tau Ceti Federation	Posted - 2006.10.26 17:39:00 - [71] Edited by: Kweel Nakashyn on 26/10/2006 17:39:54 Originally by: Jessica May So a Laptop running a game with Microsoft Auto Route in the background with a USB Sat Nav arial wouldn't be able to compute a route? (Think caurefully, you might be talking to someone who has tried this). Zomgeeze Necro (sorry again) Why not ? My purpose is to say GPS's chips are not game'n watch's, not to say GPS's chip are like modern mainframes's racks. I underlined that the device that decypher the signal isn't made by a game'n watch, and the fact that you won't catch flies with a butterfly net (catching 15 GHz waves with a silicon chip that pulse @ 3.5 GHz : there's a chip in your usb thingy). Btw, usb is not in my book of low-power devices :) If you have this device, please monitor the CPU/GPU activity while only computing/uploadinbg gps data, I would be curious if it's all computed on your usb or not.


Pages: 1 2 3 :: [one 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.