Notices
Results 1 to 1 of 1

Thread: Travelling Salesman Problem - Part 3

  1. #1 Travelling Salesman Problem - Part 3 
    Forum Freshman
    Join Date
    Nov 2012
    Posts
    9
    ( Applying ‘nearest neighbour method’ to vertex ‘c’ of the edge ‘[c,e]’ and trying to form a hamilton circuit which must include the edge ‘[c,e]’. )

    w(PC1(HC1))=8

    Adding vertex ‘d’ according to nearest neighbour method.
    pc(se[c,e],sv{c}) = (d,c,e) = PC2(HC1) = 8+6 = 14
    w(PC2(HC1))=14

    Adding vertex ‘a’ according to nearest neighbour method.
    pc(se[c,e],sv{c}) = (a,d,c,e) = PC3(HC1) = 8+6+7 = 21
    w(PC3(HC1))=21

    Adding vertex ‘b’ according to nearest neighbour method.
    pc(se[c,e],sv{c}) = (b,a,d,c,e) = PC4(HC1) = 8+6+7+14 = 35
    w(PC4(HC1))=35
    PC4(HC1) was formed by skipping the edges [a,e] and [a,c] which has a lesser weight of ‘10’ and ‘12’ respectively than the edge [a,b] which has a weight of ‘14’.
    ( Here Collection_a is used to find out that the edges [a,e] and [a,c] have been skipped from vertex ‘a’ in order to reach vertex ‘b’ when using the nearest neighbour method. )

    Joining ‘b’ to ‘e’ in order to form the hamilton circuit.
    hc(se[c,e],sv{c}) = (b,a,d,c,e) = HC1 = 8+6+7+14+5 = 40
    w(HC1)=40

    Therefore the edges which were skipped during the process of forming HC1 were [a,e] and [a,c].


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

    ( Applying ‘nearest neighbour method’ to vertex ‘e’ of the edge ‘[c,e]’ and trying to form a hamilton circuit which must include the edge ‘[c,e]’. )

    Adding vertex ‘b’ according to nearest neighbour method.
    pc(se[c,e],sv{e}) = (c,e,b) = PC2(HC2) = 8+5=13
    w(PC2(HC2)) = 13

    Adding vertex ‘d’ according to nearest neighbour method.
    pc(se[c,e],sv{e}) = (c,e,b,d) = PC3(HC2) = 8+5+13=26
    PC3(HC2) was formed by skipping the edge [b,c] which has a lesser weight of ‘9’ than the edge [b,d] which has a weight of ‘13’.
    ( Here Collection_b shows that the edge [b,c] has been skipped from vertex ‘b’ in order to reach vertex ‘d’ when using the nearest neighbour method. )
    w(PC3(HC2)) = 26

    Adding vertex ‘a’ according to nearest neighbour method.
    pc(se[c,e],sv{e}) = (c,e,b,d,a) = PC4(HC2) = 8+5+13+7=33
    PC4(HC2) was formed by skipping the edge [c,d] which has a lesser weight of ‘6’ than the edge [a,d] which has a weight of ‘7’.
    ( Here Collection_d shows that the edge [c,d] has been skipped from vertex ‘d’ in order to reach vertex ‘a’ when using the nearest neighbour method. )
    w(PC4(HC2))=33

    Joining ‘a’ to ‘c’ in order to form the hamilton circuit.
    hc(se[c,e],sv{e}) = (c,e,b,d,a) = HC2 = 8+5+13+7+12=45
    HC2 was formed by skipping the edge [a,e] which has a lesser weight of ‘10’ than the edge [a,c] which has a weight of ‘12’.
    ( Here Collection_a shows that the edge [a,e] has been skipped from vertex ‘a’ in order to reach vertex ‘c’ when using the nearest neighbour method. )
    w(HC2)=45

    Therefore the edges which were skipped during the process of forming HC2 were [b,c] , [c,d] and [a,e].

    Now the process for the edge [c,e] is finished as both the starter vertices ‘c’ and ‘e’ have been processed. Now next is ‘stage 1’ where all the edges which have been skipped has to be processed.


    Stage 1 :-

    The edges which were skipped were [a,e] , [a,c] , [b,c] and [c,d]. Now sorting the skipped edges according to the weights , we get the sorted order as [c,d] , [b,c] , [a,e] and [a,c].

    Now taking se[c,d].

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

    Step 2:-
    Take se[c,d],sv{d}.
    pc(se[c,d],sv{d} = (c,d) = PC1(HC4)
    pc(se[c,d],sv{d} = (c,d,a) = PC2(HC4)
    pc(se[c,d],sv{d} = (c,d,a,e) = PC3(HC4)
    pc(se[c,d],sv{d} = (c,d,a,e,b) = PC4(HC4)
    hc(se[c,d],sv{d} = (c,d,a,e,b) = HC4
    No edges were skipped while forming HC4. So here the process can be stopped immediately, because the possibly best minimum hamilton circuit is got here. But in order to describe how the process works, the process is continued.
    w(HC4)=6+7+10+5+9=37

    (In the next example (ie:- second example ), where the least weight edge ie:- [b,e] is taken as the starter edge in the beginning, the process is shown to be stopped when there are no skipped edges while processing for a hamilton circuit. )


    Take se[b,c].

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

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



    Continued in "Travelling Salesman Problem - Part 4"


    Reply With Quote  
     

  2.  
     

Similar Threads

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