24-09-2016, 09:43 AM
1455972286-AppendixB2.ppt (Size: 30 KB / Downloads: 3)
Regard a tour to be a simple path that starts and end at vertex 1.
Every tour consists of an edge <1,k> for some k V – {1} and a path from k to vertex 1. The path from vertex k to vertex 1 goes through each vertex in V – {1,k} exactly once.
Let g(i, S) be the length of a shortest path starting at vertex i, going through all vertices in S and terminating at vertex 1.
g(1, V- {1}) is the length of an optimal salesperson tour.
From the principle of optimality it follows that:
g(1, V – {1}) = min {c1k + g(k, V- {1, k})} (1)
2≤k ≤n