( 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.

( HereCollection_ais 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.

( HereCollection_bshows 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.

( HereCollection_dshows 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.

( HereCollection_ashows 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"