You are invited to Log in or Register a free Frihost Account!

# The Traveling Salesman Problem (TSP)

The-Nisk
This is a famous optimization problem in computer science and related fields (mathematics etc).
It is based on finding a solution which consumes the least resources. The problem has many forms, but the most common example is that of a traveling salesman, hence the name obviously. The problem goes like this:

We have a salesman which travels between cities to make a living by selling stuff, and we have a number of cities the salesman needs to visit. We need to find a route that goes through each city once (and only once) and returns the salesman back home at the end of the day. What we're really interested in is finding the shortest possible route (this has obvious real life implications such as saving money on petrol, time etc.).

Now while I have the basics of the problem and I can think up an algorithm for solving it, I'm just wondering are there ways to solve this problem aside from brute-force? I'm intending to solve this problem this week, should I have the time to. But obviously I'm interested in other solutions

P.S. if you feel want, you can paste code
ocalhoun
You might work something out with something like this:

 Code: WHILE [THERE ARE STILL UNCLAIMED POINTS]     (AN UNCLAIMED POINT IS ONE THAT IS CONNECTED TO LESS THAN TWO OTHERS)     SELECT THE CLOSEST TWO UNCLAIMED POINTS WITHOUT A LINE IN BETWEEN THEM     (CLOSEST TO EACH OTHER, NOT TO YOU)     MAKE A LINE BETWEEN THEM

Then, use this result as a baseline to be optimized with other strategies/brute force.

*edit*
A quick, imprecise, on-paper run-through of this method shows that it works pretty well, but leaves outlying points unvisited until the end (and it might skip them altogether).
If you followed this algorithm up with one designed to integrate these outlying leftovers into the existing path, you'd have a pretty good system.
... It wouldn't always come up with the absolute best route, but it would give you a good route every time, while using substantially less computing power to do so.
Bikerman
Here's the 'greedy' algorithm
Input
* Number of cities n
* Cost of traveling between the cities.
* c (i, j) i, j = 1, . . , n.
Output
* Vector of cities and total cost.
Main Steps
1. Initialization
c← 0
Cost ← 0
visits ← 0
e = 1 /* pointer of the visited city */
2. For 1 ≤ r ≤ n
Do {
Choose pointer j with minimum = c (e, j) = min{c (e, k); visits (k) = 0 and 1 ≤ k ≤ n }
cost ← cost + minimum - cost
e = j
3. C(r) ← j
C(n) = 1
cost = cost + c (e, 1)

Note that this doesn't necessarily give the best answer
Flakky
What is important to know is that the path can never cross another path. Also the cost is quite valuable. You always have a brute force method but the cost can make an heuristic. Making calculation much faster. Though I don't think this needs to be optimized unless a computer needs to compute this in real time at 25fps

1) So foreach city calculate cost for the next city, that one is important.
2) ????
3) The path with the lowest cost is the answer

Sorry for so brief, it's late and I actually need to go to bed xD
_AVG_
This is one of the famous Graph Theory problems.

I've been completely out of touch with Graph Theory for a few months now but it's nice to revisit it:
- I think you need to use one of the algorithms : Prim or Kruskal (or something - I've forgotten)
- But for certain, you need to find the least weighted Hamiltonian Cycle over the given graph : a brute force method (for which you could write a program) involves finding all the Hamiltonian cycles starting and finishing at the same vertex and then weigh each of them ; the minimum of all the weights will be the answer
ankur2010
Great...That was a good move.
I love the algorithm...and i think its getting us to the required result...
Flakky
Here is what I found on gmc (game maker community, for Game Maker):
 Code: 1.  Have nodes calculate a list of all the distances between other nodes.  Set all pheromones to 0. 2.  Place an ant on x node.  Have him initialize a visited list, and put the current node in it.  Set the total-distance to 0 and the minimum distance to 100000. 3.  While the size of the visited list is less than the number of nodes...   4.  Look at distances to all other nodes and strength of pheromones.  Manipulate these (with random(y) factored in) and choose a best-fit node.   5.  Move to the best fit node, update the totaldistance and visited list. 6.  If the size of visited list is equal to number of nodes   7.  Move to start node, update visited and totaldistance.   8.  If the totaldistance travelled is less than the minimum distance, then lay z pheromones around the path we just took. 9.  Repeat steps 3-8 until very little change in improvement occurs.

or how this guy coded this:
 Code: var best,bestdis,i,cur,nxt,rand; bestdis=1000 for(i=0 i