Question

Question 3

Sometimes when people first hear about the Traveling Salesman problem, they think: "Oh, that's not hard. Start with a city on the map; move to the nearest unvisited city; and then on each subsequent step, move to the nearest still-unvisited city, until you're done." This strategy is called a "greedy strategy": it always goes to the nearest allowed step.

Now consider four cities, all placed along the number line. City A is at point 0, City B at point 2, City C at point 3, and City D at point 10:

A B C D

00-01-02-03-04-05-06-07-08-09-10

Now, start a traveling salesman tour at City B, and use the greedy algorithm to choose your tour of the four cities, beginning and ending at B. How long is the greedy algorithm’s tour?

Answer 1

22

Step-by-step explanation:

The tour length will be the sum of the lengths of its segments. Here, we will figure the length using the greedy algorithm.

__

Starting at B=2, the nearest unvisited city is C=3, a distance of 1.

From C, the nearest unvisited city is A=0, a distance of 3.

From A, the nearest unvisited city is D=10, a distance of 10.

The return trip from D to B is a distance of 8.

The total length of the tour is ...

1 + 3 + 10 + 8 = 22