TSP Flaming – Quickly finds a solution of the Travelling Salesman Problem
Sponsored Link
Problem Statement
Given a map with cities locations, what is the least-cost round-trip route that visits each city exactly once and then returns to the starting city?
Observation
Size of solution space is n!, where n is number of cities. The most direct solution rapidly becomes impractical.
Simulated Annealing
Instead of using exhaustive enumeration a generic probabilistic meta-algorithm is used. In fixed amount of time it finds a good approximation to the global optimum in a large search space.
Install TSP Flaming in Ubuntu
Download .deb package from here .Install this .deb package by double clicking on it or run the following command from your terminal
sudo dpkg -i tspflaming_1.2-0~ppa1_i386.deb
Screenshot
What am I looking at?
This is quite the confusing post.
TSP is a great problem to solve and it would be good to see this generalised to 3D TSP at some point but..I can’t get this to install. I have an up to date
Ubuntu 9.10 (karmic) Kernel Linux 2.6.31-21-generic-pae GNOME 2.28.1 and the latest qt4 libraries that the Synaptic Package Manager will provide but still get installation errors…
dpkg: dependency problems prevent configuration of tspflaming:
tspflaming depends on libqtcore4 (>= 4:4.6.1); however:
Version of libqtcore4 on system is 4.5.3really4.5.2-0ubuntu1.
tspflaming depends on libqtgui4 (>= 4:4.5.3); however:
Version of libqtgui4 on system is 4.5.3really4.5.2-0ubuntu1.
dpkg: error processing tspflaming (–install):
dependency problems – leaving unconfigured
Errors were encountered while processing:
tspflaming
If I try apt-cache policy qt4-dev-tools, I get
qt4-dev-tools:
Installed: 4.5.3really4.5.2-0ubuntu1
Candidate: 4.5.3really4.5.2-0ubuntu1
Version table:
*** 4.5.3really4.5.2-0ubuntu1 0
500 http://nz.archive.ubuntu.com karmic/main Packages
100 /var/lib/dpkg/status
Do I wait for a package update, Ubuntu 10.01 to come off beta or a bug fix? Any thoughts welcome.
I think it depends on what Video Card you’re using.
Integrated Video Cards work better since they come
pre-installed.(Time=Money) And I wouldn’t use a PC that a salesman has been working on. (Unless he’s
a PC salesman). Runs with RHE, no problem.
You tile is false. You should replace find with approximate…. otherwise P=NP, knowing that TSP is NP-Complete. Beside TSP is such a nice way to introduce people to computer complexity and simulated annealing is also quite a beautiful way to overcome such complexity!