Please Answer Q2 & Q3.

The raw city-to-city distance data (HW2data.xls) can be found in an Excel spreadsheet on Canvas. All distances are symmetric; the distance from city A to city B is the same as the distance from city B to city A. 1. Use your own intuition to get the shortest-distance circus tour you can find. Do not use any of the algorithms from class - don't worry, you'll have plenty of opportunity for that in the rest of the homework, and your grades will not depend on the quality of the solution you find in this part. For now, just try using your intuition and logie. Draw your best answer clearly on a copy of the map (HWImap.gif), and give the total distance. 2. Using the distances provided on the website (do not just go by eye, as the graphical plot is not to scale), use the traditional Nearest Neighbor heuristic from class to find the best route for the circus to take. Draw your answer clearly on a copy of the map, provide a list of the edges in the order that you choose them, and give the total distance. 3. Repeat the above question, but use the Nearest Insertion heuristic instead of Nearest Neighbor. Start your tour by choosing first the arc with minimum cost. Draw your answer clearly on a copy of the map, provide a list of the nodes in the sequence that you insert them, and give the total distance. 50 CN DG AGA SPCA 1 WS 11 TE TO wo 13 H LA 440 HOT 10 190 WE 2013 11 TO LU be 11 ve 1H 11 CEMO TAU 14 U 4 14 IKE PUL 16C M *** M 1 VILE CE 400 11 V EL SE TH PORTLAND MINNEAPOLIS BOSTON SALT LAKE_CITY BUFFALO DETRO CHICAGU CLEVELAND LINCOLN PITTSBURGH INDIANAPOLIS KANSAS CITY LEXINGTON NASHVILLE OKLAHOMA_CITY CHARLOTTE ATLANTA OAKLAND LAS VEGAS PHOENIX SAN DIEGO NEW ORLEANS JACKSONVILLE SAN ANTONIO D E F G H 1 J K KCY 1489 1498 1346 1058 929 163 737 A B 1 2 Por 3 Portland OR 0 4 Oakland CA 534 5 San Diego CA 931 6 Phoenix AZ 993 7 Salt Lake Ci UT 626 B Lincoln NE 1331 9 San Antonio TX 1728 10 New Orleans LA 2061 11 Nashville TN 1959 12 Oklahoma Cit OK 1475 13 Kansas City MO 1489 14 Las Vegas NV 744 15 Minneapolis MN 1421 16 Chicago IL 1750 17 Detroit MI 1948 18 Indianapolis IN 1878 19 Cleveland OH 2043 20 Lexington KY 2012 21 Boston MA 2529 22 Buffalo NY 2147 23 Pittsburgh PA 2155 24 Charlotte NC 2279 25 Atlanta GA 2163 26 Jacksonville FL 2444 27 hw8rawdata Oak 534 0 452 635 587 1367 1486 1917 1946 1368 1498 395 1574 1844 2062 1935 2148 2044 2682 2287 2249 2282 2127 2368 SD 931 452 0 298 631 1254 1133 1612 1741 1132 1346 267 1535 1734 1954 1788 2028 1870 2581 2189 2116 2074 1895 2096 Phx 993 635 298 0 500 977 861 1324 1445 835 1058 256 1278 1452 1670 1498 1741 1576 2295 1907 1826 1776 1598 1802 SLC 626 587 631 500 0 788 1105 1442 1392 859 929 365 988 1259 1475 1357 1563 1474 2095 1699 1666 1724 1585 1849 Lin 1331 1367 1254 977 788 0 809 845 630 374 163 1045 343 484 704 569 785 689 1332 938 883 949 837 1130 SAn 1728 1486 1133 861 1105 809 0 513 834 435 737 1091 1130 1068 1235 1012 1262 1009 1774 1448 1303 1104 898 1014 NO 2061 1917 1612 1324 1442 845 513 0 472 586 697 1525 1057 838 927 713 919 641 1356 1093 921 639 438 502 Nsh 1959 1946 1741 1445 1392 630 834 472 0 611 471 1584 695 396 458 248 452 178 941 632 1475 1368 1132 835 859 374 435 586 611 0 321 989 701 701 900 697 952 751 1500 1132 1021 942 768 1001 697 471 321 0 1156 397 400 614 444 682 547 1237 851 770 797 676 967 1 472 1 336 212 517 1 16 M N O o R S T U V W 1489 1498 1346 1058 929 163 737 697 471 321 0 1156 397 400 614 444 682 547 1237 851 770 797 676 967 LVg 744 395 267 256 365 1045 1091 1525 1584 989 1156 0 1302 1529 1749 1600 1829 1697 2377 1982 1924 1920 1756 1985 Min 1421 1574 1535 1278 988 343 1130 1057 695 701 397 1302 0 353 529 512 626 663 1119 729 740 939 900 1208 Chi 1750 1844 1734 1452 1259 484 1068 838 396 701 400 1529 353 0 220 167 303 317 Det 1948 2062 1954 1670 1475 704 1235 927 456 900 614 1749 529 220 0 225 98 299 628 237 213 506 575 844 Ind 1878 1935 1788 1498 1357 569 1012 713 248 697 444 1600 512 Cle 2043 2148 2028 1741 1563 785 1262 919 452 952 682 1829 626 303 98 257 0 278 554 185 115 437 536 784 Lex 2012 2044 1870 1576 1474 689 1009 641 178 751 547 1697 663 317 299 151 278 0 768 455 295 277 280 570 Box 2529 2682 2581 2295 2095 1332 1774 1356 941 1500 1237 2377 1119 848 628 805 554 788 0 396 480 728 921 1029 Buf 2147 2287 2189 1907 1699 938 1448 1093 632 1132 851 1982 729 455 237 440 185 455 396 0 183 553 690 904 Pit 2155 2249 2116 1826 1666 883 1303 921 472 1021 770 1924 740 409 213 329 115 295 480 183 0 372 509 723 Cha 2279 2282 2074 1776 1724 949 1104 639 336 942 797 1920 939 589 506 427 437 277 728 553 372 0 206 351 Ati 2163 2127 1895 1598 1585 837 898 436 212 768 676 1756 900 579 575 415 536 280 921 690 509 206 0 308 167 848 225 0 257 15 805 440 329 427 415 715 455 409 589 579 881 The raw city-to-city distance data (HW2data.xls) can be found in an Excel spreadsheet on Canvas. All distances are symmetric; the distance from city A to city B is the same as the distance from city B to city A. 1. Use your own intuition to get the shortest-distance circus tour you can find. Do not use any of the algorithms from class - don't worry, you'll have plenty of opportunity for that in the rest of the homework, and your grades will not depend on the quality of the solution you find in this part. For now, just try using your intuition and logie. Draw your best answer clearly on a copy of the map (HWImap.gif), and give the total distance. 2. Using the distances provided on the website (do not just go by eye, as the graphical plot is not to scale), use the traditional Nearest Neighbor heuristic from class to find the best route for the circus to take. Draw your answer clearly on a copy of the map, provide a list of the edges in the order that you choose them, and give the total distance. 3. Repeat the above question, but use the Nearest Insertion heuristic instead of Nearest Neighbor. Start your tour by choosing first the arc with minimum cost. Draw your answer clearly on a copy of the map, provide a list of the nodes in the sequence that you insert them, and give the total distance. 50 CN DG AGA SPCA 1 WS 11 TE TO wo 13 H LA 440 HOT 10 190 WE 2013 11 TO LU be 11 ve 1H 11 CEMO TAU 14 U 4 14 IKE PUL 16C M *** M 1 VILE CE 400 11 V EL SE TH PORTLAND MINNEAPOLIS BOSTON SALT LAKE_CITY BUFFALO DETRO CHICAGU CLEVELAND LINCOLN PITTSBURGH INDIANAPOLIS KANSAS CITY LEXINGTON NASHVILLE OKLAHOMA_CITY CHARLOTTE ATLANTA OAKLAND LAS VEGAS PHOENIX SAN DIEGO NEW ORLEANS JACKSONVILLE SAN ANTONIO D E F G H 1 J K KCY 1489 1498 1346 1058 929 163 737 A B 1 2 Por 3 Portland OR 0 4 Oakland CA 534 5 San Diego CA 931 6 Phoenix AZ 993 7 Salt Lake Ci UT 626 B Lincoln NE 1331 9 San Antonio TX 1728 10 New Orleans LA 2061 11 Nashville TN 1959 12 Oklahoma Cit OK 1475 13 Kansas City MO 1489 14 Las Vegas NV 744 15 Minneapolis MN 1421 16 Chicago IL 1750 17 Detroit MI 1948 18 Indianapolis IN 1878 19 Cleveland OH 2043 20 Lexington KY 2012 21 Boston MA 2529 22 Buffalo NY 2147 23 Pittsburgh PA 2155 24 Charlotte NC 2279 25 Atlanta GA 2163 26 Jacksonville FL 2444 27 hw8rawdata Oak 534 0 452 635 587 1367 1486 1917 1946 1368 1498 395 1574 1844 2062 1935 2148 2044 2682 2287 2249 2282 2127 2368 SD 931 452 0 298 631 1254 1133 1612 1741 1132 1346 267 1535 1734 1954 1788 2028 1870 2581 2189 2116 2074 1895 2096 Phx 993 635 298 0 500 977 861 1324 1445 835 1058 256 1278 1452 1670 1498 1741 1576 2295 1907 1826 1776 1598 1802 SLC 626 587 631 500 0 788 1105 1442 1392 859 929 365 988 1259 1475 1357 1563 1474 2095 1699 1666 1724 1585 1849 Lin 1331 1367 1254 977 788 0 809 845 630 374 163 1045 343 484 704 569 785 689 1332 938 883 949 837 1130 SAn 1728 1486 1133 861 1105 809 0 513 834 435 737 1091 1130 1068 1235 1012 1262 1009 1774 1448 1303 1104 898 1014 NO 2061 1917 1612 1324 1442 845 513 0 472 586 697 1525 1057 838 927 713 919 641 1356 1093 921 639 438 502 Nsh 1959 1946 1741 1445 1392 630 834 472 0 611 471 1584 695 396 458 248 452 178 941 632 1475 1368 1132 835 859 374 435 586 611 0 321 989 701 701 900 697 952 751 1500 1132 1021 942 768 1001 697 471 321 0 1156 397 400 614 444 682 547 1237 851 770 797 676 967 1 472 1 336 212 517 1 16 M N O o R S T U V W 1489 1498 1346 1058 929 163 737 697 471 321 0 1156 397 400 614 444 682 547 1237 851 770 797 676 967 LVg 744 395 267 256 365 1045 1091 1525 1584 989 1156 0 1302 1529 1749 1600 1829 1697 2377 1982 1924 1920 1756 1985 Min 1421 1574 1535 1278 988 343 1130 1057 695 701 397 1302 0 353 529 512 626 663 1119 729 740 939 900 1208 Chi 1750 1844 1734 1452 1259 484 1068 838 396 701 400 1529 353 0 220 167 303 317 Det 1948 2062 1954 1670 1475 704 1235 927 456 900 614 1749 529 220 0 225 98 299 628 237 213 506 575 844 Ind 1878 1935 1788 1498 1357 569 1012 713 248 697 444 1600 512 Cle 2043 2148 2028 1741 1563 785 1262 919 452 952 682 1829 626 303 98 257 0 278 554 185 115 437 536 784 Lex 2012 2044 1870 1576 1474 689 1009 641 178 751 547 1697 663 317 299 151 278 0 768 455 295 277 280 570 Box 2529 2682 2581 2295 2095 1332 1774 1356 941 1500 1237 2377 1119 848 628 805 554 788 0 396 480 728 921 1029 Buf 2147 2287 2189 1907 1699 938 1448 1093 632 1132 851 1982 729 455 237 440 185 455 396 0 183 553 690 904 Pit 2155 2249 2116 1826 1666 883 1303 921 472 1021 770 1924 740 409 213 329 115 295 480 183 0 372 509 723 Cha 2279 2282 2074 1776 1724 949 1104 639 336 942 797 1920 939 589 506 427 437 277 728 553 372 0 206 351 Ati 2163 2127 1895 1598 1585 837 898 436 212 768 676 1756 900 579 575 415 536 280 921 690 509 206 0 308 167 848 225 0 257 15 805 440 329 427 415 715 455 409 589 579 881