varghese Posted November 30, 2012 Share Posted November 30, 2012 (edited) I have found a new solution to the Travelling Salesman Problem. I have tried the solution on all the "complete" graphs of the examples in the 2 textbooks given in the reference section in the post given below. The solution is as follows :- Starter Edge method for an improved solution for the Travelling Salesman Problem Abstract This paper is mainly about a solution to the graph problem of Figure 5.23 given in the book 'Elements of Discrete Mathematics' by C.L.Liu. General note In the starter edge method, the edge with the least weight in a graph is selected as the beginning edge to be taken to be processed. Then from the starter edge, a starter vertex is selected. Then from the starter vertex, the 'nearest neighbour method' ( This method is the same method that is mentioned in the book 'Elements of Discrete Mathematics' by C.L.Liu in Section 5.8 of Chapter 5 ) is applied. A hamilton circuit is obtained. Collect all the edges with lesser weights which are skipped when the process for obtaining the hamilton circuit is carried out. If any lesser weight edges are not skipped when obtaining the hamilton circuit, then this hamilton circuit is the minimum weight hamilton circuit. Collect all these edges for processing in the next stage. After the hamilton circuit is obtained, then the second starter vertex from the starter edge is selected. Then from the second starter vertex, the nearest neighbour method is applied. Then during the process of obtaining the hamilton circuit, if any lesser weight edges are skipped, they are collected to be processed in the next stage. Then in the next stage, sort all the skipped edges according to their weights. Then from the least weight skipped edge, select the skipped edge as the starter edge and start the same type of process that was done at the beginning. Proceed to process all the skipped edges to obtain hamilton circuits ( If there is any hamilton circuit which did not have any skipped edges, then stop the process immediately because the possibly minimum hamilton circuit has been found.). So the process continues ( if there are more skipped edges to be processed ) in further stages until a hamilton circuit with no skipped edges is obtained or until all the skipped edges have been processed. When all the skipped edges have been processed, collect all the hamilton circuits together and find the hamilton circuit with the least weight among them. This hamilton circuit is the possibly best minimum hamilton circuit. Notations [n1,n2] :- It denotes the edge joining the vertices n1 and n2 in a graph where n1 and n2 are alphabets or integers. Also n1 < n2 in order to avoid duplication of edges. 'n1' is called the left vertex of the edge [n1,n2] and 'n2' is called the right vertex of the edge [n1,n2]. For eg:- [b,c] and [c,b] represent the same edge, so the edge is only represented as [b,c] where b is alphabetically less than c. Also for eg:- in the edge [b,c], 'b' is called the left vertex and 'c' is called the right vertex. w[n1,n2] :- It denotes the weight of the edge connecting the vertices n1 and n2. {n1} :- It denotes the vertex n1 of a graph where n1 is an alphabet or an integer. sv{n1} :- It denotes the 'starter vertex' ie:- the vertex 'n1' from which the construction of the hamilton circuit begins. n1 is an alphabet or integer. se[n1,n2] :- It denotes the 'starter edge' ie:- an edge which joins the vertices 'n1' and 'n2'. n1 and n2 are alphabets or integers. The starter edge is the starting edge from which the construction of the hamilton circuit begins and is the edge which must be included in the hamilton circuit that is being formed. For the sake of convention, the first starter vertex is always taken from the left vertex of the starter edge and the second starter vertex is always taken from the right vertex of the starter edge. For eg:- in 'se[b,c]', sv{b} is always taken first for processing the first hamilton circuit and sv{c} is always taken second for processing the second hamilton circuit ie:- the numerically or alphabetically lesser vertex is taken first for constructing the hamilton circuit, for the purpose of convention. Also in the notation 'se[n1,n2]', 'n1' is called the left starter vertex and 'n2' is called the right starter vertex. PCm :- It denotes the mth partial circuit where m is an integer. w(PCm) :- It denotes the total weight of the mth partial circuit where m is an integer. pc(se[n1,n2],sv{n2}) = PCm :- 'pc(se[n1,n2],sv{n2})' denotes the partial circuit which has starter edge of [n1,n2] and a starter vertex of 'n2'. Also to make the notation into shortform, this notation can also be equated to PCm (ie:- the mth partial circuit ). Also to denote the vertices present in the partial circuit, the vertices can also be represented as for eg:- 'pc(se[n1,n2],sv{n2}) = PCm = (n1,n2,n3)' denotes the mth partial circuit containing the vertices n1,n2 and n3. Here {n1} is connected to {n2} to form an edge [n1,n2] and {n2} is connected to {n3} to form an edge [n2,n3]. Also the above notation can be written as 'pc(se[n1,n2],sv{n2}) = (n1,n2,n3) = PCm' which also has the same meaning. HCm :- It denotes the mth hamilton circuit where m is an integer. w(HCm) :- It denotes the weight of the mth hamilton circuit where m is an integer. pc(se[n1,n2],sv{n2}) = PCm(HCz) :- It denotes the mth partial circuit of the zth hamilton circuit. Here the zth hamilton circuit is not fully formed yet, but is going to be formed later when all the vertices of the graph has been added to the partial circuit in order to form the hamilton circuit. For eg:- 'pc(se[n1,n2],sv{n2}) = PCm(HCz) = (n1,n2,n3)' means the mth partial circuit of the zth hamilton circuit (the zth hamilton circuit is the hamilton circuit which is going to be formed later) and consists of the vertices n1,n2 and n3. Also the above notation can be written as 'pc(se[n1,n2],sv{n2}) = (n1,n2,n3) = PCm(HCz)' which also has the same meaning. w(PCm(HCz)) :- It denotes the weight of the mth partial circuit ( where m is an integer ) of the zth hamilton cirucit. ( The hamilton circuit will be formed later when all the vertices of the graph has been included in the partial circuit.) hc(se[n1,n2],sv{n2}) = HCm :- 'hc(se[n1,n2],sv{n2})' denotes the hamilton circuit which has starter edge of [n1,n2] and a starter vertex of 'n2'. Also to make the notation into shortform, this notation can also be equated to HCm (ie:- the mth hamilton circuit ). Also to denote the vertices present in the hamilton circuit, the vertices can also be represented as, for eg:- 'hc(se[n1,n2],sv{n2}) = HCm = (n1,n2,n3,n4)' which denotes the mth hamilton circuit containing the vertices n1,n2,n3 and n4. Here {n1} is connected to {n2} to form the edge [n1,n2] , {n2} is connected to {n3} to form the edge [n2,n3] , {n3} is connected to {n4} to form the edge [n3,n4] and {n4} is connected to {n1} to form the edge [n1,n4]. Also the above notation can be written as 'hc(se[n1,n2],sv{n2}) = (n1,n2,n3,n4) = HCm' which also has the same meaning. w(HCm) :- It denotes the total weight of the mth hamilton circuit . Skipped edge :- 'Skipped edge' means an edge which was considered for forming a part of the hamilton circuit because of its lesser weight, but is not taken because taking this edge will not form a hamilton circuit, since addition of this edge causes more than 2 edges to be attached to a single vertex, since in a hamilton circuit, only 2 edges are allowed to be attached to a single vertex. Stage r :- It denotes the processing stage where all the skipped edges are sorted according to their weights and are taken one by one (beginning with the least weight edge) with each edge considered as a starter edge. Also the process for obtaining the hamilton circuits from the skipped edges take place in a particular stage. 'r' is an integer. Step 1 :- It denotes the step where the first starter vertex ( ie:- the left starter vertex ) of the starter edge is taken. For eg :- in step 1 for se[b,c], sv{b} is taken, ie:- vertex b is taken as the first starter vertex. Also taking the left starter vertex as the first starter vertex for 'step 1' is for the purpose of convention. 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 ( 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. 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. 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 Address :- Haripad, Alleppey District, Kerala, India. Degree :- B.Tech ( Computer Science and Engineering ) Email :- purplesky1111@yahoo.com Edited November 30, 2012 by varghese Link to comment Share on other sites More sharing options...
Phi for All Posted November 30, 2012 Share Posted November 30, 2012 ! Moderator Note Thank you, only one thread per topic, please, to make it easier to discuss. Link to comment Share on other sites More sharing options...
varghese Posted December 4, 2012 Author Share Posted December 4, 2012 (edited) This is a continuation of the post "Travelling Salesman Problem". I am giving a very simple explanation of the algorithm so that it becomes easier to understand. I did not want to make an edit in the main post. That is why I am writing the explanation notes here. The notes are:- The main advantage of this approach is that the exact solution can be obtained for "complete" graphs in polynomial time. ( Please note that the word "complete" which is mentioned here is the same mathematical term used in graph theory ). I tried out the "complete" graph examples in the textbook using pen and paper and they are giving the exact solutions. Now the only thing is that solution needs to be tested on further complete graph examples using computers and software by scientists. Also the solution is polynomial time, because the solution is a new type of modified and improved version of the nearest neighbour method. And everyone knows that the nearest neighbour method is an approximate method which is polynomial time method. But this new modified method, gives exact solution to "complete" graphs and it is polynomial time also. In graph theory, a complete graph of n vertices has [ n(n-1)/2 ] edges. So when implementing the algorithm, in the worst case, all the edges may have to be taken for processing. Also for each edge, the left vertex and the right vertex has to be taken for processing. So the number of times the edges have to be taken for processing = number of edges * 2 = [ n(n-1)/2] * 2 = n(n-1) = n^2 - n . So the processing time for the algorithm in the worst case = O(n^2) ie:- it takes polynomial time. ( Here "^" means raised to ). In the example that I have given for describing how the algorithm works, I have taken a random edge in order to show how the algorithm works. Where the algorithm is taken with the minimum weight edge , the process is shown between the headings "Beginning of second example" and"End of second example" and this description is short and easy for viewing. I am claiming that I have tried the algorithm on all the examples given in the theory sections of the 2 textbooks and they give exact solutions. But I dont have mathematical proof. For graphs that are not complete, I cannot claim that it will give the exact solution, but I can only say that they might give the best solution. That is how far have I have tested. For other scientists, to get further convinced, it is better, if they try out this algorithm on more complete graphs at least using pen and paper for the time being instead of using computers. I am not forcing anyone to try it out. A lot of Mathematicians are saying that there might never be a solution to this problem, so I thought it was a little exciting if this algorithm would provide any clue which could further advance the research of the scientists. For proof of such problems, advanced degrees in maths is required like B.Sc, M.Sc, PhD etc. I don't even have a B.Sc degree, but only a B.Tech Degree. But the mathematics that I have learnt in B.Tech is not formal enough for finding a proof of such theorems. I can say that what I have given in the post is a " conjecture ". This word is more suitable. I will try to put the explanation of the algorithm in very simple terms as far as possible. All Discrete Mathematicians know about the nearest neighbour method. In the nearest neighbour method, a random edge is taken and the nearest neighbour method is applied starting from that edge. This is the method that is known that is known to everyone. So when the nearest neighbour method is done, the process is O(1). Now in my method ( if for example the worst case is taken ie:- every edge of the complete graph is taken ( Also suppose the complete graph consists of "n" edges. ) ) , then the nearest neighbour method is applied to each edge ( taking the most minimum weight edge first and proceeding in ascending order of the weights of the edges ) , then the number of hamilton circuits obtained will be "n" hamilton circuits. So now the order will be O(n) because of "n" edges. Now the most important part of the algorithm is that for each edge, the nearest neighbour method should be applied by starting from the left vertex of the edge and then the next hamilton circuit should be obtained by starting from the right vertex of the edge by using the nearest neighbour method. So each edge should contain two hamilton circuits (which is obtained by using the nearest neighbour method ). So now the total number of hamilton circuits obtained for "n" edges will be " 2*n " hamilton circuits. So now the the order is O(2n) ie:- O(n). ( Please note that here the number of edges is taken as "n" and not the number of vertices , for easy understanding.) The most important point is that for each edge, 2 hamilton circuits are required which are produced by starting from the left vertex and the other by starting from the right vertex of the edge. So the software for this algorithm is already there ie:- nearest neighbour method programs. The only modification that is needed for the software is that the nearest neighbour method should be applied to each edge, and for each edge, the nearest neighbour method should be applied to the left vertex and the right vertex of each edge. So for a complete graph of "n" vertices, in the worst case, there are "2n" hamilton circuits. Then the minimum weight hamilton circuit among all these hamilton circuits is taken as the shortest weight hamilton circuit. Edited December 4, 2012 by varghese Link to comment Share on other sites More sharing options...
varghese Posted December 7, 2012 Author Share Posted December 7, 2012 (edited) The "starter edge method" given in the post can be written in short form as "SEM". In order to create a software for "SEM" may take a long time. So in order to quickly get results for testing, I am giving a modified version of the starter edge method which I will call as "modified starter edge method" or in short as "MSEM". The "Nearest Neighbour Method" is written in short form as "NNM". The minimum hamilton circuit can be found from "MSEM" and it will give the same minimum hamilton circuit as the "SEM". Why I am giving the "MSEM" is because the "SEM" may take time to understand because of the many notations, although the algorithm is very simple. Since the time complexity of the travelling salesman problem is more important and since the time complexity of "MSEM" is O(n^2), "MSEM" can be used for testing and getting the results quickly. In the "NNM", a random vertex is taken to get the approximate minimum weight hamilton circuit. The "NNM" is mainly used in the "MSEM". In "MSEM", eventhough the "NNM" is used, the edges of the graph are considered very important. So the "MSEM" is as follows. Collect all the edges of the graph. Take an individual edge from the collection of edges. This edge consists of a left vertex and a right vertex. Suppose this edge is called "E1". Then from the left vertex apply the "NNM". One hamilton circuit ie:- "HC1" will be formed. Now in "HC1", the edge "E1" will be present ie:- the property of "HC1" is that the edge "E1" will be and must be included in "HC1". Now take the right vertex of "E1" and apply the "NNM" from the right vertex and form a hamilton circuit "HC2". Now again the property of "HC2" is that "E1" will be and must be included in "HC2". So from edge "E1", two hamilton circuits "HC1" and "HC2" are obtained. Now doing the same process for second edge "E2", two hamilton circuits "HC3" and "HC4" are obtained. Here the edge "E2" will be and must be present in both the hamilton circuits "HC3" and "HC4". And so like this, the "NNM" is used on both the left vertex and the right vertex of the remaining edges of the graph. So if there are "n" edges in a complete graph, then "2n" hamilton circuits will be formed. Now find the lowest weight hamilton circuit among the collection of "2n" hamilton circuits (Note :- "2n" means "two" multiplied by "n" ). This will be the minimum weight hamilton circuit which is obtained by using the "MSEM". Now using computers and a using a brute force algorithm, find all the possible hamilton circuits in the graph and find the 100% optimal weight hamilton circuit. Now compare the weight of this hamilton circuit with the minimum weight hamilton circuit obtained by using the "MSEM". As far as possible, the complete graph example should be limited to less than 10 or 20 vertices, in order for the computers to quickly find the 100% optimal hamilton circuit and then use the hamilton circuit to compare with the weight of the hamilton circuit obtained by using the "MSEM". The "starter edge method" algorithm can be used for any number of vertices "n" and the algorithm still works in polynomial time. An accurate number is that for a graph with n number of edges, there will be 2n hamilton circuits for weight calculation and comparison. So only 2n hamilton circuits needs to be processed no matter how large n may be. The brute force algorithm I mentioned above are the different kind of algorithms and software that other scientists might use to get the 100% convincing optimal weight hamilton cirucit or the exact solution, which they can use to compare with the weight of the hamilton circuit that is obtained using my method. In order to avoid confusion about the "MSEM" that I have given above, I will write this algorithm with beginning and an ending tag. Notations used here are the same as given above. [ Beginning of "MSEM" ] Collect all the edges of the graph. Take an individual edge from the collection of edges. This edge consists of a left vertex and a right vertex. Suppose this edge is called "E1". Then from the left vertex apply the "NNM". One hamilton circuit ie:- "HC1" will be formed. Now in "HC1", the edge "E1" will be present ie:- the property of "HC1" is that the edge "E1" will be and must be included in "HC1". Now take the right vertex of "E1" and apply the "NNM" from the right vertex and form a hamilton circuit "HC2". Now again the property of "HC2" is that "E1" will be and must be included in "HC2". So from edge "E1", two hamilton circuits "HC1" and "HC2" are obtained. Now doing the same process for second edge "E2", two hamilton circuits "HC3" and "HC4" are obtained. Here the edge "E2" will be and must be present in both the hamilton circuits "HC3" and "HC4". And so like this, the "NNM" is used on both the left vertex and the right vertex of the remaining edges of the graph. So if there are "n" edges in a complete graph, then "2n" hamilton circuits will be formed. Now find the lowest weight hamilton circuit among the collection of "2n" hamilton circuits (Note :- "2n" means "two" multiplied by "n" ). This will be the minimum weight hamilton circuit which is obtained by using the "MSEM". [ End of "MSEM" ] I mentioned about the time complexity of the "MSEM" above. What I meant to say was that the both "SEM" and "MSEM" are polynomial time methods. So which algorithm (ie:- "SEM" or "MSEM") is more efficient is not important, because the aim of all scientists at the present moment is to find a polynomial time solution for the Travelling Salesman Problem. So for the time being it does not matter whether "SEM" or "MSEM" is used to find the minimum weight hamilton circuit. ( As mentioned above "SEM" denotes "starter edge method" and "MSEM" denotes "modified starter edge method" ) Edited December 7, 2012 by varghese Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now