Scribd Logo
Upload

Welcome to Scribd!

  • 11 views

    13 Dynamic Programming - TSP

    Uploaded by

    ctxxfx5ykz

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    13 Dynamic Programming - TSP

    Uploaded by

    ctxxfx5ykz
    11 views12 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    11 views12 pages

    13 Dynamic Programming - TSP

    Uploaded by

    ctxxfx5ykz

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 12

    Design and Analysis of Algorithms

    Dynamic Programming
    (Travelling Salesman Problem)

    Dr. D. P. Acharjya
    Professor, SCOPE
    Office: SJT Annex 201E
    Email: debiprasannaacharjya@vit.ac.in

    Dr. D. P. Acharjya 2/21/2024 1


    Travelling Salesman Problem
     The job of a travelling salesman is to visit all the cities
    linked by roads in a particular territory.
     He has to visit all the cities exactly once and to return
    his home city in such a manner that, the total cost
    (distance travelled, time, money) is minimum.
     The above problem can be visualized as a graph theory
    problem. Consider all the cities as vertices and the
    roads connected to them as edges.
     So, it is a weighted directed graph.
     Our objective is to find a minimum cost Hamiltonian
    tour for a graph.
    Dr. D. P. Acharjya 2/21/2024 2
    Complete Graph, Walk and Tour
     A graph G(V, E); E  (VV) is said to be a
    complete graph, if for every pair of vertices, there
    exists an edge.
     A walk is a sequence of vertices and edges of a
    graph G(V, E).
     A tour is a walk in which the start and end vertex is
    same.
     A tour in which all the edges are travelled exactly
    once is known as Eulerian tour.
     A tour in which all the vertices are visited exactly
    once is known as Hamiltonian tour.
    Dr. D. P. Acharjya 2/21/2024 3
    Mathematical Formulation
     Let G(V,E) be a complete directed graph. Let the cost from
    ith vertex to jth vertex be cij.
     Let |V| = n such that n > 1.
     Let us consider the tour starts from vertex 1 and ends at
    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 i.

    Dr. D. P. Acharjya 2/21/2024 4


    Continued …
     Above equation is executed for |S| = 1, 2, 3, … with i  1
    and i  S.
     If |S| = (n - 1), then the optimal tour is defined as:

    Dr. D. P. Acharjya 2/21/2024 5


    Numerical Illustration
     Consider the cities are connected as per the
    following graph. Find an optimal tour to the
    travelling salesman problem over the given graph.

    Dr. D. P. Acharjya 2/21/2024 6


    Solution
     The adjacency matrix of the above graph with
    respect to the vertices 1, 2, 3, and 4 is given as:

     Let the source vertex be 1. Thus we get:

    Dr. D. P. Acharjya 2/21/2024 7


    Continued …
     For |S| = 1, we have S = {3} or {4} for i = 2.

    Dr. D. P. Acharjya 2/21/2024 8


    Continued …
     For |S| = 2, we have S = {3, 4} for i = 2.

    Dr. D. P. Acharjya 2/21/2024 9


    Continued …
     For |S| = 2, we have S = {2, 3} for i = 4.

    Dr. D. P. Acharjya 2/21/2024 10


    Continued …
     The optimal tour is given as |S| = (n-1) = 3

     The Optimal Tour is given below with cost = 35


    12431
    Dr. D. P. Acharjya 2/21/2024 11
    Computing Time
     The total number of computations for g(i, S) for |S|
    = k is given as:

     The number of comparisons in optimal tour is (n -


    2) as |S| = (n - 1)
     Total time is given as:

    Dr. D. P. Acharjya 2/21/2024 12

    You might also like