EVE Search - Brute force travelling salesman function

All Channels

Test Server Feedback

Brute force travelling salesman function

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

Monitor this thread via RSS [?]

Pages: [1] :: one page
Author	Thread Statistics \| Show CCP posts - 0 post(s)
zoop	Posted - 2003.09.26 15:43:00 - [1] Brute force travelling salesman function? what hell this...how hell work? ---------------------------- My God, it's full of gimps
Avaton White	Posted - 2003.09.26 15:52:00 - [2] Brute Force Travelling Salesman function? What the heck is that? Looks like a direct chinese to english translation gone horribly wrong. LOL ------------------------------------------------ "The best defense is a dead opponent." - Avaton White "The very notion of adding new features to broken code is self defeating to the point of being borderline insane." - Par'Nabuk ------------------------------------------------
Finderne	Posted - 2003.09.26 16:05:00 - [3] Edited by: Finderne on 26/09/2003 16:05:33 Travelling salesman problems are pretty common comp sci assignments. The specific problem usually amounts to something like this. A salesman has to visit every city in his territory once and return home. Find the optimum route. There's a lots of variants, and of course you need to supply data. Every airline and any halfway-modern shipping company deals with logistic problems like that by using some pretty sophisticated optimization tools. So someone at CCP impletemented an algorithm that optimizes complicated (multi-waypoints) trips for you. The brute-force part means that the technique they used is not too efficient.
Beringe	Posted - 2003.09.26 16:07:00 - [4] Edited by: Beringe on 26/09/2003 16:07:54 It's an algorithm for calculating the optimal route (i.e. the shortest) between a number of set locations. In this case, used to calculate the shortest route when you need to visit a number of solarsystems. That is is "brute force" means that it is a rather simple version of the algorith. CCP warns you not to use it for more than 8 waypoints, since it is probably way to slow for that. You probably don't care about the mathematics involved, so I won't go into that. EDIT: Finderene posted at the same time. doh! ------------------------------------------- "My main griveance with the Caldari state was that once I had finished my work for them, they wanted me dead." "No, it's none of your business."
JPFAmarr	Posted - 2003.09.27 00:10:00 - [5] I haven't played with it yet but I'm guessing this feature ROCKS! For example, let's say you have to pickup minerals at several different systems. You plug them in as waypoints and the brute force optimizer gives you the shortest route to all waypoints. Awesome! Generic Corporation
Bry I'onak	Posted - 2003.09.27 01:25:00 - [6] Rest assured it would be buggy and you find yourself lost and helpless in an unknown region of space
Shauna	Posted - 2003.09.27 01:35:00 - [7] Here's a link to a page I found via google that has some info on the traveling salesman problem. TSP - click here Really solving it is pretty nasty. They probably didn't do a real TSP solution (I hope not) since Eve doesn't need to be restricted as much as the formal TSP problem is ;)
Rigsta	Posted - 2003.09.27 01:44:00 - [8] Brute force travelling salesman.... lmao, sounds like a Drunken Master-style technique XD ----------------------------------------------- My Ideas: Drones wish list and NPC crew members
Shauna	Posted - 2003.09.27 01:56:00 - [9] yeah, using "brute force" and "traveling salesman" in the same sentence is in general, a very bad idea.
Lola	Posted - 2003.09.27 11:47:00 - [10] Brute Force refers to the fact they just calculate every possible route and pick the shortest. ----------------------------------------- Sig rented by Drethen Nerevitas.
Ezra	Posted - 2003.09.28 03:57:00 - [11] Yup. Brute Force is Very Bad for large N - which is why CCP gives warnings for N>8. The computation rises (approximately) in proportion with N! - so 9 points takes 9x as long as 8, and 10 takes 10x longer than 9 (90x longer than 8). I hope the calcs are done client-side, or are throttled to use no more than a certin amount of server resources. I only wish they'd implemented the last portion of the TSP - RETURNING to your origin. :) Right now the autopilot system doesn't allow for round-trip or circular routes. What's annoying is autopilot doesn't stop at waypoints even if you have it set to do so. Otherwise this patch rocked! ------------ Ezra Cornell pe0n, Xanadu Corporation
Golgrath	Posted - 2003.09.28 05:26:00 - [12] The brute force method is the only true solution to the TSP. Other methods are only approximations.
Shauna	Posted - 2003.09.28 05:33:00 - [13] True, but there are a lot of really great heuristics out there ;) Anyways, I did notice that it will retraverse nodes and edges, so i'll just loosely consider it a TSP ... hehe. Nice option though, very much needed! Great job CCP!
Jojin	Posted - 2003.09.28 07:29:00 - [14] Nice option and very helpful. There is one difficulty I am having. The system does not seem to differentiate Destination from Waypoint and your final destination cannot be your current system. For example, if you need to end up in a specific location at the end of your journey, the optimize option will overlook this and consider everything a waypoint. Thus your final destination may be your first stop.
Jitters	Posted - 2003.09.28 08:26:00 - [15] Quote: yeah, using "brute force" and "traveling salesman" in the same sentence is in general, a very bad idea. If I may correct you here: Solving the TSP by brute force is a good idea since it's more or less the best we have for that class of problem (NP-complete problems). As Ezra noted this solution takes time corresponding to a factorial order in the number of nodes. As you say yourself there are some good heuristics out there, and a good starting point is to analyze ahead a bit which can save the traversal of a number of bad paths. The best combinations however, still only reach exponential order (again, in the number of nodes) and the method is still brute force. For more material, take a look here And to Ezra, I think you can rest assured that the calculations are client-side (if not, we'll have someone's head for it! :-) I have been wanting this feature ever since I plotted my first route. I hope the implementation goes over well and that there will be developer time set to improve the algorithm - I imagine twenty nodes should be within reach, and that would be a lot more useful compared to eight which is just ... well, convenient.
Roba	Posted - 2003.09.28 12:06:00 - [16] Ok is the calculation done client side or server side? ie, will a faster machine be able to calculate a longer route faster?
DHU InMe	Posted - 2003.09.28 14:20:00 - [17] Quote: Yup. Brute Force is Very Bad for large N - which is why CCP gives warnings for N>8. The computation rises (approximately) in proportion with N! - so 9 points takes 9x as long as 8, and 10 takes 10x longer than 9 (90x longer than 8). I hope the calcs are done client-side, or are throttled to use no more than a certin amount of server resources. I only wish they'd implemented the last portion of the TSP - RETURNING to your origin. :) Right now the autopilot system doesn't allow for round-trip or circular routes. What's annoying is autopilot doesn't stop at waypoints even if you have it set to do so. Otherwise this patch rocked! No, CCP would not overload their server uselessly. Also, since it a brute force algorith, they will probably make it better in some month when they will have corrected IMPORTANTS BUGS. Nice links (updated 20 Dec 04): BP, bugs about them. (\_/) (O.o) (> <) This is Bunny. Copy Bunny into your signature to help him on his way.
Liam Pelas	Posted - 2003.09.28 14:42:00 - [18] first, all route calculations are performed client side. Second, autopilot won't dissable at waypoints atm, so you have to watch it, and make sure you stop manualy at each stop!
Ezra	Posted - 2003.09.29 00:22:00 - [19] Quote: Nice option and very helpful. There is one difficulty I am having. The system does not seem to differentiate Destination from Waypoint and your final destination cannot be your current system. For example, if you need to end up in a specific location at the end of your journey, the optimize option will overlook this and consider everything a waypoint. Thus your final destination may be your first stop. Yup, only thing missing from the current implementation. (Other than actually STOPPING at your webpoints.) An interesting algorithm, one that will never make it into the game but might someday be implemented out-of-game (hey CCP, want to make the jump data and current routing algorithms public?) is the ability to set additional restrictions. (System A must be visited before system B and C before D, but beyond that the order should be optimized) - Would be great for running agent missions. ------------ Ezra Cornell pe0n, Xanadu Corporation

Pages: [1] :: 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.