open All Channels
seplocked EVE General Discussion
blankseplocked So last night... I KILLED EVE.
 
This thread is older than 90 days and has been locked due to inactivity.


 
Pages: 1 [2]

Author Topic

Geormike Deninard
Posted - 2011.08.04 14:47:00 - [31]
 

Welcome to the world of powers and columns.

Kijo Rikki
Caldari
Point of No Return
Waterboard
Posted - 2011.08.04 15:13:00 - [32]
 

Hi. Mathematical layman and theoretical programmer here.

Assuming not all waypoints have multiple route choices (which is very likely I would think), would a 30 point optimization necessarily be that difficult? Is there not a programming trick to eliminate unneeded calculations?


Geormike Deninard
Posted - 2011.08.04 15:22:00 - [33]
 

Originally by: Kijo Rikki
Hi. Mathematical layman and theoretical programmer here.

Assuming not all waypoints have multiple route choices (which is very likely I would think), would a 30 point optimization necessarily be that difficult? Is there not a programming trick to eliminate unneeded calculations?




Nope, the computer needs to run ALL possible combinations in order to find the shortest one.

Ay Liz
Sacred Templars
RED.OverLord
Posted - 2011.08.04 15:23:00 - [34]
 

I just attempted to crash dotlan doing this but it refuses to optimize more than 10 waypoints Neutral

Smagd
Encina Technologies
Namtz' aar K'in
Posted - 2011.08.04 15:25:00 - [35]
 

Originally by: Kijo Rikki
Hi. Mathematical layman and theoretical programmer here.

Assuming not all waypoints have multiple route choices (which is very likely I would think), would a 30 point optimization necessarily be that difficult? Is there not a programming trick to eliminate unneeded calculations?




No. That's why this class of problems is called NP hard.

A human brain is remarkably good at approximating an optimal route, by intuitively eliminating overly long routes e. g. by pre-sorting by regions, but doing one region after the other is not the shortest route.

dexington
Caldari
Baconoration
Posted - 2011.08.04 16:03:00 - [36]
 

Originally by: Kijo Rikki
Assuming not all waypoints have multiple route choices (which is very likely I would think), would a 30 point optimization necessarily be that difficult? Is there not a programming trick to eliminate unneeded calculations?


The problem relates to the P versus PN problem, which by many is seen as one of the most important questions in mathematics. The prize for solving the problem is 1.000.000 dollars, so if you have any good ideas you should cash in :)

Aineko Macx
Posted - 2011.08.04 17:34:00 - [37]
 

I found that the largest number of waypoints the autopilot is able to optimize in a decent amount of time is 12. IIRC it takes like 20 seconds.

For longer routes an A* or genetic algorithm would be a good choice.

Marchocias
Posted - 2011.08.04 17:52:00 - [38]
 

Originally by: dexington
Originally by: Kijo Rikki
Assuming not all waypoints have multiple route choices (which is very likely I would think), would a 30 point optimization necessarily be that difficult? Is there not a programming trick to eliminate unneeded calculations?


The problem relates to the P versus PN problem, which by many is seen as one of the most important questions in mathematics. The prize for solving the problem is 1.000.000 dollars, so if you have any good ideas you should cash in :)


Whilst its true that this problem is computationally intractable for a large input graph, there are techniques that can be applied which will quickly find a good approximation to the shortest route, which CCP could implement in the event of someone picking >12 destinations.

Uuali
Posted - 2011.08.04 18:36:00 - [39]
 

Edited by: Uuali on 04/08/2011 18:36:58
Must I quote Han Solo here or has somebody already done that? lol.

Honey, it ain't hard 'til it's NP Hard.

Louis deGuerre
Gallente
Malevolence.
Posted - 2011.08.04 19:34:00 - [40]
 

Originally by: Uuali
Honey, it ain't hard 'til it's NP Hard.


Just thinking for a minute I can think of a few tricks to cut down Breadth-first search space by 80-90 %. Of course, if you want the exact 100% sure best solution there is not really an alternative. Still, searching from both directions will take a large chunk out of that, unless you search from one end of the galaxy to the other one.
Of course, they will have implemented something a lot smarter than this.

But I'm just rambling because I wanna use that quote Razz

Mongo Travler
Posted - 2011.08.04 20:24:00 - [41]
 

You wouldn't want to use a breadth first search algorithm to generate a spanning tree as there is no guarantee that the solution between any two vertices on the tree is optimal. You would be better off calculating each individual route using something like Dijkstra's algorithm to find the optimal solution between each individual pairs.

Once you have calculated these routes for all combinations (should be 450 solutions) you can check the routes to see if any of them include another waypoint i.e. the route between A and B goes through C you can remove the AB route as it is effectively the AC and CB route. After that is complete you then run into the traveling salesman problem.

If your lucky there may be one or more bottleneck systems i.e. if you remove a waypoint you end up with two or more separate graphs then you can optimize each individual piece separately to speed things along.

anyways just some thoughts on my lunch break

Jack Tronic
Posted - 2011.08.04 21:35:00 - [42]
 

Edited by: Jack Tronic on 04/08/2011 21:35:13
Originally by: Mongo Travler
You wouldn't want to use a breadth first search algorithm to generate a spanning tree as there is no guarantee that the solution between any two vertices on the tree is optimal. You would be better off calculating each individual route using something like Dijkstra's algorithm to find the optimal solution between each individual pairs.

Once you have calculated these routes for all combinations (should be 450 solutions) you can check the routes to see if any of them include another waypoint i.e. the route between A and B goes through C you can remove the AB route as it is effectively the AC and CB route. After that is complete you then run into the traveling salesman problem.

If your lucky there may be one or more bottleneck systems i.e. if you remove a waypoint you end up with two or more separate graphs then you can optimize each individual piece separately to speed things along.

anyways just some thoughts on my lunch break


Slight issue with your logic, people may set waypoints to go past a system but through it, but then double back afterwards as part of say their hauling trip, so rearranging the routes will break this feature.

Otherwise Dijkstra'a algorithim between each pair of waypoints should already be efficient. Not quite sure what bastardized logic CCP is using to cause it to hang.

Danico Buchald
Caldari
Posted - 2011.08.04 22:59:00 - [43]
 

Originally by: Jack Tronic


Slight issue with your logic, people may set waypoints to go past a system but through it, but then double back afterwards as part of say their hauling trip, so rearranging the routes will break this feature.




Uhh you mean like optimizing your route does now? It doesn't preserve waypoint order, that's kind of the point.

Mongo Travler
Posted - 2011.08.05 01:14:00 - [44]
 

Edited by: Mongo Travler on 05/08/2011 03:28:12
Edited by: Mongo Travler on 05/08/2011 03:24:55
You still run into the same problem. If you have a fixed begin and end point then you are still looking for a shortest route amongst trillions of possible solutions.

Whats causing the slowness is that once you have your connected graph you have to calculate the most efficient method of going from the start to the end system (whether or not you already "went" to the end point). Even if you fixed the end point Eve still has to compute the most efficient route of 29! routes. There are algorithms that can filter out some of these but you still have to sift through lots possible routes.

There may be a faster way to do it but I don't do much programming. Either way I'm not surprised that it takes a long time to crunch the numbers.

edit: My mistake, you don't actually need need a Hamiltonian path but it would be nice to not cross your path along the way. Still an incredibly difficult problem to solve - even for computers.

Methesda
Posted - 2011.08.05 01:40:00 - [45]
 

Holy fv[# there is a lot of students in here.

dexington
Caldari
Baconoration
Posted - 2011.08.05 02:19:00 - [46]
 

Originally by: Mongo Travler
You still run into the same probelm. If you have a fixed begin and end point then you are really looking for a hamiltonian path which again is an np hard problem.


The only problem is that you can't be sure that a hamiltonian path exists in a given route, when it's not there it's going to be a long wait for the negative result.


Pages: 1 [2]

This thread is older than 90 days and has been locked due to inactivity.


 


The new forums are live

Please adjust your bookmarks to https://forums.eveonline.com

These forums are archived and read-only