logging in or signing up TRAVELLING SALESPERSON PROBLEM ankush85 Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 3900 Category: Education License: All Rights Reserved Like it (2) Dislike it (0) Added: March 06, 2009 This Presentation is Public Favorites: 1 Presentation Description No description available. Comments Posting comment... By: gjayakanthan (32 month(s) ago) plz allow me to download this PPT of travelling salesman problem Saving..... Post Reply Close Saving..... Edit Comment Close By: swapnaja_2006 (32 month(s) ago) plz allow me to download this PPT of travelling salesman problem Saving..... Post Reply Close Saving..... Edit Comment Close By: pankajkumar (38 month(s) ago) i want to download this ppt please Saving..... Post Reply Close By: ankush85 (37 month(s) ago) u can download now ... Saving..... Edit Comment Close Premium member Presentation Transcript TRAVELLING SALESPERSON PROBLEM : 1 TRAVELLING SALESPERSON PROBLEM Let G = (V,E) be a directed graph defining an instance of travelling Sales Person Problem Le Cij = cost of edge (i,j), Cij = ? if (i,j) ? E and let ?v ? = n. Assumption : Every tour starts & ends at vertex 1. So, the solution space S = { 1, ?, 1 ? ? is a permutation of (2,3,…..n)}; ?S ? = (n-1) ! TRAVELLING SALESPERSON PROBLEM (Contd..) : 2 TRAVELLING SALESPERSON PROBLEM (Contd..) The size of S may be reduced by restricting S so that (1,i1,i2, ….in-1, 1) ? S iff <ij, ij+1 > ?E, 0 ? j ? n – 1, i0 = in =1. S can be organised into a state space tree. For complete graph with ?V ? = 4, state space tree is as in Figure 1 each leaf node (L) is a solution node & defines a path from root to L. TRAVELLING SALESPERSON PROBLEM (Contd..) : 3 TRAVELLING SALESPERSON PROBLEM (Contd..) 1 2 3 4 2 3 4 3 4 2 4 2 3 5 6 7 8 9 10 4 3 4 2 3 2 11 12 13 14 15 16 Figure 1 TRAVELLING SALESPERSON PROBLEM (Contd..) : 4 TRAVELLING SALESPERSON PROBLEM (Contd..) Node (14) represents tour i0 = 1, i1 = 3, i2 = 4, i3 =2. To use LCBB to search travelling salesperson state space tree, we need to define a cost function c(.) and two other functions c(.) and u(.) such that c(R) ? c(R) ? u(R) ?nodes R. TRAVELLING SALESPERSON PROBLEM (Contd..) : 5 TRAVELLING SALESPERSON PROBLEM (Contd..) The cost c(.) is such that the solution node with least c(.) corresponds to a shortest path/tour in G one choice for c(.) is : C(A) = { length of tour defined by path from root to A, if A is a leaf. Cost of minimum-cost leaf in the sub tree A, if A is not a leaf. c(.) can be obtained by using the reduced cost matrix corresponding to G. TRAVELLING SALESPERSON PROBLEM (Contd..) : 6 TRAVELLING SALESPERSON PROBLEM (Contd..) A row (column) is said to be reduced iff it contains at-least one zero and all remaining entries as non-negative. A Matrix is reduced iff every row and column is reduced. TRAVELLING SALESPERSON PROBLEM - Example : 7 TRAVELLING SALESPERSON PROBLEM - Example Example : Graph with 5 vertices ? 20 30 10 11 15 ? 16 4 2 3 5 ? 2 4 19 6 18 ? 3 16 4 7 16 ? TRAVELLING SALESPERSON PROBLEM (Contd..) : 8 TRAVELLING SALESPERSON PROBLEM (Contd..) Since every tour on this graph includes exactly one edge (i,j) with i = k, 1? k ? 5, and exactly one edge (i,j) with j = k, 1? k ? 5, subtracting a constant t from every entry in one row or one column of the cost matrix reduces the length of every tour by exactly t A minimum-cost tour remains a minimum cost tour following this subtraction operation. TRAVELLING SALESPERSON PROBLEM (Contd..) : 9 TRAVELLING SALESPERSON PROBLEM (Contd..) If t is chosen to be the minimum entry in row i (column j), then subtracting it from all entries in row i (column j) introduces a zero into row i (column j). Repeating this as often as needed, the cost matrix can be reduced. The total amount subtracted from the columns & rows is a lower bound on the length of a minimum-cost tour and can be used as the c value for the root of state space tree. TRAVELLING SALESPERSON PROBLEM (Contd..) : 10 TRAVELLING SALESPERSON PROBLEM (Contd..) ? 10 20 0 1 ? 10 17 0 1 13 ? 14 2 0 12 ? 11 2 0 1 3 ? 0 2 0 3 ? 0 2 16 3 15 ? 0 15 3 12 ? 0 12 0 3 12 ? 5x5 11 0 0 12 ? Subtracting 10,2,2,3,4 from Reduced cost matrix the rows 1,2,3,4,5 Subtracting 1,3 from column 1, column 3. Total amount subtracted = 10+2+2+3+4+1+3 = 25 Hence, all tours in original graph have a length at-least 25. TRAVELLING SALESPERSON PROBLEM (Contd..) : 11 TRAVELLING SALESPERSON PROBLEM (Contd..) Let A be reduced cost matrix for node R. Let S be a child of R such that the tree edge (R,S) corresponds to including edge <i,j> in the tour. If S is not a leaf, then the reduced cost matrix for S may be obtained as follows : 1) Change all entries in row i and column j of A to ?. 2) Set A(j,i) to ?. [This prevents the use of edge < j,i >] TRAVELLING SALESPERSON PROBLEM (Contd..) : 12 TRAVELLING SALESPERSON PROBLEM (Contd..) Reduce all rows & columns in the resulting matrix except for rows & columns containing only ?. Let the resulting matrix be B If r is the total amount subtracted in step (3), then c(S) = c(R) + A (i,j) + r. For leaf nodes, c(.) = c(), as each leaf defines a unique tour For upper bound function U, we can use u(R) = ? for all nodes R. For S not leaf, reduced cost matrix will be TRAVELLING SALESPERSON PROBLEM (Contd..) : 13 TRAVELLING SALESPERSON PROBLEM (Contd..) ? ? ? ? ? ? ? ? ? ? 12 ? 11 2 0 ? ? 11 2 0 0 ? ? 0 2 0 ? ? 0 2 15 ? 12 ? 0 15 ? 12 ? 0 11 ? 0 12 ? 11 ? 0 12 ? (i) (ii) iii) No further reduction required as each row & column has a zero. TRAVELLING SALESPERSON PROBLEM (Contd..) : 14 TRAVELLING SALESPERSON PROBLEM (Contd..) c(S) = c(R) + A (i,j) + r = 25 + 10 + 0 = 35 Similarly finding other reduced cost matrices, we obtain the tour length for solution node 11 is c(11) = 28 & U is updated to 28. For the next node 5, c(S) = 31 > U. Hence LCBB terminates with 1,4,2,5,3,1 as the shortest length tour. TRAVELLING SALESPERSON PROBLEM (Contd..) : 15 TRAVELLING SALESPERSON PROBLEM (Contd..) 25 1 2 3 4 5 35 2 53 3 25 4 5 31 2 3 5 28 6 50 7 8 36 3 5 52 9 10 28 3 11 28 Fig. 4 DYNAMIC STATE SPACE TREE ORGANISATION : 16 DYNAMIC STATE SPACE TREE ORGANISATION If G = (V,E) has e edges then every tour contains exactly ‘n’ of the ‘e’ edges. For each i, 1 ? i ? n there is exactly one edge of the form (i,j) and one of the form (k,i) in every tour. A possible organisation for the state space tree is a binary tree. - a left branch represents the inclusion of a particular edge while the right branch represents the exclusion of that edge. DYNAMIC STATE SPACE TREE ORGANISATION (Contd..) : 17 DYNAMIC STATE SPACE TREE ORGANISATION (Contd..) If edge <i,j> is used then the left sub-tree of the root will represent all tours including edge <i,j> & the right sub tree will represent all tours that do not include edge <i,j>. If an optimal tour is included in the left sub tree then only (n-1) edges need to be selected. If all optimal tours lie in the right sub tree then we have still to select n edges. DYNAMIC STATE SPACE TREE ORGANISATION (Contd..) : 18 DYNAMIC STATE SPACE TREE ORGANISATION (Contd..) Since the left sub tree selects fewer edges, it should be easier to find an optimal solution in it than to find one in the right sub tree. Selection Rule for edges : Select that edge which results in a right sub tree that has highest c value. Dynamic State Space Tree Organisation - example : 19 Dynamic State Space Tree Organisation - example Consider the reduced cost matrix. The fact, that all tours have a length at-least 25, is represented by the root of state space tree. At the root node, we have to determine an edge <i,j> that will maximize the c value of the right sub tree. If we select an edge <i,j> whose cost in reduced matrix is positive, then the c value of the right sub tree will remain 25 Dynamic State Space Tree Organisation – example (Contd..) : 20 Dynamic State Space Tree Organisation – example (Contd..) 1 2 3 4 5 ? 10 17 0 1 12 ? 11 2 0 0 3 ? 0 2 15 3 12 ? 0 11 0 0 12 ? Dynamic State Space Tree Organisation – example (Contd..) : 21 Dynamic State Space Tree Organisation – example (Contd..) This is because the reduced matrix for right sub-tree will have cost (i, j) = ? & all other entries are identical. Hence, B will be reduced and c cannot increase. So, we must choose an edge with reduced cost 0. Once this is chosen, the cost of the edge will be set to ? and the matrix may not be reduced. To reduce the matrix again some amount is to be subtracted and it is to be added to the c value. Thus the c value may increase Dynamic State Space Tree Organisation – example (Contd..) : 22 Dynamic State Space Tree Organisation – example (Contd..) If A is the reduced cost matrix for node R, then the selection of edge <i,j> (A(i,j) = 0) as the next partitioning edge will increase the c of the right sub-tree by ? = min k?j { A (i,k) } + min k?i{ A(k,j) } as this much needs to be subtracted from row i & column j to introduce a zero into both. Dynamic State Space Tree Organisation – example (Contd..) : 23 Dynamic State Space Tree Organisation – example (Contd..) For edges <1,4), <2,5>, <3,1>, <3,4>, <4,5>, <5,2>, & <5,3>. ? = 1, 2, 11, 0, 3, 3 & 11 So, either of edges <3,1> or <5,3> can be used. Let us assume that LCBB selects edge <3,1> c(2) can be computed in a manner similar to static state space tree. The reduced matrices are : Dynamic State Space Tree Organisation – example (Contd..) : 24 Dynamic State Space Tree Organisation – example (Contd..) 1 2 3 4 5 1 ? 10 ? 0 1 ? 10 17 0 1 2 ? ? 11 2 0 1 12-11=1 ? 11 2 0 3 ? ? ? ? ? ? 3 ? 0 2 4 ? 3 12 ? 0 4 15-11=4 3 12 ? 0 5 ? 0 0 12 ? 0 11-11=0 0 0 12 ? (i) node 2 (ii) node 3 iii) No further reduction required as each row & column has a zero. Dynamic State Space Tree Organisation – example (Contd..) : 25 Dynamic State Space Tree Organisation – example (Contd..) 25 1 include <3,1> exclude <3,1> 25 2 3 36 Same as include <5,3> exclude <5,3> 28 4 5 36 include <1,4> exclude <1,4> 28 6 7 37 Dynamic State Space Tree Organisation – example : 26 Dynamic State Space Tree Organisation – example The edge selection at node 6 is { <3,1>, <5,3>, (1,4>} This corresponds to path 5,3,1,4. At this point 3 of 5 edges have been selected. The remaining 2 may be selected directly. The only possibility is {<4,2>, <2,5> }. This gives the path 5,3,1,4,2,5 with length 28. So u = 28. Next node 3 has c(3) > u. So, LCBB terminates. Computed cost (Node 4) = 25+0+3 = 28. You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.
TRAVELLING SALESPERSON PROBLEM ankush85 Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 3900 Category: Education License: All Rights Reserved Like it (2) Dislike it (0) Added: March 06, 2009 This Presentation is Public Favorites: 1 Presentation Description No description available. Comments Posting comment... By: gjayakanthan (32 month(s) ago) plz allow me to download this PPT of travelling salesman problem Saving..... Post Reply Close Saving..... Edit Comment Close By: swapnaja_2006 (32 month(s) ago) plz allow me to download this PPT of travelling salesman problem Saving..... Post Reply Close Saving..... Edit Comment Close By: pankajkumar (38 month(s) ago) i want to download this ppt please Saving..... Post Reply Close By: ankush85 (37 month(s) ago) u can download now ... Saving..... Edit Comment Close Premium member Presentation Transcript TRAVELLING SALESPERSON PROBLEM : 1 TRAVELLING SALESPERSON PROBLEM Let G = (V,E) be a directed graph defining an instance of travelling Sales Person Problem Le Cij = cost of edge (i,j), Cij = ? if (i,j) ? E and let ?v ? = n. Assumption : Every tour starts & ends at vertex 1. So, the solution space S = { 1, ?, 1 ? ? is a permutation of (2,3,…..n)}; ?S ? = (n-1) ! TRAVELLING SALESPERSON PROBLEM (Contd..) : 2 TRAVELLING SALESPERSON PROBLEM (Contd..) The size of S may be reduced by restricting S so that (1,i1,i2, ….in-1, 1) ? S iff <ij, ij+1 > ?E, 0 ? j ? n – 1, i0 = in =1. S can be organised into a state space tree. For complete graph with ?V ? = 4, state space tree is as in Figure 1 each leaf node (L) is a solution node & defines a path from root to L. TRAVELLING SALESPERSON PROBLEM (Contd..) : 3 TRAVELLING SALESPERSON PROBLEM (Contd..) 1 2 3 4 2 3 4 3 4 2 4 2 3 5 6 7 8 9 10 4 3 4 2 3 2 11 12 13 14 15 16 Figure 1 TRAVELLING SALESPERSON PROBLEM (Contd..) : 4 TRAVELLING SALESPERSON PROBLEM (Contd..) Node (14) represents tour i0 = 1, i1 = 3, i2 = 4, i3 =2. To use LCBB to search travelling salesperson state space tree, we need to define a cost function c(.) and two other functions c(.) and u(.) such that c(R) ? c(R) ? u(R) ?nodes R. TRAVELLING SALESPERSON PROBLEM (Contd..) : 5 TRAVELLING SALESPERSON PROBLEM (Contd..) The cost c(.) is such that the solution node with least c(.) corresponds to a shortest path/tour in G one choice for c(.) is : C(A) = { length of tour defined by path from root to A, if A is a leaf. Cost of minimum-cost leaf in the sub tree A, if A is not a leaf. c(.) can be obtained by using the reduced cost matrix corresponding to G. TRAVELLING SALESPERSON PROBLEM (Contd..) : 6 TRAVELLING SALESPERSON PROBLEM (Contd..) A row (column) is said to be reduced iff it contains at-least one zero and all remaining entries as non-negative. A Matrix is reduced iff every row and column is reduced. TRAVELLING SALESPERSON PROBLEM - Example : 7 TRAVELLING SALESPERSON PROBLEM - Example Example : Graph with 5 vertices ? 20 30 10 11 15 ? 16 4 2 3 5 ? 2 4 19 6 18 ? 3 16 4 7 16 ? TRAVELLING SALESPERSON PROBLEM (Contd..) : 8 TRAVELLING SALESPERSON PROBLEM (Contd..) Since every tour on this graph includes exactly one edge (i,j) with i = k, 1? k ? 5, and exactly one edge (i,j) with j = k, 1? k ? 5, subtracting a constant t from every entry in one row or one column of the cost matrix reduces the length of every tour by exactly t A minimum-cost tour remains a minimum cost tour following this subtraction operation. TRAVELLING SALESPERSON PROBLEM (Contd..) : 9 TRAVELLING SALESPERSON PROBLEM (Contd..) If t is chosen to be the minimum entry in row i (column j), then subtracting it from all entries in row i (column j) introduces a zero into row i (column j). Repeating this as often as needed, the cost matrix can be reduced. The total amount subtracted from the columns & rows is a lower bound on the length of a minimum-cost tour and can be used as the c value for the root of state space tree. TRAVELLING SALESPERSON PROBLEM (Contd..) : 10 TRAVELLING SALESPERSON PROBLEM (Contd..) ? 10 20 0 1 ? 10 17 0 1 13 ? 14 2 0 12 ? 11 2 0 1 3 ? 0 2 0 3 ? 0 2 16 3 15 ? 0 15 3 12 ? 0 12 0 3 12 ? 5x5 11 0 0 12 ? Subtracting 10,2,2,3,4 from Reduced cost matrix the rows 1,2,3,4,5 Subtracting 1,3 from column 1, column 3. Total amount subtracted = 10+2+2+3+4+1+3 = 25 Hence, all tours in original graph have a length at-least 25. TRAVELLING SALESPERSON PROBLEM (Contd..) : 11 TRAVELLING SALESPERSON PROBLEM (Contd..) Let A be reduced cost matrix for node R. Let S be a child of R such that the tree edge (R,S) corresponds to including edge <i,j> in the tour. If S is not a leaf, then the reduced cost matrix for S may be obtained as follows : 1) Change all entries in row i and column j of A to ?. 2) Set A(j,i) to ?. [This prevents the use of edge < j,i >] TRAVELLING SALESPERSON PROBLEM (Contd..) : 12 TRAVELLING SALESPERSON PROBLEM (Contd..) Reduce all rows & columns in the resulting matrix except for rows & columns containing only ?. Let the resulting matrix be B If r is the total amount subtracted in step (3), then c(S) = c(R) + A (i,j) + r. For leaf nodes, c(.) = c(), as each leaf defines a unique tour For upper bound function U, we can use u(R) = ? for all nodes R. For S not leaf, reduced cost matrix will be TRAVELLING SALESPERSON PROBLEM (Contd..) : 13 TRAVELLING SALESPERSON PROBLEM (Contd..) ? ? ? ? ? ? ? ? ? ? 12 ? 11 2 0 ? ? 11 2 0 0 ? ? 0 2 0 ? ? 0 2 15 ? 12 ? 0 15 ? 12 ? 0 11 ? 0 12 ? 11 ? 0 12 ? (i) (ii) iii) No further reduction required as each row & column has a zero. TRAVELLING SALESPERSON PROBLEM (Contd..) : 14 TRAVELLING SALESPERSON PROBLEM (Contd..) c(S) = c(R) + A (i,j) + r = 25 + 10 + 0 = 35 Similarly finding other reduced cost matrices, we obtain the tour length for solution node 11 is c(11) = 28 & U is updated to 28. For the next node 5, c(S) = 31 > U. Hence LCBB terminates with 1,4,2,5,3,1 as the shortest length tour. TRAVELLING SALESPERSON PROBLEM (Contd..) : 15 TRAVELLING SALESPERSON PROBLEM (Contd..) 25 1 2 3 4 5 35 2 53 3 25 4 5 31 2 3 5 28 6 50 7 8 36 3 5 52 9 10 28 3 11 28 Fig. 4 DYNAMIC STATE SPACE TREE ORGANISATION : 16 DYNAMIC STATE SPACE TREE ORGANISATION If G = (V,E) has e edges then every tour contains exactly ‘n’ of the ‘e’ edges. For each i, 1 ? i ? n there is exactly one edge of the form (i,j) and one of the form (k,i) in every tour. A possible organisation for the state space tree is a binary tree. - a left branch represents the inclusion of a particular edge while the right branch represents the exclusion of that edge. DYNAMIC STATE SPACE TREE ORGANISATION (Contd..) : 17 DYNAMIC STATE SPACE TREE ORGANISATION (Contd..) If edge <i,j> is used then the left sub-tree of the root will represent all tours including edge <i,j> & the right sub tree will represent all tours that do not include edge <i,j>. If an optimal tour is included in the left sub tree then only (n-1) edges need to be selected. If all optimal tours lie in the right sub tree then we have still to select n edges. DYNAMIC STATE SPACE TREE ORGANISATION (Contd..) : 18 DYNAMIC STATE SPACE TREE ORGANISATION (Contd..) Since the left sub tree selects fewer edges, it should be easier to find an optimal solution in it than to find one in the right sub tree. Selection Rule for edges : Select that edge which results in a right sub tree that has highest c value. Dynamic State Space Tree Organisation - example : 19 Dynamic State Space Tree Organisation - example Consider the reduced cost matrix. The fact, that all tours have a length at-least 25, is represented by the root of state space tree. At the root node, we have to determine an edge <i,j> that will maximize the c value of the right sub tree. If we select an edge <i,j> whose cost in reduced matrix is positive, then the c value of the right sub tree will remain 25 Dynamic State Space Tree Organisation – example (Contd..) : 20 Dynamic State Space Tree Organisation – example (Contd..) 1 2 3 4 5 ? 10 17 0 1 12 ? 11 2 0 0 3 ? 0 2 15 3 12 ? 0 11 0 0 12 ? Dynamic State Space Tree Organisation – example (Contd..) : 21 Dynamic State Space Tree Organisation – example (Contd..) This is because the reduced matrix for right sub-tree will have cost (i, j) = ? & all other entries are identical. Hence, B will be reduced and c cannot increase. So, we must choose an edge with reduced cost 0. Once this is chosen, the cost of the edge will be set to ? and the matrix may not be reduced. To reduce the matrix again some amount is to be subtracted and it is to be added to the c value. Thus the c value may increase Dynamic State Space Tree Organisation – example (Contd..) : 22 Dynamic State Space Tree Organisation – example (Contd..) If A is the reduced cost matrix for node R, then the selection of edge <i,j> (A(i,j) = 0) as the next partitioning edge will increase the c of the right sub-tree by ? = min k?j { A (i,k) } + min k?i{ A(k,j) } as this much needs to be subtracted from row i & column j to introduce a zero into both. Dynamic State Space Tree Organisation – example (Contd..) : 23 Dynamic State Space Tree Organisation – example (Contd..) For edges <1,4), <2,5>, <3,1>, <3,4>, <4,5>, <5,2>, & <5,3>. ? = 1, 2, 11, 0, 3, 3 & 11 So, either of edges <3,1> or <5,3> can be used. Let us assume that LCBB selects edge <3,1> c(2) can be computed in a manner similar to static state space tree. The reduced matrices are : Dynamic State Space Tree Organisation – example (Contd..) : 24 Dynamic State Space Tree Organisation – example (Contd..) 1 2 3 4 5 1 ? 10 ? 0 1 ? 10 17 0 1 2 ? ? 11 2 0 1 12-11=1 ? 11 2 0 3 ? ? ? ? ? ? 3 ? 0 2 4 ? 3 12 ? 0 4 15-11=4 3 12 ? 0 5 ? 0 0 12 ? 0 11-11=0 0 0 12 ? (i) node 2 (ii) node 3 iii) No further reduction required as each row & column has a zero. Dynamic State Space Tree Organisation – example (Contd..) : 25 Dynamic State Space Tree Organisation – example (Contd..) 25 1 include <3,1> exclude <3,1> 25 2 3 36 Same as include <5,3> exclude <5,3> 28 4 5 36 include <1,4> exclude <1,4> 28 6 7 37 Dynamic State Space Tree Organisation – example : 26 Dynamic State Space Tree Organisation – example The edge selection at node 6 is { <3,1>, <5,3>, (1,4>} This corresponds to path 5,3,1,4. At this point 3 of 5 edges have been selected. The remaining 2 may be selected directly. The only possibility is {<4,2>, <2,5> }. This gives the path 5,3,1,4,2,5 with length 28. So u = 28. Next node 3 has c(3) > u. So, LCBB terminates. Computed cost (Node 4) = 25+0+3 = 28.