Question 1160836: Is it C? I want to check my answers.
Which of the following is one of the cheapest routes to pass through each vertex once starting and ending with Vertex "A" and using the Nearest Neighbor Algorithm.
A. ABDCA, $890
B. ACDBA, $900
C. ABCDA, $960
D. None of the Above
The graph for the question and the question itself are in the question here: i.imgur.com/xCsplh0.png
Answer by greenestamps(13200)   (Show Source):
You can put this solution on YOUR website!
Correct.
With the nearest neighbor algorithm, you always take the shortest/cheapest path to another vertex from the vertex you are at. With the graph shown, that is answer C.
As any good resource will tell you, the nearest neighbor algorithm will often not yield the optimal circuit, especially if it leads you to having to travel long/expensive paths near the end of the circuit.
That is exactly what happens here; the nearest neighbor algorithm has the last leg of the circuit along edge DA, which is the longest/most expensive edge in the graph.
|
|
|
