The graph below is an input instance for the Traveling Salesperson Problem showing the weight of each link between nodes. Considering that links not shown have infinite weight, find the correct alternative.
a) Using the Closest Neighbor heuristic, starting from node 'a' will result in the cycle a-c-d-f-e-b-a, with a total cost of 19.
b) Using the Closest Neighbor heuristic, any starting node will result in a total cost of 16.
c) Using the Cheapest Insertion heuristic, starting from the cycle a-b-c-a will result in a final cost of 16.
d) Using the Closest Neighbor heuristic, starting from node 'a' will result in the cycle a-b-e-c-d-f-a, with a total cost of 16.
e) None of the above.
Original idea by: Giorgio Rossa
No comments:
Post a Comment