Notices
Results 1 to 1 of 1

Thread: Travelling Salesman Problem - Part 5

  1. #1 Travelling Salesman Problem - Part 5 
    Forum Freshman
    Join Date
    Nov 2012
    Posts
    9
    Step 2:-
    Take se[b,e],sv{e}.
    pc(se[b,e],sv{e}) = (b,e) = PC1(HC17)
    pc(se[b,e],sv{e}) = (b,e,c) = PC2(HC17)
    pc(se[b,e],sv{e}) = (b,e,c,d) = PC3(HC17)
    pc(se[b,e],sv{e}) = (b,e,c,d,a) = PC4(HC17)
    hc(se[b,e],sv{e}) = (b,e,c,d,a) = HC17
    HC17 was formed by skipping the edges [a,e] and [a,c]
    w(HC17)=5+8+6+7+14=40


    Stage 4 :-

    The edges which were skipped in ‘Stage 3’ were [a,e] and [a,c]. Now sorting the skipped edges according to the weights , we get the sorted order as [a,e] and [a,c]. Edges [a,e] and [a,c] was already processed in ‘Stage 1’. So now there are no more edges to be processed in ‘Stage 4’. So the process ends in Stage 4. Now all the weights of the hamiton circuits that are obtained in the beginning ( ie:- when the starter edge ie:- the edge [c,e] was processed ) and in all of the ‘stages’ are taken together and the least weight hamilton circuit from them is taken. This least weight hamilton circuit is the possibly best minimum weight hamilton circuit.

    Taking all the hamilton circuits together, we get

    HC1 = 40 ( ‘40’ is the weight of the hamilton circuit HC1 )
    HC2 = 45
    HC3 = 40
    HC4 = 37 ( No edges were skipped for HC4 )
    HC5 = 37
    HC6 = 37 (No edges were skipped for HC6 )
    HC7 = 37
    HC8 = 37 ( No edges were skipped for HC8 )
    HC9 = 44
    HC10 = 46
    HC11 = 37 ( No edges were skipped for HC11 )
    HC12 = 40
    HC14 = 45
    HC15 = 51
    HC16 = 37 ( No edges were skipped for HC16 )
    HC17 = 40

    HC4 , HC6 , HC8 , HC11 and HC16 are not taken for comparing the weights, because when these hamilton circuits are formed, the process should immediately stop, as these circuits are minimum circuits. But as mentioned earlier, the process is continued even if these circuits are obtained in order to describe how the process works if hamilton circuits ( in which no edges are skipped ) are not formed in the process. So the hamilton circuits HC1 , HC2 , HC3 , HC5 , HC7, HC9 , HC10 , HC12 , HC14 , HC15 and HC17 are taken and their weights are compared in order to get the minimum weight.

    The minimum weight circuits are the circuits with weight of ‘37’ and they are ‘HC5’ and ‘HC7’.

    End of First Example


    Processing for Graph1 ( Solving Graph1 using se[b,e] ) ( Second example )

    This is the process in which the minimum weight starter edge from Collection_1 of Graph1 is taken.

    Beginning of Second Example

    Take se[b,e]

    Step 1:-
    Take se[b,e],sv{b}
    pc(se[b,e],sv{b}) = (b,e) = PC1(HC18)
    pc(se[b,e],sv{b}) = (c,b,e) = PC2(HC18)
    pc(se[b,e],sv{b}) = (d,c,b,e) = PC3(HC18)
    pc(se[b,e],sv{b}) = (a,d,c,b,e) = PC4(HC18)
    hc(se[b,e],sv{b}) = (a,d,c,b,e) = HC18
    No edges were skipped while forming HC18.
    w(HC18)=5+9+6+7+10=37.
    Since no lesser weight edges were skipped while forming HC18, the process is immediately stopped.

    So in processing Graph1 with se[b,e] and sv{b}, the possibily minumum circuit ‘HC18’ is obtained.

    End of Second Example


    Conclusion :- The ‘starter edge’ method gives the possibly best hamilton circuit or an improved minimum weight hamilton circuit.


    Reference:-
    1) " Elements of Discrete Mathematics " by C.L.Liu ( Second Edition )( ISBN of the book is 0-07-100544-7 ).
    2) " A First Look at Graph Theory " by John Clark and Derek Allan Holton( ISBN of the book is 81-7023-463-8 ).



    Written by :- Samuel Gheverghese




    Continued in "Travelling Salesman Problem - Part 6"


    Reply With Quote  
     

  2.  
     

Similar Threads

  1. Travelling Salesman Problem - Part 4
    By varghese in forum Mathematics
    Replies: 0
    Last Post: December 4th, 2012, 01:47 AM
  2. Travelling Salesman Problem - Part 3
    By varghese in forum Mathematics
    Replies: 0
    Last Post: December 4th, 2012, 01:43 AM
  3. Travelling Salesman Problem - Part 2
    By varghese in forum Mathematics
    Replies: 0
    Last Post: December 4th, 2012, 01:38 AM
  4. Travelling Salesman Problem - Part 1
    By varghese in forum Mathematics
    Replies: 0
    Last Post: December 4th, 2012, 01:35 AM
  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
  •