Chapter 6 Traveling Salesman Problem

• Section 6.1: Hamilton Circuits and Hamilton Paths HAMILTON CIRCUITS AND PATHS • HAMILTON = Touch each VERTEX exactly one time (enter/ leave once). EULER CIRCUITS AND PATHS EULER = touch each EDGE of a graph exactly one time. • By Definition: must touch every vertex “can touch more than once depending on degree” • By Definition: Doesn’t require touching every edge HAMILTON Circuits/Paths VERSUS EULER Circuits/Paths For each of the following graphs, use our definitions of Hamilton and Euler to determine if circuits and paths of each type are possible. Graph 1 Graph 3 Graph 4 Graph 5 Graph 6 EULER PATH NO Graph 2 EULER CIRCUIT YES NO NO YES NO NO YES YES YES YES NO YES YES NO YES NO NO NO HAMILTON PATH HAMILTON CIRCUIT YES NO NO YES NO What do you notice about the relationship between a graph having an Euler Circuit or Path and having a Hamilton Circuit of path? There is no relationship IN GENERAL, THERE ARE NO THEOREMS TO DETERMINE IF A GRAPH HAS A HAMILTON PATH OR CIRCUIT. HELPFUL HINT: #1: FOR HAMILTON CIRCUITS/ PATHS, VERTICES OF DEGREE 1 OR 2 ARE VERY HELPFUL BECAUSE THEY REPRESENT REQUIRED EDGES TO REACH THAT VERTEX. #2: EXAMPLE: Hamilton Circuit = A, B, C, D, A SHIFT/SAME Hamilton Circuits: Follows the SAME rotation order for a circuit, but with a different start. B, C, D, A, B C, D, A, B, C D, A, B, C, D A B D C DISTINCT Hamilton Circuits: A different order of vertices (Left to Right) from the same starting vertex. (reverse order counts) A, D, C, B, A (reverse order) A, D, B, C, A AND reverse = A, C, B, D, A A, B, D, C, A AND reverse = A, C, D, B, A EXAMPLE #1: List all possible Hamiltonian circuits in the following graph A B 1. A, B, C, D, E, F, G, A 2. A, B, E, D, C, F, G, A 3. A, F, C, D, C, B, G, A 4. A, F, E, D, C, B, G, A REVERSE EACH ONE OF THESE 4 CIRCUITS C D G F E What about the Hamiltonian circuits that start at B, C, D, etc.? Well, since such a circuit must pass through all of the vertices it doesn’t matter which vertex we start with. Related to the idea of shifts of circuits. EXAMPLE #2: (a) Find a Hamiltonian path that begins at A and ends at E. (b) Find a Hamiltonian circuit that starts at A and ends with the pair of vertices E, A. (c) Find a Hamiltonian path that begins at F and ends at G. A D E F B G (a) A, F, B, C, G, D, E (b) A, F, B, C, G, D, E, A (c) F, B, C, E, A, D, G F, A, E, B, C, D, G C Example 3: The following graph has no Hamiltonian circuits or paths--why not? 4 bridges exist = can’t have a circuit; No path possible because multiple vertices of degree 1 EXAMPLE #4: (a) Find all Hamiltonian circuits that starts at A. (b) Find all Hamiltonian circuits that starts at D. (c) Explain why your answers in a and b must have the same number of circuits. (a) A, C, F, D, E, B, A A, D, F, E, B, C, A A, D, E, F, C, B, A (REVERSE ORDER as well) (b) Re-order answers in part a (c) Re-ordering concept A D F C E B Section 6.2: Complete Graphs EXAMPLE PUT 6 OR 8 DOTS ON WHITEBOARD AND START CONNECTING THEM AND ASK STUDENTS TO DESCRIBE HOW I AM MAKING THE GRAPH: “ONE DOT IS CONNECTED TO EVERY OTHER DOT” TO START DEFINITION COMPLETE GRAPH: A graph in which every pair of distinct vertices is joined by exactly one edge. o Notation: KN = a complete graph of N vertices EXAMPLES OF COMPLETE GRAPHS for 3, 4, and 5 vertices: K3 K4 K5 Use the definition of a complete graph to answer the following questions: 1. Does a complete graph have to be connected? 2. Is a complete graph allowed to have loops? YES; “every pair of vertices connected by an edge” NO; “Distinct (Different) Vertices only” 3. Is a complete graph allowed to have multiple edges? 4. Can different vertices have different degree? NO; exactly “one edge” NO; each vertex must be connected all remaining vertices What is the DEGREE of each VERTEX for N vertices? K3: Degree = 2 K4: Degree = 3 K5: Degree = 4 1 Less than the # of vertices Degree = N - 1 How many EDGES are in KN (complete graph of N vertices)? What is the relationship between edges and degrees? EDGES TOTAL DEGREE K3: EDGES = 3 6 = 3*2 Euler’s Sum of Degree Theorem: (total # of degrees) = 2 * (# of edges) K4: EDGES = 6 12 = 4*3 N(N-1) = 2 * (# of edges) K5: EDGES = 10 20 = 5*4 K6: EDGES = 15 30 = 6*5 • N ( N − 1) = number of edges in KN 2 Where have you seen this formula before? Chapter 1: the number of pairwise comparisons. DEGREE and VERTICES are consecutive numbers. Complete Graph KN SUMMARY OF COMPLETE GRAPH INFORMATION Number of Vertices Degree of Each Vertex N N–1 Connected Graph, No Loops, No Multiple Edges Number of Edges N ( N − 1) = 2 K3= Complete Graph of 4 Vertices 1) How many Hamiltonian circuits does it have? A 2 B 1 A, B, C, A 2 A, C, B, A K4 = Complete Graph of 4 Vertices 1) How many Hamiltonian circuits does it have? 1 A, B, C, D, A 6 A B C K3 C K4 D 2 3 4 5 6 A, B, D, C, A A, C, B, D, A A, C, D, B, A A, D, B, C, A A, D, C, B, A If we were to answer the same questions for K5 we would find the following: 1) How many Hamiltonian circuits does it have? (Do you notice any possible relation in how we answered this question for K3 and K4 that might help you here?) (5 - 1) (5 - 2) ( 5 - 3) (5 - 4) = (4)(3)(2)(1) = 24 (see page 202 for exact circuits) How many DISTINCT HAMILTON CIRCUITS are in KN? Complete Graph K3: K4: K5: K6: Vertices 3 4 5 6 Hamilton Circuits 2 6 24 120 (N – 1)! = (Degree) != Distinct Hamilton Circuits in KN. Calculator Command Reminder: [MATH] – [PRB] – [4:!] INDEPENDENT PRACTICE: Apply the Properties of Complete Graphs (1) How many edges are there in K20? 20(19)/2 = 190 edges (2) How many distinct Hamilton Circuits exist in K10? (10 – 1)! = 9! = 362880 (3) How many vertices are in the K50 graph? N = 50 (4) What is the degree of every vertex in K200? Degree = 200-1 = 199 (5) How many distinct Hamilton Circuits exist in K22? (22 – 1)! = 21! Or 5.109094217E19 (6) How many edges are there in K32? Edges = (32)(32 – 1)/2 = 496 edges (7) What is the degree of every vertex in K15? Degree = 15 – 1 = 14 (8) If KN has 120 distinct Hamiltonian circuits then what is N? N=6 Trial and Error: Divide 120 by consecutive numbers starting with 2 Add one to last number used = Number of vertices (9) If KN has 55 edges then what is N? N = 11 55 = (N)(N-1)/2; HINT: square root trick of DOUBLE EDGES round up = N and round down = N -1 (10) If the number of edges of K12 is x and the number of edges of K13 is y, what is the values of y - x? (13)(12)/2 - (12)(11)/ 2 = (12/2) (13-11) = 12 (11) For each of the following cases find the value of N. a. KN has 5040 distinct Hamilton Circuits. 5040 = 7!; N = 7 + 1 = 8 b. KN has 66 edges. 66 = 12*11/2; N = 12 c. KN has 80,200 edges. 80,200 = 401*400/2; N = 401 (12) If KN has 362,880 distinct Hamilton Circuits, then… 362,880 = 6!; N = 7 a. How many vertices are in the KN graph? 7 VERTICES b. What is the degree of each vertex are in the KN graph? 7 -1 = 6 c. How many edges are in the KN graph?7*6/2 = 21 edges Section 6.3: Traveling Salesman Problems WEIGHTED GRAPH: Any graph whose edges have numbers associated or assigned to them (NOT DRAWN TO SCALE ALWAYS) o Weights: number for each edge o Examples of Weights: distance, time, cost… Complete Weighted Graph: Complete graph that has weights associated with it TRAVELING SALESMAN PROBLEMS: From home, the traveling salesman must visit different destinations to sell goods and return home. This is essentially finding a Hamilton Circuit. GOAL: Try to find the cheapest, most efficient, optimal route that is a Hamilton circuit for a given graph (find the least total weight) Example – The Simpsons: Homer Simpson he has to run errands at the Kwik-E-Mart, the Retirement Home and Moe`s. Assuming that he wants to begin and end his day at home find the route that will allow him to get back to napping as soon as possible. A 20 12 The numbers will represent the number of blocks between each destination. D 8 15 When we place values like this on the edges of a graph we refer to them as the weights of the edges. 17 20 B C What if Homer preferred going to see Grandpa first to get it out of the way? A–B–C–D–A A-B-D-C- A 12 + 20 + 17 + 8 = 57 BLOCKS 12+15+17+20 = 64 BLOCKS What if Homer preferred going to the KWIK-E-MART last? A-B-D-C- A A–D–B–C–A 12+15+17+20 = 64 BLOCKS 8 +15 + 20 + 20 = 63 BLOCKS Traveling Salesman Problem Steps: (1) Create graph models (2) Apply weights to these models (3) Find optimal Hamilton Circuits. (Not Always a practical statement) REAL-LIFE EXAMPLES: 1) Routing School Buses 2) Package Deliveries: UPS or FedEx Delivery Truck 3) Running Errands around Town 4) Planning a road trip 5) Grocery Shopping: Planning which aisles you need to go down Section 6.4 and 6.5: Simple Algorithms for Solving Traveling Salesman Problems Strategy #1: BRUTE FORCE (Exhaustive Search) Circuit A, B, C, D, A Mirror Image A, D, C, B, A A, B, D, C, A A, C, D, B, A A, C, B, D, A A, D, B, C, A Weight 13 + 9 + 14 + 15 = 51 13 + 16 + 14 + 12 = 55 12 + 9 + 16 + 15 = 52 15 A 13 12 B D 16 14 9 BRUTE-FORCE ALGORITHM Step 1: Make a list of ALL distinct Hamilton circuits of the graph from ONE starting vertex Step 2: Calculate its TOTAL WEIGHT for each circuit. Step 3: Choose an OPTIMAL circuit. (There is always more than one optimal circuit because of mirrorimages) PRO: Guarantee Optimal Hamilton Circuit CON: INEFFICIENT ALGORITHM # steps needed to carry out algorithm grows disproportionately with the size of population (vertices) ie TAKES A LOT OF TIME the more vertices/ edges there are STRATEGY #2: NEAREST – NEIGHBOR ALGORITHM From the start vertex, go to the vertex that is the shortest to get to. From each new vertex go to the next new city that is the shortest to get to. When there are no more new vertices to go to, go to the starting vertex. A (12) C (9) B (16) D (15) A = 52 NEAREST-NEIGHBOR ALGORITHM Start: Start at the designated starting vertex (home). If there is no designated starting vertex, pick any vertex. Step 1: From the starting vertex go to its NEAREST NEIGHBOR (vertex that is the smallest weight away) Middle Steps: From each vertex go to its nearest neighbor that hasn’t already been visited. (smallest remaining weight of possible vertices) Keep doing this until all the vertices have been visited. Last Step: From the last neighbor (vertex) RETURN to the starting vertex (home). PRO: EFFICIENT ALGORITHM Amount of computational effort required to implement it grows in some reasonable proportion with the size of population (vertices) ie WORKS FAST/ LESS TIME CONSUMING TO COMPLETE METHOD CON: Not an optimal Algorithm; Answers won’t always be the OPTIMAL, but relatively close to being the best possible way C A weighted Graph may also be represented as table. Vertices along the first row and column. Weights on the interior of table. A B C D A 8 D A AB = 12 AC = 20 AD = 8 B BA = 12 BC = 20 BD = 15 C CA = 20 CB = 20 D DA = 8 DB = 15 DC = 17 CD = 17 12 B 20 15 17 20 Observations: 1) Diagonal is blank because NO LOOPS exist. 2) Upper Right Triangle and Lower Left Triangle are Identical Numbers a. Represent Same Edges, but are in different order of starting and ending vertices Draw the following complete weighted graph described by table: A B C D E A B 3 3 4 5 5 7 6 9 C D E 4 5 6 5 7 9 6 8 6 1 8 1 FIND THE NEAREST NEIGHBOR SOLUTION STARTING AT D: D (1) E (6) A (3) B (5) C (6) D = 21 C The following Complete Weighted Graph can also be represented by the table: A A B C D E F G 75 50 28 35 15 22 30 60 80 65 50 40 48 35 28 20 30 29 40 32 B 75 C 50 30 D 28 60 40 E 35 80 48 20 F 15 65 35 30 40 G 22 50 28 29 32 13 13 B 30 C 40 60 50 48 35 75 A 65 28 28 22 35 50 29 D 32 30 20 15 80 E 40 G 13 F Does BRUTE FORCE seem practical here? NO; (7-1)!= 720 POSSIBLE HAMILTON CIRCUITS Start at Vertex A – Find the NEAREST NEIGHBOR SOLUTION: (Use table or graph) A – (15) – F – (13) – G – (28) – C – (30) – B – (60) – D – (20) - E – (35) - A = 201 Section 6.7: Repetitive Nearest-Neighbor Algorithm The Nearest Neighbor Algorithm is an EFFICIENT but NOT always ACCURATE algorithm. • Is there a way we can improve it because we like its efficiency? Compare from different starting spots The REPETITIVE Nearest-Neighbor Algorithm: • Perform the Nearest-Neighbor Algorithm for every vertex of the graph as the starting vertex. • Compare circuits and CHOOSE the circuit with least weight of all the options. o If needed, Re-order (shift) that Hamilton Circuit to have the DESIGNATED START vertex first. o Re-ordered (shifted) circuits have the same weight but change its starting vertex EXP #1: Perform the nearest neighbor algorithm for start of A. 10 A 9 B 15 D 13 17 A: A, B, D, C, A = 9 + 13 + 11+ 15 = 48 B: B, A, D, C, B = 9 + 10 + 11 + 17 = 47 11 C: C, D, A, B, C = 11 + 10 + 9 + 17 = 47 C D: D, A, B, C, D = 10 + 9 + 17 + 11 = 47 Final Answer: A,B,C,D,A or A,D,C,B,A = 47 EXAMPLE #2: Label the graph and complete the Repetitive nearest neighbor algorithm for a start of C. A E B ACEDBA = $773 C A B C D E A $185 $119 $152 $133 D B C $185 $119 $121 $121 $150 $174 $200 $120 BCAEDB = $722 CAEDBC = $722 (Final) D E $152 $133 $150 $200 $174 $120 $199 $199 DBCAED = $722 ECADBE = $741 EXAMPLE #3: Perform repetitive nearest neighbor algorithm for a start of B. A B C D E F G A 75 50 28 35 15 22 B C 75 50 30 30 60 40 80 48 65 35 50 28 D E F G 28 35 15 22 60 80 65 50 40 48 35 28 20 30 29 20 40 32 30 40 13 29 32 13 Final: shift A Answer B, D, E, A, F, G, C, B B, C, G, F, A, E, D, B START with A: a,f,g,c,b,d,e,a 201 = 5+13+28+30+60+20+35 START with B: b,c,g,f,a,d,e,b 214 =30+28+13+15+28+20+80 START with C: c,g,f,a,d,e,b,c 214 =28+13+15+28+20+80+30 START with D: d,e,a,f,g,c,b,d 221=20+35+15+13+28+50+60 START with E: e,d,a,f,g,c,b,e 214= 20+28+15+13+28+30+80 START with F: f,a,g,d,e,c,b,f 229 =15+22+29+20+48+30+65 START with G: g,f,a,d,e,c,b,g 204=13+15+28+20+48+30+50 Section 6.8: Cheapest-Link Algorithm GOAL: Piece together a Hamilton circuit by individual edges or “LINKS” of graph trying to choose the smallest or “cheapest” weights first. The Cheapest-Link Algorithm for N Vertices: • Step #1: Pick the edge with the smallest weight first. Mark the edge (or otherwise note that you have chosen it). o Smallest weight ANYWHERE on the graph • Step #2: Pick the next ‘cheapest’ edge anywhere in the graph. Mark or note it. • Step #3, …, N-1:Continue picking the ‘cheapest’ available edge in the graph and as long as (a) it does not close a circuit and (b) it does not result in three edges coming out of a single vertex. (DEGREE = 2) (c) Ties can be broken at random and don’t break the two rules  HINT: Draw out the edges chosen helps to double check what is and is not available. • Step #N: Connect the last two vertices to close the circuit (you are forced to choose this edge so no need for “cheapest”) REORDER CIRCUIT TO THE NECESSARY STARTING VERTEX (N Vertices = N edges chosen for circuit) EXAMPLE #1: Start at G C C 40 48 30 60 50 35 B 65 B 75 28 28 A A 35 29 DD 30 20 E E 40 50 32 15 G 80 22 FF 13 G When table only, draw links to visualize circuit. A B C D E F G A B 75 75 50 30 28 60 35 80 15 65 22 50 C D E F 50 28 35 15 30 60 80 65 40 48 35 40 20 30 48 20 40 35 30 40 28 29 32 13 START IT AT G: G G 22 50 28 29 32 13 – F – A – D – E – C – B – G = 13 + 15 + 28 + 20 + 48 + 30 + 50 = 204 EXAMPLE #2: Start at B A 12 E 19 24 B 17 21 19 D 29 9 Start at B: B, A, E, C, D, B B, D, C, E, A, B 27 C EXAMPLE #3: Start at D A B C D A $185 $119 $152 B $185 $121 $150 C $119 $121 $174 D $152 $150 $174 E $133 $200 $120 $199 E $133 $200 $120 $199 A – C = 119 E – C = 120 B – D = 150 A – D = 152 E – B = 200 741 = total cost Start at D: D, A, C, E, B, D or D, B, E, C, A, D