Let G=(V,E) be a directed graph with edge cost cij. The variable cij is defined such that cij>0 for all i and j and cij=∞ if (i,j) ∉ E.
A tour of G is a directed simple cycle that includes every vertex in V.
The cost of the tour is the sum of the edge costs in the tour.
The travelling salesperson problem is to find a tour of minimum cost.
Let us assume for simplicity out tours starts at vertex 1. Every tour consists of an edge (1,k) for some k ∈ V-{1} and a path from k to vertex 1.
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.
Then we need to find g(1, V-{1}) to get the optimal sales person tour.
Generalizing we obtain (for i∉S )
clearly
Problem:
Solution:
g(2, ɸ)=c21=5
g(3, ɸ)=c31=6
g(4, ɸ)=c41=8
g(2,{3})= c23+g(3, ɸ)=9+6=15
g(2,{4})=c24+g(4, ɸ)=10+8=18
g(3,{2})=18
g(3,{4})=20
g(4,{2})=13
g(4,{3})=15
g(2,{3,4})=min{c23+g(3,{4}), c24+g(4,{3})
= min{9+20,10+15}=25
g(3,{2,4})= min{c32+g(2,{4}), c34+g(4,{2})}
=min{13+18,12+13}=25
g(4,{2,3})=23
g(1,{2,3,4})=min{c12+g(2,{3,4}), c13+g(3,{2,4}), c14+g(4,{2,3})}
=min{10+25,15+25,20+23}=35
So the tour of minimum cost is 1-2-4-3-1, tour cost is 35
Top comments (0)