Traveling Salesman Problem Using Convhull
Of course it is not the concorde library, can compute only one path in 2D space, very often of greater length than the one computed by professionals programs, but it is very simple and
understandable. Anyway solutions are not so bad, and I think many progresses can be made.
Starting from the convhull it is possible to find a path of length very close to the exact solution. It is just necessary to add to the convhull the others points. The adding process must be efficient so at each iteration we add the point that causes minimum growth of the path length.
The concept behind it is the minimization of the enclosing surface.
I have not calculated the mean error with exact solutions, but should be around 5-10%.
Complexity of the algorithm is O(N^2), so it is quite fast considering the complexity of the problem.
Inputs:
- x: float vector that contains x coordinates of cities/points
- y: float vector that contains y coordinates of cities/points
- showcurrentpath: 1 to activate the plot of the temporarypath, this may slow execution, and it is unadvisable for morethan 200 points.
Output:
- idVisted: contains index order of cities visited
- totdist: path length.
here is an example:
Visit my website:
http://giaccariluigi.altervista.org/blog/
For any problem,suggestion,question just contact me at:
If you find it useful, donations can be done on my website.
Download Now
Popularity: 14% [?]
Translator
By N2H Follow Us
Video Posts
-
