# Thread: TSP travelling salesperson problem

1. ## TSP travelling salesperson problem

Can someone please point me in the direction of a GOOD explnation for how to do these when there is a matrix given? How to figure out the tour cost?I have googled for ages but nothing is explaining what is actually the process to find a solution, can someone please explain or just point me in the direction of an explanation.

I dont understand what is being done to the matrix to arrive at the tour price?

2. Originally Posted by SydneyBristow
Can someone please point me in the direction of a GOOD explnation for how to do these when there is a matrix given? How to figure out the tour cost?I have googled for ages but nothing is explaining what is actually the process to find a solution, can someone please explain or just point me in the direction of an explanation.

I dont understand what is being done to the matrix to arrive at the tour price?
See here.

If you have five cities A, B, C, D, E, then you'll have a 5 by 5 matrix with its entries are distance between them. Travel costs are predetermined. If you find a solution in a brute force manner, there are 5! cases described by permutations.

For example,
ABCDE,
BACDE,
....

n! is a really big number for a large n, so you might need to find an approximate solution of TSP by using heuristic algorithms.

3. I read that wiki page, i still dont get it.

I need to learn to do an Approximate TSP

For example, given this matrix

A B C D E F
A ∞ 3 2 7 1 5
B 3 ∞ 5 2 3 2
C 2 5 ∞ 3 4 1
D 7 2 3 ∞ 4 3
E 1 3 4 4 ∞ 5
F 5 2 1 3 5 ∞

in what order are the vertices inserted into the algorithm (i dont understand what algorithm to be quite honest)

. Steps:
(a) T1 = A 􀀀 A
(b) T2 = A 􀀀 E 􀀀 A
(c) T3 = A 􀀀 E 􀀀 C 􀀀 A
(d) T4 = A 􀀀 E 􀀀 F 􀀀 C 􀀀 A
(e) T5 = A 􀀀 E 􀀀 B 􀀀 F 􀀀 C 􀀀 A
(f) T6 = A 􀀀 E 􀀀 D 􀀀 B 􀀀 F 􀀀 C 􀀀 A
2. Total cost is 1 + 4 + 2 + 2 + 1 + 2 = 12.

I dont know why A-A =1 and then for t2 it is A-E-A??? Why? WHY!! I feel like i am going to go insane trying to figure this out.

4. Originally Posted by SydneyBristow
I read that wiki page, i still dont get it.

I need to learn to do an Approximate TSP

For example, given this matrix

A B C D E F
A ∞ 3 2 7 1 5
B 3 ∞ 5 2 3 2
C 2 5 ∞ 3 4 1
D 7 2 3 ∞ 4 3
E 1 3 4 4 ∞ 5
F 5 2 1 3 5 ∞

in what order are the vertices inserted into the algorithm (i dont understand what algorithm to be quite honest)

. Steps:
(a) T1 = A �� A
(b) T2 = A �� E �� A
(c) T3 = A �� E �� C �� A
(d) T4 = A �� E �� F �� C �� A
(e) T5 = A �� E �� B �� F �� C �� A
(f) T6 = A �� E �� D �� B �� F �� C �� A
2. Total cost is 1 + 4 + 2 + 2 + 1 + 2 = 12.

I dont know why A-A =1 and then for t2 it is A-E-A??? Why? WHY!! I feel like i am going to go insane trying to figure this out.

I think it depends on what algorithm you use.

A B C D E F
A 0 3 2 7 1 5
B 3 0 5 2 3 2
C 2 5 0 3 4 1
D 7 2 3 0 4 3
E 1 3 4 4 0 5
F 5 2 1 3 5 0

There are 6! cases for the brute force method in your example.

For example,

The travel cost of the route for ACDFEB is

A-C : 2
C-D: 3
D-F: 3
F-E: 5
E-B : 3
B-A: 3

If you sum up the whole number, then the total cost is 19.

5. Ok here is what i dont get.

How do you decide on that route? ... why cant its just be ABCDEF, why is it ACDFEB

How do i know what the algorithm options are. This is supposed to be approximate TSP. I read the explanation but it literally sounds like gibberish.

this is the explanation:

Pick any vertex as a starting circuit C1 consisting
of 1 vertex.
• Given the k-vertex circuit Ck, k ≥ 1, find the
vertex zk not on Ck that is closest to a vertex,
call it yk , on Ck. (cost matrix C is symmetric)
• Let Ck+1 be the k+1-vertex circuit obtained by
inserting zk immediately in front of yk in Ck.
• Repeat steps 2 and 3 until a Hamilton circuit
(containing all vertices) is formed

6. Originally Posted by SydneyBristow
Ok here is what i dont get.

How do you decide on that route? ... why cant its just be ABCDEF, why is it ACDFEB

How do i know what the algorithm options are. This is supposed to be approximate TSP. I read the explanation but it literally sounds like gibberish.

this is the explanation:

Pick any vertex as a starting circuit C1 consisting
of 1 vertex.
• Given the k-vertex circuit Ck, k ≥ 1, find the
vertex zk not on Ck that is closest to a vertex,
call it yk , on Ck. (cost matrix C is symmetric)
• Let Ck+1 be the k+1-vertex circuit obtained by
inserting zk immediately in front of yk in Ck.
• Repeat steps 2 and 3 until a Hamilton circuit
(containing all vertices) is formed
Calculate cost ABCDE as I did in my previous post. Is it the same with ACDFEB? What I am saying is that the problem reduces to the permutation problem. Different permutation generates the different travel cost. Your first line seems to use the greedy algorithm. As I said, there are tons of algorithms to solve TSP problem using heuristics, and your algorithm is simply one of them.

7. ok it is sort of becoming more clear now. So using the greedy algorithm is to choose the closest point from the current point as the next point.

So if i start at A the closest is E =1
from E to B=3
B to D (or F, but alphabetically first lets say D)=2
D to C=3
C to F=1
F back to A =5

So i get AEBDCFA which is going to be 1+3+2+3+1+5=15 which is the tour cost of that particular tour using the greedy algorithm, so it is one of many possible solutions for this problem?

So i am looking at a practice exam problem, and the solution is 12 and the tour chosen is AEDBFCA which is a more optimal tour... how do i know when to choose what? is that some other algorithm that produced AEDBFCA?

8. Originally Posted by SydneyBristow
ok it is sort of becoming more clear now. So using the greedy algorithm is to choose the closest point from the current point as the next point.

So if i start at A the closest is E =1
from E to B=3
B to D (or F, but alphabetically first lets say D)=2
D to C=3
C to F=1
F back to A =5

So i get AEBDCFA which is going to be 1+3+2+3+1+5=15 which is the tour cost of that particular tour using the greedy algorithm, so it is one of many possible solutions for this problem?

So i am looking at a practice exam problem, and the solution is 12 and the tour chosen is AEDBFCA which is a more optimal tour... how do i know when to choose what? is that some other algorithm that produced AEDBFCA?
If you use a permutaion method, you can get the correct answer for TSP all the time. However, it is not feasible to calculate all n! cases if n is a large number. For instance, if you have 100 cities, the time of computation might require more than billion years ( O(100!) > O(2^100) and 2^100 is an enormous number).

My suggestion is, if n < 10, then use the permutation and find the exact answer.

If n>10, use an heuristic algorithm to find the approximate solution of TSP problem.

1. Greedy algorith : it is very straight forward and easy to use. It does not generate a good performance though.
2. Dynamic programming : You might consider this one using some tables.
3. Genetic algorithm : It applies crossover, mutation, etc, to the permutations of cities. Instead of searching n!, it efficiently finds the approximate solution.
....

I don't know much about other algorithms for TSP.

There is no single algorithm that performs best all the time in all situations for TSP problems. It is up to you to choose the algorithm after examining the TSP problem you want to solve.