{"id":2699,"date":"2023-05-12T18:49:11","date_gmt":"2023-05-12T18:49:11","guid":{"rendered":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/?post_type=chapter&#038;p=2699"},"modified":"2025-08-29T04:43:34","modified_gmt":"2025-08-29T04:43:34","slug":"euler-and-hamiltonian-paths-and-circuits-learn-it-4","status":"web-only","type":"chapter","link":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/chapter\/euler-and-hamiltonian-paths-and-circuits-learn-it-4\/","title":{"raw":"Euler and Hamiltonian Paths and Circuits: Learn It 4","rendered":"Euler and Hamiltonian Paths and Circuits: Learn It 4"},"content":{"raw":"<p>With Hamiltonian circuits, our focus will not be on existence, but on the question of optimization; given a graph where the edges have weights, can we find the optimal Hamiltonian circuit; the one with lowest total weight.<\/p>\r\n<p>This problem is called the <strong>Traveling salesperson problem<\/strong> (TSP) because the question can be framed like this: Suppose a salesperson needs to give sales pitches in four cities. They looks up the airfares between each city, and put the costs in a graph. The salesperson needs to figure out what order they should travel to visit each city once then return home with the lowest cost?<\/p>\r\n<p>To answer this question of how to find the lowest cost Hamiltonian circuit, we will consider some possible approaches.<\/p>\r\n<h2>Brute Force Algorithm<\/h2>\r\n<p>The first option that might come to mind is to just try all different possible circuits. We call this the <strong>brute force algorithm<\/strong>.<\/p>\r\n<section class=\"textbox questionHelp\">\r\n<p><strong>How To: Brute Force Algorithm (a.k.a. exhaustive search)<\/strong><\/p>\r\n<ol style=\"list-style-type: decimal;\">\r\n\t<li>List all possible Hamiltonian circuits<\/li>\r\n\t<li>Find the length of each circuit by adding the edge weights<\/li>\r\n\t<li>Select the circuit with minimal total weight.<\/li>\r\n<\/ol>\r\n<\/section>\r\n<section class=\"textbox example\">Apply the Brute force algorithm to find the minimum cost Hamiltonian circuit on the graph below.<center><img class=\"aligncenter wp-image-6229 size-full\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/07165127\/HamiltonianCircuit-1.png\" alt=\"Triangular graph with 4 vertices and 6 edges. The outer vertices of the triangle are labeled A, B, and C, and there is one vertex in the center of the triangle labeled D. AB is labeled 4, AC is labeled 2, AD is labeled1, BC is labeled 13, BD is labeled 9, and CD is labeled 8.\" width=\"289\" height=\"251\" \/><\/center>[reveal-answer q=\"997641\"]Show Solution[\/reveal-answer] [hidden-answer a=\"997641\"]To apply the Brute force algorithm, we list all possible Hamiltonian circuits and calculate their weight:\r\n\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td><strong>Circuit<\/strong><\/td>\r\n<td><strong>Weight<\/strong><\/td>\r\n<\/tr>\r\n<tr>\r\n<td>[latex]ABCDA[\/latex]<\/td>\r\n<td>[latex]4+13+8+1 = 26[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>[latex]ABDCA[\/latex]<\/td>\r\n<td>[latex]4+9+8+2 = 23[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>[latex]ACBDA[\/latex]<\/td>\r\n<td>[latex]2+13+9+1 = 25[\/latex]<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<p>&nbsp;<\/p>\r\n<p>Note: These are the unique circuits on this graph. All other possible circuits are the reverse of the listed ones or start at a different vertex, but result in the same weights. From this we can see that the second circuit, [latex]ABDCA[\/latex], is the optimal circuit.<\/p>\r\n<p>Watch this example worked again in the following video.<\/p>\r\n<iframe title=\"YouTube video player\" src=\"https:\/\/www.youtube.com\/embed\/wDXQ6tWsJxw?si=8ZJVlB2obVtH68Hh\" width=\"560\" height=\"315\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe>\r\n<p>You can view the <a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/TSP+by+brute+force.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cTSP by brute force\u201d here (opens in new window).<\/a><\/p>\r\n\r\n[\/hidden-answer]<\/section>\r\n<p>The Brute force algorithm is optimal; it will always produce the Hamiltonian circuit with minimum weight. Is it efficient? To answer that question, we need to consider how many Hamiltonian circuits a graph could have. For simplicity, let\u2019s look at the worst-case possibility, where every vertex is connected to every other vertex. This is called a <strong>complete graph.<\/strong><\/p>\r\n<center>\r\n[caption id=\"attachment_10346\" align=\"aligncenter\" width=\"250\"]<img class=\"wp-image-10346 size-full\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/02184943\/gt11.png\" alt=\"Star Shaped graph with 5 vertices named Seattle, Dallas, Atlanta, Chicago, LA and the following dollar amounts between the cities: Seattle and dallas - $120, Seattle and atlanta - $140, Seattle and LA $70, LA and chicago - $100, chicago and atlanta - $75, atlanta and dallas - $85, dallas and chicago - $165, LA and atlanta - $170, chicago and dallas - $165. The outer connections are made in red, between Seattle and LA, LA and Chicago, Chicago and Atlanta, Atlanta and Dallas, and Dallas and Seattle .\" width=\"250\" height=\"128\" \/> Figure 1. A complete graph connecting five cities[\/caption]\r\n<\/center>\r\n<p>&nbsp;<\/p>\r\n<p>Suppose we had a complete graph with five vertices like the air travel graph above. From Seattle there are four cities we can visit first. From each of those, there are three choices. From each of those cities, there are two possible cities to visit next. There is then only one choice for the last city before returning home. This can be shown visually:<\/p>\r\n<center>\r\n[caption id=\"attachment_6233\" align=\"aligncenter\" width=\"500\"]<img class=\"wp-image-6233\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/07165422\/FullTreeCircuit-300x107.png\" alt=\"A flowchart of all potential routes one could take from Seattle through LA, Dallas, Chicago, and Atlanta without repeating cities. There are four possibilities for the first step, 12 for the second step, 24 for the third step, and 24 for the fourth step\" width=\"500\" height=\"178\" \/> Figure 2. A flowchart of potential routes that can be taken to Seattle through Los Angeles, Dallas, Chicago, and Atlanta[\/caption]\r\n<\/center>\r\n<p>&nbsp;<\/p>\r\n<p>Counting the number of routes, we can see there are [latex]4\\cdot{3}\\cdot{2}\\cdot{1}[\/latex] routes. For six cities there would be [latex]5\\cdot{4}\\cdot{3}\\cdot{2}\\cdot{1}[\/latex] routes. \u00a0<\/p>\r\n<section class=\"textbox keyTakeaway\">\r\n<div>\r\n<h3>Number of Possible Circuits<\/h3>\r\n<p>For [latex]N[\/latex] vertices in a complete graph, there will be [latex](n-1)!=(n-1)(n-2)(n-3)\\dots{3}\\cdot{2}\\cdot{1}[\/latex] routes. Half of these are duplicates in reverse order, so there are [latex]\\frac{(n-1)!}{2}[\/latex] unique circuits.<\/p>\r\n<p>&nbsp;<\/p>\r\n<p>The exclamation symbol, [latex]![\/latex], is read \u201cfactorial\u201d and is shorthand for the product shown.<\/p>\r\n<\/div>\r\n<\/section>\r\n<section class=\"textbox example\">How many circuits would a complete graph with [latex]8[\/latex] vertices have? [reveal-answer q=\"997642\"]Show Solution[\/reveal-answer] [hidden-answer a=\"997642\"] A complete graph with [latex]8[\/latex] vertices would have [latex](8-1) !=7 !=7 \\cdot 6 \\cdot 5 \\cdot 4 \\cdot 3 \\cdot 2 \\cdot 1=5040[\/latex] possible Hamiltonian circuits. Half of the circuits are duplicates of other circuits but in reverse order, leaving [latex]2520[\/latex] unique routes. While this is a lot, it doesn\u2019t seem unreasonably huge. But consider what happens as the number of cities increase:\r\n\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td><strong>Cities<\/strong><\/td>\r\n<td><strong>Unique Hamiltonian Circuits<\/strong><\/td>\r\n<\/tr>\r\n<tr>\r\n<td>[latex]9[\/latex]<\/td>\r\n<td>[latex]\\frac{8!}{2} = 20,160[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>[latex]10[\/latex]<\/td>\r\n<td>[latex]\\frac{9!}{2} = 181,440[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>[latex]11[\/latex]<\/td>\r\n<td>[latex]\\frac{10!}{2} = 1,814,400[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>[latex]15[\/latex]<\/td>\r\n<td>[latex]\\frac{14!}{2} = 43,589,145,600[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>[latex]20[\/latex]<\/td>\r\n<td>[latex]\\frac{19!}{2} = 60,822,550,204,416,000[\/latex]<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<p>&nbsp;<\/p>\r\n<p>Watch this example worked again in the following video.<\/p>\r\n<iframe title=\"YouTube video player\" src=\"https:\/\/www.youtube.com\/embed\/DwZw4t0qxuQ?si=J9FX9igugsoL9ivf\" width=\"560\" height=\"315\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe>\r\n<p>You can view the <a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Number+of+circuits+in+a+complete+graph.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cNumber of circuits in a complete graph\u201d here (opens in new window).<\/a><\/p>\r\n\r\n[\/hidden-answer]<\/section>\r\n<p>As you can see the number of circuits is growing extremely quickly. If a computer looked at one billion circuits a second, it would still take almost two years to examine all the possible circuits with only [latex]20[\/latex] cities! Certainly brute force is <strong>not<\/strong> an efficient algorithm. Let's look at another option.<\/p>\r\n<h2>Nearest Neighbor Algorithm<\/h2>\r\n<section class=\"textbox questionHelp\"><strong>How To: Nearest Neighbor Algorithm (NNA)<\/strong>\r\n<ol style=\"list-style-type: decimal;\">\r\n\t<li>Select a starting point.<\/li>\r\n\t<li>Move to the nearest unvisited vertex (the edge with smallest weight).<\/li>\r\n\t<li>Repeat until the circuit is complete.<\/li>\r\n<\/ol>\r\n<\/section>\r\n<p>Unfortunately, no one has yet found an efficient <em>and<\/em> optimal algorithm to solve the TSP, and it is very unlikely anyone ever will. Since it is not practical to use brute force to solve the problem, we turn instead to <strong>heuristic algorithms<\/strong>; efficient algorithms that give approximate solutions. In other words, heuristic algorithms are fast, but may or may not produce the optimal circuit.<\/p>\r\n<section class=\"textbox example\"><center><img class=\"aligncenter size-full wp-image-10346\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/02184943\/gt11.png\" alt=\"Star Shaped graph with 5 vertices named Seattle, Dallas, Atlanta, Chicago, LA and the following dollar amounts between the cities: Seattle and dallas - $120, Seattle and atlanta - $140, Seattle and LA $70, LA and chicago - $100, chicago and atlanta - $75, atlanta and dallas - $85, dallas and chicago - $165, LA and atlanta - $170, chicago and dallas - $165. The outer connections are made in red, between Seattle and LA, LA and Chicago, Chicago and Atlanta, Atlanta and Dallas, and Dallas and Seattle .\" width=\"250\" height=\"128\" \/><\/center>\r\n<p>&nbsp;<\/p>\r\n<p>Consider again our salesperson.<\/p>\r\n\r\nStarting at Seattle, the nearest neighbor (cheapest flight) is to LA, at a cost of [latex]$70[\/latex]. From there:\r\n\r\n<ul>\r\n\t<li>LA to Chicago: [latex]$100[\/latex]<\/li>\r\n\t<li>Chicago to Atlanta: [latex]$75[\/latex]<\/li>\r\n\t<li>Atlanta to Dallas: [latex]$85[\/latex]<\/li>\r\n\t<li>Dallas to Seattle: [latex]$120[\/latex]<\/li>\r\n\t<li>Total cost: [latex]$450[\/latex]<\/li>\r\n<\/ul>\r\n\r\nIn this case, nearest neighbor found the optimal circuit.<\/section>\r\n<section class=\"textbox tryIt\">[ohm2_question hide_question_numbers=1]6964[\/ohm2_question]<\/section>\r\n<p>What if the NNA does not pick the most optimal edge?<\/p>\r\n<section class=\"textbox example\"><img class=\"alignright wp-image-6229\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/07165127\/HamiltonianCircuit-1-150x150.png\" alt=\"Triangular graph with 4 vertices and 6 edges. The outer vertices of the triangle are labeled A, B, and C, and there is one vertex in the center of the triangle labeled D. AB is labeled 4, AC is labeled 2, AD is labeled 1, BC is labeled 13, BD is labeled 9, and CD is labeled 8.\" width=\"200\" height=\"174\" \/>\r\n<p>Consider our earlier graph, shown to the right.<\/p>\r\n<p>Starting at vertex [latex]A[\/latex], the nearest neighbor is vertex [latex]D[\/latex] with a weight of [latex]1[\/latex].<\/p>\r\n<p>From [latex]D[\/latex], the nearest neighbor is [latex]C[\/latex], with a weight of [latex]8[\/latex].<\/p>\r\n<p>From [latex]C[\/latex], our only option is to move to vertex [latex]B[\/latex], the only unvisited vertex, with a cost of [latex]13[\/latex].<\/p>\r\n<p>From [latex]B[\/latex] we return to [latex]A[\/latex] with a weight of [latex]4[\/latex].<\/p>\r\n<p>The resulting circuit is [latex]ADCBA[\/latex] with a total weight of [latex]1+8+13+4 = 26[\/latex].<\/p>\r\n<\/section>\r\n<p>We ended up finding the worst circuit in the graph! What happened? Unfortunately, while it is very easy to implement, the NNA is a greedy algorithm, meaning it only looks at the immediate decision without considering the consequences in the future. In this case, following the edge [latex]AD[\/latex] forced us to use the very expensive edge [latex]BC[\/latex] later. How could we improve the outcome? One option would be to redo the nearest neighbor algorithm with a different starting point to see if the result changed. Since nearest neighbor is so fast, doing it several times isn\u2019t a big deal.<\/p>\r\n<section class=\"textbox example\"><img class=\"alignright wp-image-6229\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/07165127\/HamiltonianCircuit-1-150x150.png\" alt=\"Triangular graph with 4 vertices and 6 edges. The outer vertices of the triangle are labeled A, B, and C, and there is one vertex in the center of the triangle labeled D. AB is labeled 4, AC is labeled 2, AD is labeled1, BC is labeled 13, BD is labeled 9, and CD is labeled 8.\" width=\"200\" height=\"174\" \/>\r\n<p>Starting at vertex [latex]A[\/latex] resulted in a circuit with weight [latex]26[\/latex], as seen above. Lets repeat the NNA for the other vertices.<\/p>\r\n<p>Starting at vertex [latex]B[\/latex], the nearest neighbor circuit is [latex]BADCB[\/latex] with a weight of [latex]4+1+8+13 = 26[\/latex]. This is the same circuit we found starting at vertex [latex]A[\/latex]. No better.<\/p>\r\n<p>Starting at vertex [latex]C[\/latex], the nearest neighbor circuit is [latex]CADBC[\/latex] with a weight of [latex]2+1+9+13 = 25[\/latex]. Better!<\/p>\r\n<p>Starting at vertex [latex]D[\/latex], the nearest neighbor circuit is [latex]DACBA[\/latex]. Notice that this is actually the same circuit we found starting at [latex]C[\/latex], just written with a different starting vertex.<\/p>\r\n<p>The repeat nearest neighbor algorithm (RNNA) was able to produce a slightly better circuit with a weight of [latex]25[\/latex], but still not the optimal circuit in this case. Notice that even though we found the circuit by starting at vertex [latex]C[\/latex], we could still write the circuit starting at [latex]A[\/latex]: [latex]ADBCA[\/latex] or [latex]ACBDA[\/latex].<\/p>\r\n<\/section>\r\n<section class=\"textbox example\">The table below shows the time, in milliseconds, it takes to send a packet of data between computers on a network. If data needed to be sent in sequence to each computer, then notification needed to come back to the original computer, we would be solving the TSP. The computers are labeled [latex]A-F[\/latex] for convenience.\r\n\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td>&nbsp;<\/td>\r\n<td>[latex]A[\/latex]<\/td>\r\n<td>[latex]B[\/latex]<\/td>\r\n<td>[latex]C[\/latex]<\/td>\r\n<td>[latex]D[\/latex]<\/td>\r\n<td>[latex]E[\/latex]<\/td>\r\n<td>[latex]F[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>[latex]A[\/latex]<\/td>\r\n<td>--<\/td>\r\n<td>[latex]44[\/latex]<\/td>\r\n<td>[latex]34[\/latex]<\/td>\r\n<td>[latex]12[\/latex]<\/td>\r\n<td>[latex]40[\/latex]<\/td>\r\n<td>[latex]41[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>[latex]B[\/latex]<\/td>\r\n<td>[latex]44[\/latex]<\/td>\r\n<td>--<\/td>\r\n<td>[latex]31[\/latex]<\/td>\r\n<td>[latex]43[\/latex]<\/td>\r\n<td>[latex]24[\/latex]<\/td>\r\n<td>[latex]50[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>[latex]C[\/latex]<\/td>\r\n<td>[latex]34[\/latex]<\/td>\r\n<td>[latex]31[\/latex]<\/td>\r\n<td>--<\/td>\r\n<td>[latex]20[\/latex]<\/td>\r\n<td>[latex]39[\/latex]<\/td>\r\n<td>[latex]27[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>[latex]D[\/latex]<\/td>\r\n<td>[latex]12[\/latex]<\/td>\r\n<td>[latex]43[\/latex]<\/td>\r\n<td>[latex]20[\/latex]<\/td>\r\n<td>--<\/td>\r\n<td>[latex]11[\/latex]<\/td>\r\n<td>[latex]17[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>[latex]E[\/latex]<\/td>\r\n<td>[latex]40[\/latex]<\/td>\r\n<td>[latex]24[\/latex]<\/td>\r\n<td>[latex]39[\/latex]<\/td>\r\n<td>[latex]11[\/latex]<\/td>\r\n<td>--<\/td>\r\n<td>[latex]42[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>[latex]F[\/latex]<\/td>\r\n<td>[latex]41[\/latex]<\/td>\r\n<td>[latex]50[\/latex]<\/td>\r\n<td>[latex]27[\/latex]<\/td>\r\n<td>[latex]17[\/latex]<\/td>\r\n<td>[latex]42[\/latex]<\/td>\r\n<td>--<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<p>&nbsp;<\/p>\r\n<ol style=\"list-style-type: upper-alpha;\">\r\n\t<li>Find the circuit generated by the NNA starting at vertex [latex]B[\/latex].<\/li>\r\n\t<li>Find the circuit generated by the RNNA.<\/li>\r\n<\/ol>\r\n\r\n[reveal-answer q=\"997644\"]Show Solution[\/reveal-answer] [hidden-answer a=\"997644\"] At each step, we look for the nearest location we haven\u2019t already visited. From [latex]B[\/latex] the nearest computer is [latex]E[\/latex] with time [latex]24[\/latex]. From [latex]E[\/latex], the nearest computer is [latex]D[\/latex] with time [latex]11[\/latex]. From [latex]D[\/latex] the nearest is [latex]A[\/latex] with time [latex]12[\/latex]. From [latex]A[\/latex] the nearest is [latex]C[\/latex] with time [latex]34[\/latex]. From [latex]C[\/latex], the only computer we haven\u2019t visited is [latex]F[\/latex] with time [latex]27[\/latex]. From [latex]F[\/latex], we return back to [latex]B[\/latex] with time [latex]50[\/latex]. The NNA circuit from [latex]B[\/latex] is [latex]BEDACFB[\/latex] with time [latex]158[\/latex] milliseconds. [\/hidden-answer]<\/section>\r\n<p>While certainly better than the basic NNA, unfortunately, the RNNA is still greedy and will produce very bad results for some graphs. As an alternative, our next approach will step back and look at the \u201cbig picture\u201d \u2013 it will select first the edges that are shortest, and then fill in the gaps.<\/p>\r\n<h2>Sorted Edges Algorithm<\/h2>\r\n<section class=\"textbox questionHelp\">\r\n<p><strong>How To: Sorted Edges Algorithm (a.k.a. cheapest link algorithm)<\/strong><\/p>\r\n<ol style=\"list-style-type: decimal;\">\r\n\t<li>Select the cheapest unused edge in the graph.<\/li>\r\n\t<li>Repeat step 1, adding the cheapest unused edge to the circuit, unless:\r\n\r\n<ol style=\"list-style-type: lower-alpha;\">\r\n\t<li>adding the edge would create a circuit that doesn\u2019t contain all vertices, or<\/li>\r\n\t<li>adding the edge would give a vertex degree [latex]3[\/latex].<\/li>\r\n<\/ol>\r\n<\/li>\r\n\t<li>Repeat until a circuit containing all vertices is formed.<\/li>\r\n<\/ol>\r\n<\/section>\r\n<section class=\"textbox example\">Using the four vertex graph from earlier, we can use the Sorted Edges algorithm.<center><img class=\"aligncenter wp-image-6229\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/07165127\/HamiltonianCircuit-1-150x150.png\" alt=\"Triangular graph with 4 vertices and 6 edges. The outer vertices of the triangle are labeled A, B, and C, and there is one vertex in the center of the triangle labeled D. AB is labeled 4, AC is labeled 2, AD is labeled1, BC is labeled 13, BD is labeled 9, and CD is labeled 8.\" width=\"200\" height=\"174\" \/><\/center>\r\n<p>&nbsp;<\/p>\r\n\r\nThe cheapest edge is [latex]AD[\/latex], with a cost of [latex]1[\/latex]. We highlight that edge to mark it selected. The next shortest edge is [latex]AC[\/latex], with a weight of [latex]2[\/latex], so we highlight that edge.<center><img class=\"aligncenter wp-image-6390\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10141815\/HamiltonianCircuit-2-1.png\" alt=\"triangular graph with 4 vertices and 6 edges. There is one vertex in the center of the triangle. The edge between A and D is highlighted\" width=\"200\" height=\"174\" \/><\/center>\u00a0<center><img class=\"aligncenter wp-image-6391\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10141908\/HamiltonianCircuit-3.png\" alt=\"triangular graph with 4 vertices and 6 edges. There is one vertex in the center of the triangle. Edges between A and D and A and C are highlighted.\" width=\"200\" height=\"174\" \/><\/center>\r\n<p>&nbsp;<\/p>\r\n\r\nFor the third edge, we\u2019d like to add [latex]AB[\/latex], but that would give vertex [latex]A[\/latex] degree [latex]3[\/latex], which is not allowed in a Hamiltonian circuit. The next shortest edge is [latex]CD[\/latex], but that edge would create a circuit [latex]ACDA[\/latex] that does not include vertex [latex]B[\/latex], so we reject that edge. The next shortest edge is [latex]BD[\/latex], so we add that edge to the graph.<center><img class=\"aligncenter wp-image-6393\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142033\/HamiltonianCircuit-4.png\" alt=\"triangular graph with 4 vertices and 6 edges. There is one vertex in the center of the triangle. Edges between A and D and A and C are highlighted. Edge between A and B is highlighted.\" width=\"200\" height=\"174\" \/><\/center>\r\n<p style=\"text-align: center;\"><strong>Bad<\/strong><\/p>\r\n<center><img class=\"aligncenter wp-image-6394\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142131\/HamiltonianCircuit-5.png\" alt=\"triangular graph with 4 vertices and 6 edges. There is one vertex in the center of the triangle. Edges between A and D and A and C are highlighted. \" width=\"200\" height=\"174\" \/><\/center>\r\n<p style=\"text-align: center;\"><strong>Bad<\/strong><\/p>\r\n<center><img class=\"aligncenter wp-image-6395\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142216\/HamiltonianCircuit-6.png\" alt=\"triangular graph with 4 vertices and 6 edges. There is one vertex in the center of the triangle. Edges between A and D and A and C are highlighted.\" width=\"200\" height=\"174\" \/><\/center>\r\n<p style=\"text-align: center;\"><strong>Okay<\/strong><\/p>\r\n\r\nWe then add the last edge to complete the circuit: [latex]ACBDA[\/latex] with weight [latex]25[\/latex]. Notice that the algorithm did not produce the optimal circuit in this case; the optimal circuit is [latex]ACDBA[\/latex] with weight [latex]23[\/latex].<center><img class=\"aligncenter wp-image-6396\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142316\/HamiltonianCircuit-7.png\" alt=\"Notice that the algorithm did not produce the optimal circuit in this case; the optimal circuit is ACDBA with weight 23. \" width=\"200\" height=\"174\" \/><\/center>\r\n<p>&nbsp;<\/p>\r\n<p>While the Sorted Edge algorithm overcomes some of the shortcomings of NNA, it is still only a heuristic algorithm, and does not guarantee the optimal circuit.<\/p>\r\n<\/section>\r\n<section class=\"textbox example\">Your teacher\u2019s band, <em>Derivative Work<\/em>, is doing a bar tour in Oregon. The driving distances are shown below. Plan an efficient route for your teacher to visit all the cities and return to the starting location. Use NNA starting at Portland, and then use Sorted Edges.\r\n\r\n<table style=\"width: 586px; height: 333px;\">\r\n<tbody>\r\n<tr>\r\n<td>&nbsp;<\/td>\r\n<td>\u00a0Ashland<\/td>\r\n<td>Astoria<\/td>\r\n<td>\u00a0Bend<\/td>\r\n<td>\u00a0Corvallis<\/td>\r\n<td>\u00a0Crater Lake<\/td>\r\n<td>\u00a0Eugene<\/td>\r\n<td>\u00a0Newport<\/td>\r\n<td>\u00a0Portland<\/td>\r\n<td>\u00a0Salem<\/td>\r\n<td>\u00a0Seaside<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Ashland<\/td>\r\n<td>-<\/td>\r\n<td>[latex]374[\/latex]<\/td>\r\n<td>[latex]200[\/latex]<\/td>\r\n<td>[latex]223[\/latex]<\/td>\r\n<td>[latex]108[\/latex]<\/td>\r\n<td>[latex]178[\/latex]<\/td>\r\n<td>[latex]252[\/latex]<\/td>\r\n<td>[latex]285[\/latex]<\/td>\r\n<td>[latex]240[\/latex]<\/td>\r\n<td>[latex]356[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Astoria<\/td>\r\n<td>[latex]374[\/latex]<\/td>\r\n<td>-<\/td>\r\n<td>[latex]255[\/latex]<\/td>\r\n<td>[latex]166[\/latex]<\/td>\r\n<td>[latex]433[\/latex]<\/td>\r\n<td>[latex]199[\/latex]<\/td>\r\n<td>[latex]135[\/latex]<\/td>\r\n<td>[latex]95[\/latex]<\/td>\r\n<td>[latex]136[\/latex]<\/td>\r\n<td>[latex]17[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Bend<\/td>\r\n<td>[latex]200[\/latex]<\/td>\r\n<td>[latex]255[\/latex]<\/td>\r\n<td>-<\/td>\r\n<td>[latex]128[\/latex]<\/td>\r\n<td>[latex]277[\/latex]<\/td>\r\n<td>[latex]128[\/latex]<\/td>\r\n<td>[latex]180[\/latex]<\/td>\r\n<td>[latex]160[\/latex]<\/td>\r\n<td>[latex]131[\/latex]<\/td>\r\n<td>[latex]247[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Corvallis<\/td>\r\n<td>[latex]223[\/latex]<\/td>\r\n<td>[latex]166[\/latex]<\/td>\r\n<td>[latex]128[\/latex]<\/td>\r\n<td>-<\/td>\r\n<td>[latex]430[\/latex]<\/td>\r\n<td>[latex]47[\/latex]<\/td>\r\n<td>[latex]52[\/latex]<\/td>\r\n<td>[latex]84[\/latex]<\/td>\r\n<td>[latex]40[\/latex]<\/td>\r\n<td>[latex]155[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Crater Lake<\/td>\r\n<td>[latex]108[\/latex]<\/td>\r\n<td>[latex]433[\/latex]<\/td>\r\n<td>[latex]277[\/latex]<\/td>\r\n<td>[latex]430[\/latex]<\/td>\r\n<td>-<\/td>\r\n<td>[latex]453[\/latex]<\/td>\r\n<td>[latex]478[\/latex]<\/td>\r\n<td>[latex]344[\/latex]<\/td>\r\n<td>[latex]389[\/latex]<\/td>\r\n<td>[latex]423[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Eugene<\/td>\r\n<td>[latex]178[\/latex]<\/td>\r\n<td>[latex]199[\/latex]<\/td>\r\n<td>[latex]128[\/latex]<\/td>\r\n<td>[latex]47[\/latex]<\/td>\r\n<td>[latex]453[\/latex]<\/td>\r\n<td>-<\/td>\r\n<td>[latex]91[\/latex]<\/td>\r\n<td>[latex]110[\/latex]<\/td>\r\n<td>[latex]64[\/latex]<\/td>\r\n<td>[latex]181[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Newport<\/td>\r\n<td>[latex]252[\/latex]<\/td>\r\n<td>[latex]135[\/latex]<\/td>\r\n<td>[latex]180[\/latex]<\/td>\r\n<td>[latex]52[\/latex]<\/td>\r\n<td>[latex]478[\/latex]<\/td>\r\n<td>[latex]91[\/latex]<\/td>\r\n<td>-<\/td>\r\n<td>[latex]114[\/latex]<\/td>\r\n<td>[latex]83[\/latex]<\/td>\r\n<td>[latex]117[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Portland<\/td>\r\n<td>[latex]285[\/latex]<\/td>\r\n<td>[latex]95[\/latex]<\/td>\r\n<td>[latex]160[\/latex]<\/td>\r\n<td>[latex]84[\/latex]<\/td>\r\n<td>[latex]344[\/latex]<\/td>\r\n<td>[latex]110[\/latex]<\/td>\r\n<td>[latex]114[\/latex]<\/td>\r\n<td>-<\/td>\r\n<td>[latex]47[\/latex]<\/td>\r\n<td>[latex]78[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Salem<\/td>\r\n<td>[latex]240[\/latex]<\/td>\r\n<td>[latex]136[\/latex]<\/td>\r\n<td>[latex]131[\/latex]<\/td>\r\n<td>[latex]40[\/latex]<\/td>\r\n<td>[latex]389[\/latex]<\/td>\r\n<td>[latex]64[\/latex]<\/td>\r\n<td>[latex]83[\/latex]<\/td>\r\n<td>[latex]47[\/latex]<\/td>\r\n<td>-<\/td>\r\n<td>[latex]118[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Seaside<\/td>\r\n<td>[latex]356[\/latex]<\/td>\r\n<td>[latex]17[\/latex]<\/td>\r\n<td>[latex]247[\/latex]<\/td>\r\n<td>[latex]155[\/latex]<\/td>\r\n<td>[latex]423[\/latex]<\/td>\r\n<td>[latex]181[\/latex]<\/td>\r\n<td>[latex]117[\/latex]<\/td>\r\n<td>[latex]78[\/latex]<\/td>\r\n<td>[latex]118[\/latex]<\/td>\r\n<td>-<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n\r\n[reveal-answer q=\"997645\"]Show Solution[\/reveal-answer] [hidden-answer a=\"997645\"] Using NNA with a large number of cities, you might find it helpful to mark off the cities as they\u2019re visited to keep from accidently visiting them again. Looking in the row for Portland, the smallest distance is [latex]47[\/latex], to Salem.\r\n\r\n<p>Following that idea, our circuit will be:<\/p>\r\n\r\n[latex]\\begin{array} {ll} \\text{Portland to Salem} &amp; 47 \\\\ \\text{Salem to Corvallis} &amp; 40 \\\\ \\text{Corvallis to Eugene} &amp; 47 \\\\ \\text{Eugene to Newport} &amp; 91 \\\\ \\text{Newport to Seaside} &amp; 117 \\\\ \\text{Seaside to Astoria} &amp; 17 \\\\ \\text{Astoria to Bend} &amp; 255 \\\\ \\text{Bend to Ashland} &amp; 200 \\\\ \\text{Ashland to Crater Lake} &amp; 108 \\\\ \\text{Crater Lake to Portland} &amp; 344 \\\\ \\text{Total trip length: } &amp; 1266\\text{ miles} \\end{array}[\/latex]\r\n\r\n<p>Using Sorted Edges, you might find it helpful to draw an empty graph, perhaps by drawing vertices in a circular pattern. Adding edges to the graph as you select them will help you visualize any circuits or vertices with degree [latex]3[\/latex].<\/p>\r\n<center><img class=\"aligncenter size-medium wp-image-6398\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142420\/Oregon-Circuit-1-300x199.png\" alt=\"ring of dots with city names in problem as labels.\" width=\"300\" height=\"199\" \/><\/center>\r\n<p>&nbsp;<\/p>\r\n<p>We start adding the shortest edges:<\/p>\r\n\r\n[latex]\\begin{array} {ll} \\text{Seaside to Astoria} &amp; 17\\text{ miles} \\\\ \\text{Corvallis to Salem} &amp; 40\\text{ miles} \\\\ \\text{Portland to Salem} &amp; 47\\text{ miles} \\\\ \\text{Corvallis to Eugene} &amp; 47\\text{ miles} \\end{array}[\/latex] <img class=\"size-medium wp-image-6399 alignright\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142512\/Oregon-Circuit-2-300x199.png\" alt=\"ring of dots with city names in problem as labels. edges between Seaside and Astoria, Eugene and Corvallis, Salem and Corvallis, and Salem and Portland.\" width=\"300\" height=\"199\" \/>\r\n<p>The graph after adding these edges is shown to the right.\u00a0 The next shortest edge is from Corvallis to Newport at [latex]52[\/latex] miles, but adding that edge would give Corvallis degree [latex]3[\/latex]. Continuing on, we can skip over any edge pair that contains Salem or Corvallis, since they both already have degree [latex]2[\/latex].<\/p>\r\n\r\n[latex]\\begin{array} {ll} \\text{Portland to Seaside} &amp; 78\\text{ miles} \\\\ \\text{Eugene to Newport} &amp; 91\\text{ miles} \\\\ \\text{Portland to Astoria} &amp; \\text{(reject \u2013 closes circuit)} \\\\ \\text{Ashland to Crater Lk} &amp; 108\\text{ miles} \\end{array}[\/latex] <img class=\"wp-image-6401 size-medium alignright\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142619\/Oregon-Circuit-3-300x199.png\" alt=\"ring of dots with city names in problem as labels. edges between Seaside and Astoria, Seaside and Portland, Eugene and Corvallis, Eugene and Newport, Salem and Corvallis, Salem and Portland, and Ashland and Crater Lake..\" width=\"300\" height=\"199\" \/>\r\n<p>The graph after adding these edges is shown to the right. At this point, we can skip over any edge pair that contains Salem, Seaside, Eugene, Portland, or Corvallis since they already have degree [latex]2[\/latex]. \u00a0<\/p>\r\n\r\n[latex]\\begin{array} {ll} \\text{Newport to Astoria} &amp; \\text{(reject \u2013 closes circuit)} \\\\ \\text{Newport to Bend} &amp; 180\\text{ miles} \\\\ \\text{Bend to Ashland} &amp; 200\\text{ miles} \\end{array}[\/latex]\r\n\r\n<p>At this point the only way to complete the circuit is to add:<\/p>\r\n<p>Crater Lk to Astoria\u00a0\u00a0 [latex]433[\/latex] miles.<\/p>\r\n<p>\u00a0The final circuit, written to start at Portland, is:<\/p>\r\n<p>Portland, Salem, Corvallis, Eugene, Newport, Bend, Ashland, Crater Lake, Astoria, Seaside, Portland.<\/p>\r\n<p>\u00a0Total trip length: [latex]1241[\/latex] miles.<\/p>\r\n<p>While better than the NNA route, neither algorithm produced the optimal route. The following route can make the tour in [latex]1069[\/latex] miles:<\/p>\r\n<p>Portland, Astoria, Seaside, Newport, Corvallis, Eugene, Ashland, Crater Lake, Bend, Salem, Portland<\/p>\r\n<center><img class=\"aligncenter wp-image-6403 size-medium\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142708\/Oregon-Circuit-4-300x199.png\" alt=\"ring of dots with city names in problem as labels. edges between Seaside and Astoria, Seaside and Portland, Eugene and Corvallis, Eugene and Newport, Salem and Corvallis, Salem and Portland, Ashland and Crater Lake, Ashland and Bend, Bend and Newport, and Astoria and Crater Lake.\" width=\"300\" height=\"199\" \/><\/center>\r\n<p>&nbsp;<\/p>\r\n<p>Watch the example of nearest neighbor algorithm for traveling from city to city using a table worked out in the video below.<\/p>\r\n<p>[embed]https:\/\/youtu.be\/GFp-046PQx0[\/embed]<\/p>\r\n<p>You can view the <a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Nearest+Neighbor+from+a+table.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cNearest Neighbor from a table\u201d here (opens in new window).<\/a><\/p>\r\n<p>In the next video we use the same table, but use sorted edges to plan the trip.<\/p>\r\n<iframe title=\"YouTube video player\" src=\"https:\/\/www.youtube.com\/embed\/_gXyujMsrmw?si=vFgQ3MgLwgHxwt50\" width=\"560\" height=\"315\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe>\r\n<p>You can view the <a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Sorted+Edges+from+a+table.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cSorted Edges from a table\u201d here (opens in new window).<\/a><\/p>\r\n\r\n[\/hidden-answer]<\/section>\r\n<section class=\"textbox tryIt\">[ohm2_question hide_question_numbers=1]6966[\/ohm2_question]<\/section>","rendered":"<p>With Hamiltonian circuits, our focus will not be on existence, but on the question of optimization; given a graph where the edges have weights, can we find the optimal Hamiltonian circuit; the one with lowest total weight.<\/p>\n<p>This problem is called the <strong>Traveling salesperson problem<\/strong> (TSP) because the question can be framed like this: Suppose a salesperson needs to give sales pitches in four cities. They looks up the airfares between each city, and put the costs in a graph. The salesperson needs to figure out what order they should travel to visit each city once then return home with the lowest cost?<\/p>\n<p>To answer this question of how to find the lowest cost Hamiltonian circuit, we will consider some possible approaches.<\/p>\n<h2>Brute Force Algorithm<\/h2>\n<p>The first option that might come to mind is to just try all different possible circuits. We call this the <strong>brute force algorithm<\/strong>.<\/p>\n<section class=\"textbox questionHelp\">\n<p><strong>How To: Brute Force Algorithm (a.k.a. exhaustive search)<\/strong><\/p>\n<ol style=\"list-style-type: decimal;\">\n<li>List all possible Hamiltonian circuits<\/li>\n<li>Find the length of each circuit by adding the edge weights<\/li>\n<li>Select the circuit with minimal total weight.<\/li>\n<\/ol>\n<\/section>\n<section class=\"textbox example\">Apply the Brute force algorithm to find the minimum cost Hamiltonian circuit on the graph below.<\/p>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-6229 size-full\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/07165127\/HamiltonianCircuit-1.png\" alt=\"Triangular graph with 4 vertices and 6 edges. The outer vertices of the triangle are labeled A, B, and C, and there is one vertex in the center of the triangle labeled D. AB is labeled 4, AC is labeled 2, AD is labeled1, BC is labeled 13, BD is labeled 9, and CD is labeled 8.\" width=\"289\" height=\"251\" srcset=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/07165127\/HamiltonianCircuit-1.png 289w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/07165127\/HamiltonianCircuit-1-65x56.png 65w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/07165127\/HamiltonianCircuit-1-225x195.png 225w\" sizes=\"(max-width: 289px) 100vw, 289px\" \/><\/div>\n<div class=\"qa-wrapper\" style=\"display: block\"><button class=\"show-answer show-answer-button collapsed\" data-target=\"q997641\">Show Solution<\/button> <\/p>\n<div id=\"q997641\" class=\"hidden-answer\" style=\"display: none\">To apply the Brute force algorithm, we list all possible Hamiltonian circuits and calculate their weight:<\/p>\n<table>\n<tbody>\n<tr>\n<td><strong>Circuit<\/strong><\/td>\n<td><strong>Weight<\/strong><\/td>\n<\/tr>\n<tr>\n<td>[latex]ABCDA[\/latex]<\/td>\n<td>[latex]4+13+8+1 = 26[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>[latex]ABDCA[\/latex]<\/td>\n<td>[latex]4+9+8+2 = 23[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>[latex]ACBDA[\/latex]<\/td>\n<td>[latex]2+13+9+1 = 25[\/latex]<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<p>Note: These are the unique circuits on this graph. All other possible circuits are the reverse of the listed ones or start at a different vertex, but result in the same weights. From this we can see that the second circuit, [latex]ABDCA[\/latex], is the optimal circuit.<\/p>\n<p>Watch this example worked again in the following video.<\/p>\n<p><iframe loading=\"lazy\" title=\"YouTube video player\" src=\"https:\/\/www.youtube.com\/embed\/wDXQ6tWsJxw?si=8ZJVlB2obVtH68Hh\" width=\"560\" height=\"315\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<p>You can view the <a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/TSP+by+brute+force.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cTSP by brute force\u201d here (opens in new window).<\/a><\/p>\n<\/div>\n<\/div>\n<\/section>\n<p>The Brute force algorithm is optimal; it will always produce the Hamiltonian circuit with minimum weight. Is it efficient? To answer that question, we need to consider how many Hamiltonian circuits a graph could have. For simplicity, let\u2019s look at the worst-case possibility, where every vertex is connected to every other vertex. This is called a <strong>complete graph.<\/strong><\/p>\n<div style=\"text-align: center;\">\n<figure id=\"attachment_10346\" aria-describedby=\"caption-attachment-10346\" style=\"width: 250px\" class=\"wp-caption aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-10346 size-full\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/02184943\/gt11.png\" alt=\"Star Shaped graph with 5 vertices named Seattle, Dallas, Atlanta, Chicago, LA and the following dollar amounts between the cities: Seattle and dallas - $120, Seattle and atlanta - $140, Seattle and LA $70, LA and chicago - $100, chicago and atlanta - $75, atlanta and dallas - $85, dallas and chicago - $165, LA and atlanta - $170, chicago and dallas - $165. The outer connections are made in red, between Seattle and LA, LA and Chicago, Chicago and Atlanta, Atlanta and Dallas, and Dallas and Seattle .\" width=\"250\" height=\"128\" srcset=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/02184943\/gt11.png 250w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/02184943\/gt11-65x33.png 65w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/02184943\/gt11-225x115.png 225w\" sizes=\"(max-width: 250px) 100vw, 250px\" \/><figcaption id=\"caption-attachment-10346\" class=\"wp-caption-text\">Figure 1. A complete graph connecting five cities<\/figcaption><\/figure>\n<\/div>\n<p>&nbsp;<\/p>\n<p>Suppose we had a complete graph with five vertices like the air travel graph above. From Seattle there are four cities we can visit first. From each of those, there are three choices. From each of those cities, there are two possible cities to visit next. There is then only one choice for the last city before returning home. This can be shown visually:<\/p>\n<div style=\"text-align: center;\">\n<figure id=\"attachment_6233\" aria-describedby=\"caption-attachment-6233\" style=\"width: 500px\" class=\"wp-caption aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-6233\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/07165422\/FullTreeCircuit-300x107.png\" alt=\"A flowchart of all potential routes one could take from Seattle through LA, Dallas, Chicago, and Atlanta without repeating cities. There are four possibilities for the first step, 12 for the second step, 24 for the third step, and 24 for the fourth step\" width=\"500\" height=\"178\" srcset=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/07165422\/FullTreeCircuit-300x107.png 300w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/07165422\/FullTreeCircuit-768x274.png 768w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/07165422\/FullTreeCircuit-65x23.png 65w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/07165422\/FullTreeCircuit-225x80.png 225w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/07165422\/FullTreeCircuit-350x125.png 350w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/07165422\/FullTreeCircuit.png 866w\" sizes=\"(max-width: 500px) 100vw, 500px\" \/><figcaption id=\"caption-attachment-6233\" class=\"wp-caption-text\">Figure 2. A flowchart of potential routes that can be taken to Seattle through Los Angeles, Dallas, Chicago, and Atlanta<\/figcaption><\/figure>\n<\/div>\n<p>&nbsp;<\/p>\n<p>Counting the number of routes, we can see there are [latex]4\\cdot{3}\\cdot{2}\\cdot{1}[\/latex] routes. For six cities there would be [latex]5\\cdot{4}\\cdot{3}\\cdot{2}\\cdot{1}[\/latex] routes. \u00a0<\/p>\n<section class=\"textbox keyTakeaway\">\n<div>\n<h3>Number of Possible Circuits<\/h3>\n<p>For [latex]N[\/latex] vertices in a complete graph, there will be [latex](n-1)!=(n-1)(n-2)(n-3)\\dots{3}\\cdot{2}\\cdot{1}[\/latex] routes. Half of these are duplicates in reverse order, so there are [latex]\\frac{(n-1)!}{2}[\/latex] unique circuits.<\/p>\n<p>&nbsp;<\/p>\n<p>The exclamation symbol, [latex]![\/latex], is read \u201cfactorial\u201d and is shorthand for the product shown.<\/p>\n<\/div>\n<\/section>\n<section class=\"textbox example\">How many circuits would a complete graph with [latex]8[\/latex] vertices have? <\/p>\n<div class=\"qa-wrapper\" style=\"display: block\"><button class=\"show-answer show-answer-button collapsed\" data-target=\"q997642\">Show Solution<\/button> <\/p>\n<div id=\"q997642\" class=\"hidden-answer\" style=\"display: none\"> A complete graph with [latex]8[\/latex] vertices would have [latex](8-1) !=7 !=7 \\cdot 6 \\cdot 5 \\cdot 4 \\cdot 3 \\cdot 2 \\cdot 1=5040[\/latex] possible Hamiltonian circuits. Half of the circuits are duplicates of other circuits but in reverse order, leaving [latex]2520[\/latex] unique routes. While this is a lot, it doesn\u2019t seem unreasonably huge. But consider what happens as the number of cities increase:<\/p>\n<table>\n<tbody>\n<tr>\n<td><strong>Cities<\/strong><\/td>\n<td><strong>Unique Hamiltonian Circuits<\/strong><\/td>\n<\/tr>\n<tr>\n<td>[latex]9[\/latex]<\/td>\n<td>[latex]\\frac{8!}{2} = 20,160[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>[latex]10[\/latex]<\/td>\n<td>[latex]\\frac{9!}{2} = 181,440[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>[latex]11[\/latex]<\/td>\n<td>[latex]\\frac{10!}{2} = 1,814,400[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>[latex]15[\/latex]<\/td>\n<td>[latex]\\frac{14!}{2} = 43,589,145,600[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>[latex]20[\/latex]<\/td>\n<td>[latex]\\frac{19!}{2} = 60,822,550,204,416,000[\/latex]<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<p>Watch this example worked again in the following video.<\/p>\n<p><iframe loading=\"lazy\" title=\"YouTube video player\" src=\"https:\/\/www.youtube.com\/embed\/DwZw4t0qxuQ?si=J9FX9igugsoL9ivf\" width=\"560\" height=\"315\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<p>You can view the <a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Number+of+circuits+in+a+complete+graph.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cNumber of circuits in a complete graph\u201d here (opens in new window).<\/a><\/p>\n<\/div>\n<\/div>\n<\/section>\n<p>As you can see the number of circuits is growing extremely quickly. If a computer looked at one billion circuits a second, it would still take almost two years to examine all the possible circuits with only [latex]20[\/latex] cities! Certainly brute force is <strong>not<\/strong> an efficient algorithm. Let&#8217;s look at another option.<\/p>\n<h2>Nearest Neighbor Algorithm<\/h2>\n<section class=\"textbox questionHelp\"><strong>How To: Nearest Neighbor Algorithm (NNA)<\/strong><\/p>\n<ol style=\"list-style-type: decimal;\">\n<li>Select a starting point.<\/li>\n<li>Move to the nearest unvisited vertex (the edge with smallest weight).<\/li>\n<li>Repeat until the circuit is complete.<\/li>\n<\/ol>\n<\/section>\n<p>Unfortunately, no one has yet found an efficient <em>and<\/em> optimal algorithm to solve the TSP, and it is very unlikely anyone ever will. Since it is not practical to use brute force to solve the problem, we turn instead to <strong>heuristic algorithms<\/strong>; efficient algorithms that give approximate solutions. In other words, heuristic algorithms are fast, but may or may not produce the optimal circuit.<\/p>\n<section class=\"textbox example\">\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-10346\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/02184943\/gt11.png\" alt=\"Star Shaped graph with 5 vertices named Seattle, Dallas, Atlanta, Chicago, LA and the following dollar amounts between the cities: Seattle and dallas - $120, Seattle and atlanta - $140, Seattle and LA $70, LA and chicago - $100, chicago and atlanta - $75, atlanta and dallas - $85, dallas and chicago - $165, LA and atlanta - $170, chicago and dallas - $165. The outer connections are made in red, between Seattle and LA, LA and Chicago, Chicago and Atlanta, Atlanta and Dallas, and Dallas and Seattle .\" width=\"250\" height=\"128\" srcset=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/02184943\/gt11.png 250w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/02184943\/gt11-65x33.png 65w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/02184943\/gt11-225x115.png 225w\" sizes=\"(max-width: 250px) 100vw, 250px\" \/><\/div>\n<p>&nbsp;<\/p>\n<p>Consider again our salesperson.<\/p>\n<p>Starting at Seattle, the nearest neighbor (cheapest flight) is to LA, at a cost of [latex]$70[\/latex]. From there:<\/p>\n<ul>\n<li>LA to Chicago: [latex]$100[\/latex]<\/li>\n<li>Chicago to Atlanta: [latex]$75[\/latex]<\/li>\n<li>Atlanta to Dallas: [latex]$85[\/latex]<\/li>\n<li>Dallas to Seattle: [latex]$120[\/latex]<\/li>\n<li>Total cost: [latex]$450[\/latex]<\/li>\n<\/ul>\n<p>In this case, nearest neighbor found the optimal circuit.<\/section>\n<section class=\"textbox tryIt\"><iframe loading=\"lazy\" id=\"ohm6964\" class=\"resizable\" src=\"https:\/\/ohm.one.lumenlearning.com\/multiembedq.php?id=6964&theme=lumen&iframe_resize_id=ohm6964&source=tnh\" width=\"100%\" height=\"150\"><\/iframe><\/section>\n<p>What if the NNA does not pick the most optimal edge?<\/p>\n<section class=\"textbox example\"><img loading=\"lazy\" decoding=\"async\" class=\"alignright wp-image-6229\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/07165127\/HamiltonianCircuit-1-150x150.png\" alt=\"Triangular graph with 4 vertices and 6 edges. The outer vertices of the triangle are labeled A, B, and C, and there is one vertex in the center of the triangle labeled D. AB is labeled 4, AC is labeled 2, AD is labeled 1, BC is labeled 13, BD is labeled 9, and CD is labeled 8.\" width=\"200\" height=\"174\" srcset=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/07165127\/HamiltonianCircuit-1-65x56.png 65w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/07165127\/HamiltonianCircuit-1-225x195.png 225w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/07165127\/HamiltonianCircuit-1.png 289w\" sizes=\"(max-width: 200px) 100vw, 200px\" \/><\/p>\n<p>Consider our earlier graph, shown to the right.<\/p>\n<p>Starting at vertex [latex]A[\/latex], the nearest neighbor is vertex [latex]D[\/latex] with a weight of [latex]1[\/latex].<\/p>\n<p>From [latex]D[\/latex], the nearest neighbor is [latex]C[\/latex], with a weight of [latex]8[\/latex].<\/p>\n<p>From [latex]C[\/latex], our only option is to move to vertex [latex]B[\/latex], the only unvisited vertex, with a cost of [latex]13[\/latex].<\/p>\n<p>From [latex]B[\/latex] we return to [latex]A[\/latex] with a weight of [latex]4[\/latex].<\/p>\n<p>The resulting circuit is [latex]ADCBA[\/latex] with a total weight of [latex]1+8+13+4 = 26[\/latex].<\/p>\n<\/section>\n<p>We ended up finding the worst circuit in the graph! What happened? Unfortunately, while it is very easy to implement, the NNA is a greedy algorithm, meaning it only looks at the immediate decision without considering the consequences in the future. In this case, following the edge [latex]AD[\/latex] forced us to use the very expensive edge [latex]BC[\/latex] later. How could we improve the outcome? One option would be to redo the nearest neighbor algorithm with a different starting point to see if the result changed. Since nearest neighbor is so fast, doing it several times isn\u2019t a big deal.<\/p>\n<section class=\"textbox example\"><img loading=\"lazy\" decoding=\"async\" class=\"alignright wp-image-6229\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/07165127\/HamiltonianCircuit-1-150x150.png\" alt=\"Triangular graph with 4 vertices and 6 edges. The outer vertices of the triangle are labeled A, B, and C, and there is one vertex in the center of the triangle labeled D. AB is labeled 4, AC is labeled 2, AD is labeled1, BC is labeled 13, BD is labeled 9, and CD is labeled 8.\" width=\"200\" height=\"174\" srcset=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/07165127\/HamiltonianCircuit-1-65x56.png 65w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/07165127\/HamiltonianCircuit-1-225x195.png 225w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/07165127\/HamiltonianCircuit-1.png 289w\" sizes=\"(max-width: 200px) 100vw, 200px\" \/><\/p>\n<p>Starting at vertex [latex]A[\/latex] resulted in a circuit with weight [latex]26[\/latex], as seen above. Lets repeat the NNA for the other vertices.<\/p>\n<p>Starting at vertex [latex]B[\/latex], the nearest neighbor circuit is [latex]BADCB[\/latex] with a weight of [latex]4+1+8+13 = 26[\/latex]. This is the same circuit we found starting at vertex [latex]A[\/latex]. No better.<\/p>\n<p>Starting at vertex [latex]C[\/latex], the nearest neighbor circuit is [latex]CADBC[\/latex] with a weight of [latex]2+1+9+13 = 25[\/latex]. Better!<\/p>\n<p>Starting at vertex [latex]D[\/latex], the nearest neighbor circuit is [latex]DACBA[\/latex]. Notice that this is actually the same circuit we found starting at [latex]C[\/latex], just written with a different starting vertex.<\/p>\n<p>The repeat nearest neighbor algorithm (RNNA) was able to produce a slightly better circuit with a weight of [latex]25[\/latex], but still not the optimal circuit in this case. Notice that even though we found the circuit by starting at vertex [latex]C[\/latex], we could still write the circuit starting at [latex]A[\/latex]: [latex]ADBCA[\/latex] or [latex]ACBDA[\/latex].<\/p>\n<\/section>\n<section class=\"textbox example\">The table below shows the time, in milliseconds, it takes to send a packet of data between computers on a network. If data needed to be sent in sequence to each computer, then notification needed to come back to the original computer, we would be solving the TSP. The computers are labeled [latex]A-F[\/latex] for convenience.<\/p>\n<table>\n<tbody>\n<tr>\n<td>&nbsp;<\/td>\n<td>[latex]A[\/latex]<\/td>\n<td>[latex]B[\/latex]<\/td>\n<td>[latex]C[\/latex]<\/td>\n<td>[latex]D[\/latex]<\/td>\n<td>[latex]E[\/latex]<\/td>\n<td>[latex]F[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>[latex]A[\/latex]<\/td>\n<td>&#8212;<\/td>\n<td>[latex]44[\/latex]<\/td>\n<td>[latex]34[\/latex]<\/td>\n<td>[latex]12[\/latex]<\/td>\n<td>[latex]40[\/latex]<\/td>\n<td>[latex]41[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>[latex]B[\/latex]<\/td>\n<td>[latex]44[\/latex]<\/td>\n<td>&#8212;<\/td>\n<td>[latex]31[\/latex]<\/td>\n<td>[latex]43[\/latex]<\/td>\n<td>[latex]24[\/latex]<\/td>\n<td>[latex]50[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>[latex]C[\/latex]<\/td>\n<td>[latex]34[\/latex]<\/td>\n<td>[latex]31[\/latex]<\/td>\n<td>&#8212;<\/td>\n<td>[latex]20[\/latex]<\/td>\n<td>[latex]39[\/latex]<\/td>\n<td>[latex]27[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>[latex]D[\/latex]<\/td>\n<td>[latex]12[\/latex]<\/td>\n<td>[latex]43[\/latex]<\/td>\n<td>[latex]20[\/latex]<\/td>\n<td>&#8212;<\/td>\n<td>[latex]11[\/latex]<\/td>\n<td>[latex]17[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>[latex]E[\/latex]<\/td>\n<td>[latex]40[\/latex]<\/td>\n<td>[latex]24[\/latex]<\/td>\n<td>[latex]39[\/latex]<\/td>\n<td>[latex]11[\/latex]<\/td>\n<td>&#8212;<\/td>\n<td>[latex]42[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>[latex]F[\/latex]<\/td>\n<td>[latex]41[\/latex]<\/td>\n<td>[latex]50[\/latex]<\/td>\n<td>[latex]27[\/latex]<\/td>\n<td>[latex]17[\/latex]<\/td>\n<td>[latex]42[\/latex]<\/td>\n<td>&#8212;<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<ol style=\"list-style-type: upper-alpha;\">\n<li>Find the circuit generated by the NNA starting at vertex [latex]B[\/latex].<\/li>\n<li>Find the circuit generated by the RNNA.<\/li>\n<\/ol>\n<div class=\"qa-wrapper\" style=\"display: block\"><button class=\"show-answer show-answer-button collapsed\" data-target=\"q997644\">Show Solution<\/button> <\/p>\n<div id=\"q997644\" class=\"hidden-answer\" style=\"display: none\"> At each step, we look for the nearest location we haven\u2019t already visited. From [latex]B[\/latex] the nearest computer is [latex]E[\/latex] with time [latex]24[\/latex]. From [latex]E[\/latex], the nearest computer is [latex]D[\/latex] with time [latex]11[\/latex]. From [latex]D[\/latex] the nearest is [latex]A[\/latex] with time [latex]12[\/latex]. From [latex]A[\/latex] the nearest is [latex]C[\/latex] with time [latex]34[\/latex]. From [latex]C[\/latex], the only computer we haven\u2019t visited is [latex]F[\/latex] with time [latex]27[\/latex]. From [latex]F[\/latex], we return back to [latex]B[\/latex] with time [latex]50[\/latex]. The NNA circuit from [latex]B[\/latex] is [latex]BEDACFB[\/latex] with time [latex]158[\/latex] milliseconds. <\/div>\n<\/div>\n<\/section>\n<p>While certainly better than the basic NNA, unfortunately, the RNNA is still greedy and will produce very bad results for some graphs. As an alternative, our next approach will step back and look at the \u201cbig picture\u201d \u2013 it will select first the edges that are shortest, and then fill in the gaps.<\/p>\n<h2>Sorted Edges Algorithm<\/h2>\n<section class=\"textbox questionHelp\">\n<p><strong>How To: Sorted Edges Algorithm (a.k.a. cheapest link algorithm)<\/strong><\/p>\n<ol style=\"list-style-type: decimal;\">\n<li>Select the cheapest unused edge in the graph.<\/li>\n<li>Repeat step 1, adding the cheapest unused edge to the circuit, unless:\n<ol style=\"list-style-type: lower-alpha;\">\n<li>adding the edge would create a circuit that doesn\u2019t contain all vertices, or<\/li>\n<li>adding the edge would give a vertex degree [latex]3[\/latex].<\/li>\n<\/ol>\n<\/li>\n<li>Repeat until a circuit containing all vertices is formed.<\/li>\n<\/ol>\n<\/section>\n<section class=\"textbox example\">Using the four vertex graph from earlier, we can use the Sorted Edges algorithm.<\/p>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-6229\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/07165127\/HamiltonianCircuit-1-150x150.png\" alt=\"Triangular graph with 4 vertices and 6 edges. The outer vertices of the triangle are labeled A, B, and C, and there is one vertex in the center of the triangle labeled D. AB is labeled 4, AC is labeled 2, AD is labeled1, BC is labeled 13, BD is labeled 9, and CD is labeled 8.\" width=\"200\" height=\"174\" srcset=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/07165127\/HamiltonianCircuit-1-65x56.png 65w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/07165127\/HamiltonianCircuit-1-225x195.png 225w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/07165127\/HamiltonianCircuit-1.png 289w\" sizes=\"(max-width: 200px) 100vw, 200px\" \/><\/div>\n<p>&nbsp;<\/p>\n<p>The cheapest edge is [latex]AD[\/latex], with a cost of [latex]1[\/latex]. We highlight that edge to mark it selected. The next shortest edge is [latex]AC[\/latex], with a weight of [latex]2[\/latex], so we highlight that edge.<\/p>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-6390\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10141815\/HamiltonianCircuit-2-1.png\" alt=\"triangular graph with 4 vertices and 6 edges. There is one vertex in the center of the triangle. The edge between A and D is highlighted\" width=\"200\" height=\"174\" srcset=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10141815\/HamiltonianCircuit-2-1.png 289w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10141815\/HamiltonianCircuit-2-1-65x56.png 65w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10141815\/HamiltonianCircuit-2-1-225x195.png 225w\" sizes=\"(max-width: 200px) 100vw, 200px\" \/><\/div>\n<p>\u00a0<\/p>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-6391\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10141908\/HamiltonianCircuit-3.png\" alt=\"triangular graph with 4 vertices and 6 edges. There is one vertex in the center of the triangle. Edges between A and D and A and C are highlighted.\" width=\"200\" height=\"174\" srcset=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10141908\/HamiltonianCircuit-3.png 289w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10141908\/HamiltonianCircuit-3-65x56.png 65w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10141908\/HamiltonianCircuit-3-225x195.png 225w\" sizes=\"(max-width: 200px) 100vw, 200px\" \/><\/div>\n<p>&nbsp;<\/p>\n<p>For the third edge, we\u2019d like to add [latex]AB[\/latex], but that would give vertex [latex]A[\/latex] degree [latex]3[\/latex], which is not allowed in a Hamiltonian circuit. The next shortest edge is [latex]CD[\/latex], but that edge would create a circuit [latex]ACDA[\/latex] that does not include vertex [latex]B[\/latex], so we reject that edge. The next shortest edge is [latex]BD[\/latex], so we add that edge to the graph.<\/p>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-6393\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142033\/HamiltonianCircuit-4.png\" alt=\"triangular graph with 4 vertices and 6 edges. There is one vertex in the center of the triangle. Edges between A and D and A and C are highlighted. Edge between A and B is highlighted.\" width=\"200\" height=\"174\" srcset=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142033\/HamiltonianCircuit-4.png 289w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142033\/HamiltonianCircuit-4-65x56.png 65w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142033\/HamiltonianCircuit-4-225x195.png 225w\" sizes=\"(max-width: 200px) 100vw, 200px\" \/><\/div>\n<p style=\"text-align: center;\"><strong>Bad<\/strong><\/p>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-6394\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142131\/HamiltonianCircuit-5.png\" alt=\"triangular graph with 4 vertices and 6 edges. There is one vertex in the center of the triangle. Edges between A and D and A and C are highlighted.\" width=\"200\" height=\"174\" srcset=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142131\/HamiltonianCircuit-5.png 289w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142131\/HamiltonianCircuit-5-65x56.png 65w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142131\/HamiltonianCircuit-5-225x195.png 225w\" sizes=\"(max-width: 200px) 100vw, 200px\" \/><\/div>\n<p style=\"text-align: center;\"><strong>Bad<\/strong><\/p>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-6395\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142216\/HamiltonianCircuit-6.png\" alt=\"triangular graph with 4 vertices and 6 edges. There is one vertex in the center of the triangle. Edges between A and D and A and C are highlighted.\" width=\"200\" height=\"174\" srcset=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142216\/HamiltonianCircuit-6.png 289w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142216\/HamiltonianCircuit-6-65x56.png 65w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142216\/HamiltonianCircuit-6-225x195.png 225w\" sizes=\"(max-width: 200px) 100vw, 200px\" \/><\/div>\n<p style=\"text-align: center;\"><strong>Okay<\/strong><\/p>\n<p>We then add the last edge to complete the circuit: [latex]ACBDA[\/latex] with weight [latex]25[\/latex]. Notice that the algorithm did not produce the optimal circuit in this case; the optimal circuit is [latex]ACDBA[\/latex] with weight [latex]23[\/latex].<\/p>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-6396\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142316\/HamiltonianCircuit-7.png\" alt=\"Notice that the algorithm did not produce the optimal circuit in this case; the optimal circuit is ACDBA with weight 23.\" width=\"200\" height=\"174\" srcset=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142316\/HamiltonianCircuit-7.png 289w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142316\/HamiltonianCircuit-7-65x56.png 65w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142316\/HamiltonianCircuit-7-225x195.png 225w\" sizes=\"(max-width: 200px) 100vw, 200px\" \/><\/div>\n<p>&nbsp;<\/p>\n<p>While the Sorted Edge algorithm overcomes some of the shortcomings of NNA, it is still only a heuristic algorithm, and does not guarantee the optimal circuit.<\/p>\n<\/section>\n<section class=\"textbox example\">Your teacher\u2019s band, <em>Derivative Work<\/em>, is doing a bar tour in Oregon. The driving distances are shown below. Plan an efficient route for your teacher to visit all the cities and return to the starting location. Use NNA starting at Portland, and then use Sorted Edges.<\/p>\n<table style=\"width: 586px; height: 333px;\">\n<tbody>\n<tr>\n<td>&nbsp;<\/td>\n<td>\u00a0Ashland<\/td>\n<td>Astoria<\/td>\n<td>\u00a0Bend<\/td>\n<td>\u00a0Corvallis<\/td>\n<td>\u00a0Crater Lake<\/td>\n<td>\u00a0Eugene<\/td>\n<td>\u00a0Newport<\/td>\n<td>\u00a0Portland<\/td>\n<td>\u00a0Salem<\/td>\n<td>\u00a0Seaside<\/td>\n<\/tr>\n<tr>\n<td>Ashland<\/td>\n<td>&#8211;<\/td>\n<td>[latex]374[\/latex]<\/td>\n<td>[latex]200[\/latex]<\/td>\n<td>[latex]223[\/latex]<\/td>\n<td>[latex]108[\/latex]<\/td>\n<td>[latex]178[\/latex]<\/td>\n<td>[latex]252[\/latex]<\/td>\n<td>[latex]285[\/latex]<\/td>\n<td>[latex]240[\/latex]<\/td>\n<td>[latex]356[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>Astoria<\/td>\n<td>[latex]374[\/latex]<\/td>\n<td>&#8211;<\/td>\n<td>[latex]255[\/latex]<\/td>\n<td>[latex]166[\/latex]<\/td>\n<td>[latex]433[\/latex]<\/td>\n<td>[latex]199[\/latex]<\/td>\n<td>[latex]135[\/latex]<\/td>\n<td>[latex]95[\/latex]<\/td>\n<td>[latex]136[\/latex]<\/td>\n<td>[latex]17[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>Bend<\/td>\n<td>[latex]200[\/latex]<\/td>\n<td>[latex]255[\/latex]<\/td>\n<td>&#8211;<\/td>\n<td>[latex]128[\/latex]<\/td>\n<td>[latex]277[\/latex]<\/td>\n<td>[latex]128[\/latex]<\/td>\n<td>[latex]180[\/latex]<\/td>\n<td>[latex]160[\/latex]<\/td>\n<td>[latex]131[\/latex]<\/td>\n<td>[latex]247[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>Corvallis<\/td>\n<td>[latex]223[\/latex]<\/td>\n<td>[latex]166[\/latex]<\/td>\n<td>[latex]128[\/latex]<\/td>\n<td>&#8211;<\/td>\n<td>[latex]430[\/latex]<\/td>\n<td>[latex]47[\/latex]<\/td>\n<td>[latex]52[\/latex]<\/td>\n<td>[latex]84[\/latex]<\/td>\n<td>[latex]40[\/latex]<\/td>\n<td>[latex]155[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>Crater Lake<\/td>\n<td>[latex]108[\/latex]<\/td>\n<td>[latex]433[\/latex]<\/td>\n<td>[latex]277[\/latex]<\/td>\n<td>[latex]430[\/latex]<\/td>\n<td>&#8211;<\/td>\n<td>[latex]453[\/latex]<\/td>\n<td>[latex]478[\/latex]<\/td>\n<td>[latex]344[\/latex]<\/td>\n<td>[latex]389[\/latex]<\/td>\n<td>[latex]423[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>Eugene<\/td>\n<td>[latex]178[\/latex]<\/td>\n<td>[latex]199[\/latex]<\/td>\n<td>[latex]128[\/latex]<\/td>\n<td>[latex]47[\/latex]<\/td>\n<td>[latex]453[\/latex]<\/td>\n<td>&#8211;<\/td>\n<td>[latex]91[\/latex]<\/td>\n<td>[latex]110[\/latex]<\/td>\n<td>[latex]64[\/latex]<\/td>\n<td>[latex]181[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>Newport<\/td>\n<td>[latex]252[\/latex]<\/td>\n<td>[latex]135[\/latex]<\/td>\n<td>[latex]180[\/latex]<\/td>\n<td>[latex]52[\/latex]<\/td>\n<td>[latex]478[\/latex]<\/td>\n<td>[latex]91[\/latex]<\/td>\n<td>&#8211;<\/td>\n<td>[latex]114[\/latex]<\/td>\n<td>[latex]83[\/latex]<\/td>\n<td>[latex]117[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>Portland<\/td>\n<td>[latex]285[\/latex]<\/td>\n<td>[latex]95[\/latex]<\/td>\n<td>[latex]160[\/latex]<\/td>\n<td>[latex]84[\/latex]<\/td>\n<td>[latex]344[\/latex]<\/td>\n<td>[latex]110[\/latex]<\/td>\n<td>[latex]114[\/latex]<\/td>\n<td>&#8211;<\/td>\n<td>[latex]47[\/latex]<\/td>\n<td>[latex]78[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>Salem<\/td>\n<td>[latex]240[\/latex]<\/td>\n<td>[latex]136[\/latex]<\/td>\n<td>[latex]131[\/latex]<\/td>\n<td>[latex]40[\/latex]<\/td>\n<td>[latex]389[\/latex]<\/td>\n<td>[latex]64[\/latex]<\/td>\n<td>[latex]83[\/latex]<\/td>\n<td>[latex]47[\/latex]<\/td>\n<td>&#8211;<\/td>\n<td>[latex]118[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>Seaside<\/td>\n<td>[latex]356[\/latex]<\/td>\n<td>[latex]17[\/latex]<\/td>\n<td>[latex]247[\/latex]<\/td>\n<td>[latex]155[\/latex]<\/td>\n<td>[latex]423[\/latex]<\/td>\n<td>[latex]181[\/latex]<\/td>\n<td>[latex]117[\/latex]<\/td>\n<td>[latex]78[\/latex]<\/td>\n<td>[latex]118[\/latex]<\/td>\n<td>&#8211;<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<div class=\"qa-wrapper\" style=\"display: block\"><button class=\"show-answer show-answer-button collapsed\" data-target=\"q997645\">Show Solution<\/button> <\/p>\n<div id=\"q997645\" class=\"hidden-answer\" style=\"display: none\"> Using NNA with a large number of cities, you might find it helpful to mark off the cities as they\u2019re visited to keep from accidently visiting them again. Looking in the row for Portland, the smallest distance is [latex]47[\/latex], to Salem.<\/p>\n<p>Following that idea, our circuit will be:<\/p>\n<p>[latex]\\begin{array} {ll} \\text{Portland to Salem} & 47 \\\\ \\text{Salem to Corvallis} & 40 \\\\ \\text{Corvallis to Eugene} & 47 \\\\ \\text{Eugene to Newport} & 91 \\\\ \\text{Newport to Seaside} & 117 \\\\ \\text{Seaside to Astoria} & 17 \\\\ \\text{Astoria to Bend} & 255 \\\\ \\text{Bend to Ashland} & 200 \\\\ \\text{Ashland to Crater Lake} & 108 \\\\ \\text{Crater Lake to Portland} & 344 \\\\ \\text{Total trip length: } & 1266\\text{ miles} \\end{array}[\/latex]<\/p>\n<p>Using Sorted Edges, you might find it helpful to draw an empty graph, perhaps by drawing vertices in a circular pattern. Adding edges to the graph as you select them will help you visualize any circuits or vertices with degree [latex]3[\/latex].<\/p>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-medium wp-image-6398\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142420\/Oregon-Circuit-1-300x199.png\" alt=\"ring of dots with city names in problem as labels.\" width=\"300\" height=\"199\" srcset=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142420\/Oregon-Circuit-1-300x199.png 300w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142420\/Oregon-Circuit-1-65x43.png 65w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142420\/Oregon-Circuit-1-225x149.png 225w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142420\/Oregon-Circuit-1-350x232.png 350w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142420\/Oregon-Circuit-1.png 686w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/div>\n<p>&nbsp;<\/p>\n<p>We start adding the shortest edges:<\/p>\n<p>[latex]\\begin{array} {ll} \\text{Seaside to Astoria} & 17\\text{ miles} \\\\ \\text{Corvallis to Salem} & 40\\text{ miles} \\\\ \\text{Portland to Salem} & 47\\text{ miles} \\\\ \\text{Corvallis to Eugene} & 47\\text{ miles} \\end{array}[\/latex] <img loading=\"lazy\" decoding=\"async\" class=\"size-medium wp-image-6399 alignright\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142512\/Oregon-Circuit-2-300x199.png\" alt=\"ring of dots with city names in problem as labels. edges between Seaside and Astoria, Eugene and Corvallis, Salem and Corvallis, and Salem and Portland.\" width=\"300\" height=\"199\" srcset=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142512\/Oregon-Circuit-2-300x199.png 300w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142512\/Oregon-Circuit-2-65x43.png 65w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142512\/Oregon-Circuit-2-225x149.png 225w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142512\/Oregon-Circuit-2-350x232.png 350w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142512\/Oregon-Circuit-2.png 686w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/p>\n<p>The graph after adding these edges is shown to the right.\u00a0 The next shortest edge is from Corvallis to Newport at [latex]52[\/latex] miles, but adding that edge would give Corvallis degree [latex]3[\/latex]. Continuing on, we can skip over any edge pair that contains Salem or Corvallis, since they both already have degree [latex]2[\/latex].<\/p>\n<p>[latex]\\begin{array} {ll} \\text{Portland to Seaside} & 78\\text{ miles} \\\\ \\text{Eugene to Newport} & 91\\text{ miles} \\\\ \\text{Portland to Astoria} & \\text{(reject \u2013 closes circuit)} \\\\ \\text{Ashland to Crater Lk} & 108\\text{ miles} \\end{array}[\/latex] <img loading=\"lazy\" decoding=\"async\" class=\"wp-image-6401 size-medium alignright\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142619\/Oregon-Circuit-3-300x199.png\" alt=\"ring of dots with city names in problem as labels. edges between Seaside and Astoria, Seaside and Portland, Eugene and Corvallis, Eugene and Newport, Salem and Corvallis, Salem and Portland, and Ashland and Crater Lake..\" width=\"300\" height=\"199\" srcset=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142619\/Oregon-Circuit-3-300x199.png 300w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142619\/Oregon-Circuit-3-65x43.png 65w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142619\/Oregon-Circuit-3-225x149.png 225w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142619\/Oregon-Circuit-3-350x232.png 350w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142619\/Oregon-Circuit-3.png 686w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/p>\n<p>The graph after adding these edges is shown to the right. At this point, we can skip over any edge pair that contains Salem, Seaside, Eugene, Portland, or Corvallis since they already have degree [latex]2[\/latex]. \u00a0<\/p>\n<p>[latex]\\begin{array} {ll} \\text{Newport to Astoria} & \\text{(reject \u2013 closes circuit)} \\\\ \\text{Newport to Bend} & 180\\text{ miles} \\\\ \\text{Bend to Ashland} & 200\\text{ miles} \\end{array}[\/latex]<\/p>\n<p>At this point the only way to complete the circuit is to add:<\/p>\n<p>Crater Lk to Astoria\u00a0\u00a0 [latex]433[\/latex] miles.<\/p>\n<p>\u00a0The final circuit, written to start at Portland, is:<\/p>\n<p>Portland, Salem, Corvallis, Eugene, Newport, Bend, Ashland, Crater Lake, Astoria, Seaside, Portland.<\/p>\n<p>\u00a0Total trip length: [latex]1241[\/latex] miles.<\/p>\n<p>While better than the NNA route, neither algorithm produced the optimal route. The following route can make the tour in [latex]1069[\/latex] miles:<\/p>\n<p>Portland, Astoria, Seaside, Newport, Corvallis, Eugene, Ashland, Crater Lake, Bend, Salem, Portland<\/p>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-6403 size-medium\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142708\/Oregon-Circuit-4-300x199.png\" alt=\"ring of dots with city names in problem as labels. edges between Seaside and Astoria, Seaside and Portland, Eugene and Corvallis, Eugene and Newport, Salem and Corvallis, Salem and Portland, Ashland and Crater Lake, Ashland and Bend, Bend and Newport, and Astoria and Crater Lake.\" width=\"300\" height=\"199\" srcset=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142708\/Oregon-Circuit-4-300x199.png 300w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142708\/Oregon-Circuit-4-65x43.png 65w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142708\/Oregon-Circuit-4-225x149.png 225w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142708\/Oregon-Circuit-4-350x232.png 350w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/05\/10142708\/Oregon-Circuit-4.png 686w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/div>\n<p>&nbsp;<\/p>\n<p>Watch the example of nearest neighbor algorithm for traveling from city to city using a table worked out in the video below.<\/p>\n<p><iframe loading=\"lazy\" id=\"oembed-1\" title=\"Nearest Neighbor from a table\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/GFp-046PQx0?feature=oembed&#38;rel=0\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<p>You can view the <a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Nearest+Neighbor+from+a+table.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cNearest Neighbor from a table\u201d here (opens in new window).<\/a><\/p>\n<p>In the next video we use the same table, but use sorted edges to plan the trip.<\/p>\n<p><iframe loading=\"lazy\" title=\"YouTube video player\" src=\"https:\/\/www.youtube.com\/embed\/_gXyujMsrmw?si=vFgQ3MgLwgHxwt50\" width=\"560\" height=\"315\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<p>You can view the <a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Sorted+Edges+from+a+table.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cSorted Edges from a table\u201d here (opens in new window).<\/a><\/p>\n<\/div>\n<\/div>\n<\/section>\n<section class=\"textbox tryIt\"><iframe loading=\"lazy\" id=\"ohm6966\" class=\"resizable\" src=\"https:\/\/ohm.one.lumenlearning.com\/multiembedq.php?id=6966&theme=lumen&iframe_resize_id=ohm6966&source=tnh\" width=\"100%\" height=\"150\"><\/iframe><\/section>\n","protected":false},"author":15,"menu_order":12,"template":"","meta":{"_candela_citation":"[{\"type\":\"original\",\"description\":\"Revision and Adaptation\",\"author\":\"\",\"organization\":\"Lumen Learning\",\"url\":\"\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"\"},{\"type\":\"cc\",\"description\":\"Math in Society\",\"author\":\"David Lippman\",\"organization\":\"\",\"url\":\"http:\/\/www.opentextbookstore.com\/mathinsociety\/\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"\"}]","pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":[],"pb_section_license":""},"chapter-type":[],"contributor":[],"license":[],"part":75,"module-header":"learn_it","content_attributions":[{"type":"original","description":"Revision and Adaptation","author":"","organization":"Lumen Learning","url":"","project":"","license":"cc-by","license_terms":""},{"type":"cc","description":"Math in Society","author":"David Lippman","organization":"","url":"http:\/\/www.opentextbookstore.com\/mathinsociety\/","project":"","license":"cc-by","license_terms":""}],"internal_book_links":[],"video_content":null,"cc_video_embed_content":{"cc_scripts":"","media_targets":[]},"try_it_collection":null,"_links":{"self":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/2699"}],"collection":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/users\/15"}],"version-history":[{"count":97,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/2699\/revisions"}],"predecessor-version":[{"id":15927,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/2699\/revisions\/15927"}],"part":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/parts\/75"}],"metadata":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/2699\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/media?parent=2699"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapter-type?post=2699"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/contributor?post=2699"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/license?post=2699"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}