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 
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 presorting 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 Breadthfirst search space by 8090 %. 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 
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. 