Notices
Results 1 to 1 of 1

Thread: Travelling Salesman Problem - Part 2

  1. #1 Travelling Salesman Problem - Part 2 
    Forum Freshman
    Join Date
    Nov 2012
    Posts
    9
    Step 2
    :- It denotes the step where the second starter vertex ( ie:- the right starter vertex ) of the starter edge is taken. For eg:- in step 2 for se[b,c], sv{c} is taken, ie:- vertex c is taken as the second starter vertex. Taking the right starter vertex as the second starter vertex for ‘step 2’ is for the purpose of convention.

    End of Notations


    Description of Starter edge method

    1S) Find the edge with the least minimum weight from all the edges of the graph.

    2S) Process the graph by taking the edge with the least weight and using the edge as a starter edge.

    3S) Process the starter edge for obtaining a hamilton circuit by first taking the left starter vertex of the starter edge. Then from the left starter vertex, apply the nearest neighbour method . If a hamilton circuit ( with no skipped edges ) is obtained, then stop the process immediately as this hamilton circuit is the possibly best minimum hamilton circuit. But if during the process, there are skipped edges, then keep the skipped edges for processing in the next stage.

    4S) After a hamilton circuit is obtained by using the first starter vertex, then process the starter edge by taking the right starter vertex. Then from the right starter vertex, apply the nearest neighbour method. If a hamilton circuit ( with no skipped edges ) is obtained, then stop the process immediately as this hamilton circuit is the possibly best minimum hamilton circuit. But if during the process, there are skipped edges, then keep the skipped edges for processing in the next stage.

    5S) Collect all the skipped edges and then sort the skipped edges according to their weight in ascending order. Then select the edge with the least weight and then take the edge as a starter edge and process it for a hamilton circuit using Step ‘3S’ and Step ‘4S’ . Do the process for finding the hamilton circuit for all the other skipped edges using Step ‘3S’ and Step ‘4S’ . The process is stopped if a hamilton circuit with no skipped edges is obtained. Otherwise the process is continued until all the skipped edges of all the ‘stages’ have been processed.

    6S) Collect all the hamilton circuits obtained during the processing of the starter edge in the beginning and the skipped edges of all the ‘stages’. Then select the hamilton circuit with the least weight among them. This hamilton circuit is the possibly best minimum weight hamilton circuit.

    ( Step numbers used for numbering the steps in the description are written as ‘1S’, ‘2S’ etc.. )

    End of Description


    The graph which is used to show how the starter edge method works is the same graph given in Figure 5.23 of Chapter 5 in Section 5.8 contained in the book ‘Elements of Discrete Mathematics’ by C.L.Liu. The graph is given the name Graph1.


    Collection_1 is a collection of the edges and the weights of all the edges of Graph1. The edges of Collection_1 are arranged in ascending sorted order of their weights.
    Collection_1 is :-
    w[b,e] = 5 ( ie:- Weight of edge [b,e] is ‘5’ )
    w[c,d] = 6
    w[a,d] = 7
    w[c,e] = 8
    w[b,c] = 9
    w[a,e] = 10
    w[d,e] = 11
    w[a,c] = 12
    w[b,d] = 13
    w[a,b] = 14

    Collection_a is a collection of the edges and the weights of all the edges of Graph1 which are connected to {a} ( ie:- vertex ‘a’ of Graph1 ) . The edges of Collection_a are arranged in ascending sorted order of their weights.
    Collection_a is :-
    w[a,d] = 7 ( ie:- Weight of edge [a,d] is ‘7’)
    w[a,e] = 10
    w[a,c] = 12
    w[a,b] =14

    Collection_b is a collection of the edges and the weights of all the edges of Graph1 which are connected to {b}. The edges of Collection_b are arranged in ascending sorted order of their weights.
    Collection_b is :-
    w[b,e] = 5
    w[b,c] = 9
    w[b,d] = 13
    w[a,b] = 14

    Collection_c is a collection of the edges and the weights of all the edges of Graph1 which are connected to {c}. The edges of Collection_c are arranged in ascending sorted order of their weights.
    Collection_c is :-
    w[c,d] = 6
    w[c,e] = 8
    w[b,c] = 9
    w[a,c] = 12

    Collection_d is a collection of the edges and the weights of all the edges of Graph1 which are connected to {d}. The edges of Collection_d are arranged in ascending sorted order of their weights.
    Collection_d is :-
    w[c,d] = 6
    w[a,d] = 7
    w[d,e] = 11
    w[b,d] = 13

    Collection_e is a collection of the edges and the weights of all the edges of Graph1 which are connected to {e}. The edges of Collection_e are arranged in ascending sorted order of their weights.
    Collection_e is :-
    w[b,e] = 5
    w[c,e] = 8
    w[a,e] = 10
    w[d,e] = 11

    Collection_a , Collection_b , Collection_c , Collection_d and Collection_e are the collections of the edges of Graph1 which are connected to {a} , {b} , {c} , {d} and {e} respectively.
    ( {a} , {b} , {c} , {d} and {e} are vertices of Graph1. )


    According to Collection_1 , edge [b,e] should be taken as the starter edge first, because of the least weight of the edge [b,e]. But in order to create an example of how the method works, an edge [c,e] is taken as the starter edge.


    Usage of starter edge method for Graph1

    Processing for Graph1 ( Solving Graph1 using se[c,e] ) ( First example )

    Beginning of First example

    Take edge se[c,e].

    Step 1 :-
    Take se[c,e] and sv{c}. ( Here ‘c’ is the left starter vertex of se[c,e] )
    pc(se[c,e],sv{c}) = (c,e) = PC1(HC1) = 8



    Continued in Travelling Salesman Problem - Part 3


    Reply With Quote  
     

  2.  
     

Similar Threads

  1. Travelling Salesman Problem - Part 1
    By varghese in forum Mathematics
    Replies: 0
    Last Post: December 4th, 2012, 01:35 AM
  2. Travelling into the future
    By couchSports in forum Physics
    Replies: 9
    Last Post: May 6th, 2010, 10:38 AM
  3. Travelling hotspots or travelling plates?
    By Pong in forum Earth Sciences
    Replies: 32
    Last Post: December 26th, 2009, 03:28 PM
  4. Complexity of Traveling Salesman Problem
    By diogenes in forum Mathematics
    Replies: 1
    Last Post: May 30th, 2008, 09:27 PM
  5. Complexity of Traveling Salesman Problem
    By diogenes in forum Computer Science
    Replies: 0
    Last Post: May 30th, 2008, 03:27 PM
Tags for this Thread

View Tag Cloud

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •