Hillgrove - Home



The traveling salesman problem requires us to find the longest Hamilton Circuit.TrueFalseThe nearest-neighbor algorithm constructs a(n) ____________ circuit in a complete graph by starting at a vertex.FleuryEulerVectorHamiltonWhen applying the nearest-neighbor algorithm, if there are two or more vertices equally nearby, any one of them may be selected.TrueFalseWhen applying the cheapest-link algorithm, do not choose an edge that would result in a vertex of degree _____?The edges in a certain graph represent roads, and the vertices represent intersections. We want to clean all of the roads and not require the street sweeper to move along streets that have already been cleaned. Should we look for an Euler circuit or a Hamilton circuit?The edges in a certain graph represent roads, and the vertices represent intersections. We want to time the traffic signals at each intersection and not visit any intersection twice. Should we look for an Euler circuit or a Hamilton circuit?Use the graph below to answer the TWO following scenarios:A traveling salesman must visit all four cities indicated in the figure below. How many miles does he travel if he starts in A then visits B, C, and D before returning to A?A traveling salesman must visit all four cities indicated in the figure. How many miles will he travel if he starts in A then visits D, B, and C before returning to A? -596789-24778800 Use the nearest-neighbor algorithm starting at vertex A of the figure(s) below to find an approximate solution to the traveling salesman problem and the cheapest possible Hamiltonian Circuit:right958000228462864100Solution: __________________Solution: ___________________1738113409953412392825500351663033020000-53779635755400Solution: __________________ Solution (start in ATL): ____________________Solution: ___________________________Solution: ___________________________Use the cheapest-link algorithm starting at vertex A of the figure(s) below to find an approximate solution to the traveling salesman problem:right958000228462864100Solution: __________________Solution: ___________________1738113409953412392825500351663033020000-53779635755400Solution: __________________ Solution (start in ATL): ____________________Solution: ___________________________Solution: ___________________________3200400190500There are 6 Hamiltonian circuits in the graph to the right. List all 6 Hamiltonian circuits. What is the total weight (distance) for each? What is the shortest Hamiltonian circuit? Using the nearest-neighbor algorithm starting at vertex D, what is the resulting circuit? What is the total weight of the nearest-neighbor circuit?40551109525 Starting at vertex A, use the nearest-neighbor to find the circuit.What is the total weight of the circuit from #13?Starting at vertex D, use the nearest-neighbor to find the circuit.What is the total weight of the nearest-neighbor circuit starting at D? ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download