finding a new route
I am trying to code a program that can find the shortest possible route for a trip.
It's like i want to visit spot A, B, C, D, E, F, G and those are all scrambled in the map. (start from point A and i want to return A at the end)
What i have is a brute force that test every route and come up with a route. However, it is very inefficient as the variables grow larger the compiler will stop running (it was around 60). Is there anyone out there that has a better idea other than brute force?
When i say the compiler stops it means it used up too much memory and it won't run.
The way i do is for example
from A to B is 3miles B to C is 5 miles and C to D is 2 Miles etc.. (make sure the final destination is where you start)
I test every route possible since i start from A i will try B, C, D, E and for each variable is similar to tree. This method is very slow and inefficient. Anyone have a better idea?
It's like i want to visit spot A, B, C, D, E, F, G and those are all scrambled in the map. (start from point A and i want to return A at the end)
What i have is a brute force that test every route and come up with a route. However, it is very inefficient as the variables grow larger the compiler will stop running (it was around 60). Is there anyone out there that has a better idea other than brute force?
When i say the compiler stops it means it used up too much memory and it won't run.
The way i do is for example
from A to B is 3miles B to C is 5 miles and C to D is 2 Miles etc.. (make sure the final destination is where you start)
I test every route possible since i start from A i will try B, C, D, E and for each variable is similar to tree. This method is very slow and inefficient. Anyone have a better idea?
Looks similar to: http://en.wikipedia.org/wiki/Travelling_salesman_problem
Because of that:
So in short, not really...
Because of that:
| Wikipedia wrote: |
|---|
| The most direct solution would be to try all permutations (ordered combinations) and see which one is cheapest (using brute force search). The running time for this approach lies within a polynomial factor of O(n!), the factorial of the number of cities, so this solution becomes impractical even for only 20 cities. One of the earliest applications of dynamic programming is the Held–Karp algorithm that solves the problem in time O(n22n).[13] The dynamic programming solution requires exponential space. Using inclusion–exclusion, the problem can be solved in time within a polynomial factor of 2n and polynomial space.[14] Improving these time bounds seems to be difficult. For example, it is an open problem if there exists an exact algorithm for TSP that runs in time O(1.9999n)[15] |
So in short, not really...
Topic archived. No new replies allowed.