Coders Packet

Travelling salesperson problem

By M Abirami

  • Travelling Salesman.docx
  • The tourist or traveler want to visit all the places in a city within a day or in few hours. TSP will help them to find shortest distance .

    Travelling Salesman problem is used to find shortest distance.If a person give group of cities and ask us to find a particular city with shortest distance in this situation Travelling Salesman Problem will help us to find shortest distance of the city.

    Travelling salesman problem is the too bad computational problem. We can also use brute-force approach to evaluate every possible route and select the best one. For n number of vertices in a graph, there are (n - 1)! number of possibilities.

    Algorithm: Traveling-Salesman-Problem 
    T{1}, 1) = 0 
    for s = 2 to n do 
       for all subsets S Є {1, 2, 3, … , n} of size s and containing 1 
          T(S, 1) = ∞ 
       for all j Є S and j ≠ 1 
          T(S, j) = min {T (S – {j}, i) + d(i, j) for i Є S and i ≠ j} 
    Return minj T({1, 2, 3, …, n}, j) + d(j, i) 


    Download Complete Code


    No comments yet