This is a permutation problem. Let G = (V, E) be a directed graph with edge costs $c_{ij}$, where

Let $\left|V\right|=n$ and assume n > 1.

A tour of G is a directed simple cycle that includes every vertex in V. The cost of a tour is the sum of the costs of the edges on the tour. The TSP finds a tour of minimum cost.

Applications

1. Routing a postal van to pick up mail from mail boxes located at n different sites. An (n + 1)-vertex graph represents this situation. One vertex represents the post office from which the postal van starts and to which it must return. Edge ⟨i, j⟩ is assigned a cost equal to the distance from site i to site j. The aim is to minimize the tour length.
2. Robot arm to tighten the nuts on some piece of machinery on an assembly line. The arm should start from the initial position, successively move to each of the remaining nuts, and return to the initial position. The path of the arm is the tour, and the vertices represent the nuts. The aim is to minimize the time needed for the arm to complete the task.
3. Production environment in which several commodities are manufactured on the same set of machines. Manufacture proceeds in cycles. In each production cycle, n different commodities are produced. When the machines are changed from production of commodity i to j, a changeover cost $c_{ij}$ is incurred. Find a sequence that minimizes the sum of changeover costs. It is necessary to include the cost of starting the next cycle, which is the changeover cost from the last to the first commodity. This is a TSP on an n-vertex graph with edge costs $c_{ij}$ being the changeover cost from commodity i to j.

Dynamic programming formulation

Let a tour be a simple path that starts and ends at vertex 1. Every tour consists of an edge ⟨1, k⟩ for some $k\in V-\left\{1\right\}$ and a path from vertex k to vertex 1. The path from vertex k to 1 goes through each vertex in $V-\{1,k\}$ exactly once.

If the tour is optimal, then the path from k to 1 must be a shortest k to 1 path going through all vertices in $V-\{1,k\}$.

Let $g(i,S)$ be the length of the shortest path starting at vertex i, going through all vertices in S, and terminating at vertex 1. Then $g(1,V-\{1\left\}\right)$ is the length of an optimal salesperson tour.

From the principle of optimality:

Generalizing the above equation (for $i\notin S$):

Equation (1) can be solved for $g(1,V-\{1\left\}\right)$ if we know $g(k,V-\{1,k\left\}\right)$ for all k.

The g values can be obtained by (2). To obtain $g(i,S)$ for all |S| = 1, start with

then obtain $g(i,S)$ for all |S| = 2, and so on.

When |S| < n − 1, the values of i and S for which g(i, S) is needed are such that i ≠ 1, 1 ∉ S, and i ∉ S.

Example

Consider the directed graph with the following edge lengths.

Let the tour start at vertex 1. The given adjacency matrix is $c_{ij}$, with rows and columns numbered 1 to 4.

Step 1: |S| = 0

$g(i,\varnothing )=c_{i1}$

Step 2: |S| = 1, i ∉ S (S can be {2}, {3} or {4})

$g(i,S)=\underset{j\in S}{\min }\{c_{ij}+g(j,S-\left\{j\right\}\left)\right\}$

Step 3: compute g(i, S) with |S| = 2, i ≠ 1, 1 ∉ S and i ∉ S

The value of j that gives the minimum is recorded as well.

Step 4: compute g(1, S) with |S| = 3

⇒ The optimal tour has length 35.

Constructing the tour

To construct a tour of this length, consider the value of j that minimizes the right-hand side.

• $J(i,S)=J(1,\{2,3,4\left\}\right)=2$: the tour starts at 1 and goes to 2, i.e. 1 → 2.
• Consider $g(2,\{3,4\left\}\right)$, i.e. $J(2,\{3,4\left\}\right)=4$, so the next edge is ⟨2, 4⟩: 1 → 2 → 4.
• Now $g(4,\{3\left\}\right)$, i.e. $J(4,\{3\left\}\right)=3$, so the tour continues 4 → 3 and then returns to 1.

⇒ 1 → 2 → 4 → 3 → 1 is the optimal tour, with length 10 + 10 + 9 + 6 = 35.

Complexity

• Time complexity = $\Theta \left(n^2{2}^n\right)$. This is better than enumerating all $n!$ different tours and finding the best one.
• Space complexity = $O\left(n{2}^n\right)$. This is too large even for modest values of n.