This slideshow introduces and explains the "Traveling Salesman" Problem.
There are n cities. Every pair of cities is separated by some distance. A traveling salesman aims to visit each one exactly once, and the total distance covered during the tour is as short as possible.
This can be modeled as a complete graph where each node represents a particular city and the weight of the edges denote the distance between the two cities it connects. The problem now can be stated as finding the shortest simple cycle in the graph that passes through all vertices in the graph. (The length of a cycle is the sum of weights of all the edges included in the cycle.)
Note: A simple cycle may be defined as a closed walk with no repetitions of vertices and edges allowed, other than the repetition of the starting and ending vertex.
An example:
A
B
C
D
E
1
2
3
4
4
5
6
7
8
10
The red edges form a minimum-length tour with total length being 24.
The Traveling Salesman problem can be defined either as a decision problem or not. The decision form is know to be NP-complete.
Given a graph G=(V,E), find the shortest simple cycle that passes through all vertices of the graph.The length of the cycle is the sum of weights of its edges.
OR
(Decision Problem Form:) Given a graph G=(V,E) and integer k, does the graph contain a simple cycle that passes through all vertices and has length ≤k?
A
B
C
D
E
F
G
1
2
3
4
5
6
4
5
6
7
8
7
8
9
10
10
11
12
13
14
16
Does this graph have a simple cycle that includes all vertices and has length ≤50?
No
Does this graph have a simple cycle that includes all vertices and has length <= 55?
