Pages: 1 [2] :: one page |
|
Author |
Thread Statistics | Show CCP posts - 2 post(s) |
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 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. ________________________ CCP: Where fixing bugs is a luxury, not an obligation. |
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. ---- Will 2011-06-24 go down as the day CCP stood still, or the day the dream died? |
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. Imperial 0rder
|
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
|
|
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]
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.
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.
|
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] :: one page |
First page | Previous page | Next page | Last page |