Notices
Results 1 to 1 of 1

Thread: Travelling Salesman Problem - Part 4

  1. #1 Travelling Salesman Problem - Part 4 
    Forum Freshman
    Join Date
    Nov 2012
    Posts
    9
    Take se[a,e].

    Step 1:-
    Take se[a,e],sv{a}.
    pc(se[a,e],sv{a}) = (a,e) = PC1(HC7)
    pc(se[a,e],sv{a}) = (d,a,e) = PC2(HC7)
    pc(se[a,e],sv{a}) = (c,d,a,e) = PC3(HC7)
    pc(se[a,e],sv{a}) = (b,c,d,a,e) = PC4(HC7)
    PC4(HC7) was formed by skipping the edge [c,e]
    hc(se[a,e],sv{a}) = (b,c,d,a,e) = HC7
    w(HC7) = 10+7+6+9+5 = 37

    Step 2:-
    Take se[a,e],sv{e}.
    pc(se[a,e],sv{e}) = (a,e) = PC1(HC8)
    pc(se[a,e],sv{e}) = (b,c,d) = PC2(HC8)
    pc(se[a,e],sv{e}) = (b,c,d,a) = PC3(HC8)
    pc(se[a,e],sv{e}) = (b,c,d,a,e) = PC4(HC8)
    hc(se[a,e],sv{e}) = (b,c,d,a,e) = HC8
    w(HC8)=10+5+9+6+7=37
    No edges were skipped while forming HC8.


    Take se[a,c].

    Step 1:-
    Take se[a,c],sv{a}.
    pc(se[a,c],sv{a}) = (a,c) = PC1(HC9)
    pc(se[a,c],sv{a}) = (d,a,c) = PC2(HC9)
    pc(se[a,c],sv{a}) = (e,d,a,c) = PC3(HC9)
    PC3(HC9) was formed by skipping the edge [c,d]
    pc(se[a,c],sv{a}) = (b,e,d,a,c) = PC4(HC9)
    hc(se[a,c],sv{a}) = (b,e,d,a,c) = HC9
    w(HC9) = 12+7+11+5+9 = 44

    Step 2:-
    Take se[a,c],sv{c}.
    pc(se[a,c],sv{c}) = (a,c) = PC1(HC10)
    pc(se[a,c],sv{c}) = (a,c,d) = PC2(HC10)
    pc(se[a,c],sv{c}) = (a,c,d,e) = PC3(HC10)
    PC3(HC10) was formed by skipping the edge [a,d]
    pc(se[a,c],sv{c}) = (a,c,d,e,b) = PC4(HC10)
    hc(se[a,c],sv{c}) = (a,c,d,e,b) = HC10
    HC10 was formed by skipping the edges [b,c] and [b,d]
    w(HC10)=10+6+11+5+14=46


    Stage 2 :-

    The edges which were skipped in ‘Stage 1’ were [b,c] , [b,d] , [c,e] , [c,d] and [a,d] . Now sorting the skipped edges according to the weights , we get the sorted order as [c,d] , [a,d] , [c,e] , [b,c] and [b,d]. Edge [c,e] was processed in the beginning as the first starter edge. [c,d] and [b,c] was processed in ‘Stage 1’. So now the edges left for processing in ‘Stage 2’ are [a,d] and [b,d].


    Take se[a,d].

    Step 1:-
    Take se[a,d],sv{a}.
    pc(se[a,d],sv{a}) = (a,d) = PC1(HC11)
    pc(se[a,d],sv{a}) = (e,a,d) = PC2(HC11)
    pc(se[a,d],sv{a}) = (b,e,a,d) = PC3(HC11)
    pc(se[a,d],sv{a}) = (c,b,e,a,d) = PC4(HC11)
    hc(se[a,d],sv{a}) = (c,b,e,a,d) = HC11
    w(HC11) = 7+10+5+9+6=37
    No edges were skipped while forming HC11.


    Step 2:-
    Take se[a,d],sv{d}.
    pc(se[a,d],sv{d}) = (a,d) = PC1(HC12)
    pc(se[a,d],sv{d}) = (a,d,c) = PC2(HC12)
    pc(se[a,d],sv{d}) = (a,d,c,e) = PC3(HC12)
    pc(se[a,d],sv{d}) = (a,d,c,e,b) = PC4(HC12)
    hc(se[a,d],sv{d}) = (a,d,c,e,b) = HC12
    HC12 was formed by skipping the edges [b,c] and [b,d]
    w(HC12)=7+6+8+5+14=40


    Take se[b,d].

    Step 1:-
    Take se[b,d],sv{b}.
    pc(se[b,d],sv{b}) = (b,d) = PC1(HC14)
    pc(se[b,d],sv{b}) = (e,b,d) = PC2(HC14)
    pc(se[b,d],sv{b}) = (c,e,b,d) = PC3(HC14)
    pc(se[b,d],sv{b}) = (a,c,e,b,d) = PC4(HC14)
    PC4(HC14) was formed by skipping the edges [c,d] and [b,c]
    hc(se[b,d],sv{b}) = (a,c,e,b,d) = HC14
    w(HC14) = 13+5+8+12+7=45


    Step 2:-
    Take se[b,d],sv{d}.
    pc(se[b,d],sv{d}) = (b,d) = PC1(HC15)
    pc(se[b,d],sv{d}) = (b,d,c) = PC2(HC15)
    pc(se[b,d],sv{d}) = (b,d,c,e) = PC3(HC15)
    pc(se[b,d],sv{d}) = (b,d,c,e,a) = PC4(HC15)
    PC4(HC15) was formed by skipping the edge [b,e]
    hc(se[b,d],sv{d}) = (b,d,c,e,a) = HC15
    HC15 was formed by skipping the edge [a,d] and [a,c]
    w(HC15)=13+6+8+10+14=51


    Stage 3 :-

    The edges which were skipped in ‘Stage 2’ were [b,c] , [b,d] , [c,d] , [b,e] , [a,d] and [a,c] . Now sorting the skipped edges according to the weights , we get the sorted order as [b,e], [c,d] , [a,d] , [b,c] , [a,c] and [b,d]. Edges [c,d] , [b,c] and [a,c] was processed in ‘Stage 1’. Edges [a,d] and [b,d] was processed in ‘Stage 2’ . So now the edge left for processing in ‘Stage 3’ is [b,e].


    Take se[b,e].

    Step 1:-
    Take se[b,e],sv{b}.
    pc(se[b,e],sv{b}) = (c,b,e) = PC1(HC16)
    pc(se[b,e],sv{b}) = (c,b,e) = PC2(HC16)
    pc(se[b,e],sv{b}) = (d,c,b,e) = PC3(HC16)
    pc(se[b,e],sv{b}) = (a,d,c,b,e) = PC4(HC16)
    hc(se[b,e],sv{b}) = (b,e) = HC16
    w(HC16) = 5+9+6+7+10=37
    No edges were skipped while forming HC16.




    Continued in "Travelling Salesman Problem - Part 5"


    Reply With Quote  
     

  2.  
     

Similar Threads

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