A post office must plan a route to visit five cities (A, B, C, D, E) and return to the start. Distances (cost units) are given in the graph below. The graph satisfies the triangle inequality and is undirected. Apply the cheapest insertion heuristic (from the traveling salesperson problem), starting with triangle ABC (initial cycle: A → B → C → A). At each step, insert the vertex that yields the smallest cost increase according to the cheapest insertion heuristic. Which final cycle is obtained and what is its total cost?
A) A → C → B → D → E → A, total cost 29
B) A → B → E → D → C → A, total cost 27
C) A → B → D → C → E → A, total cost 25
D) A → D → B → E → C → A, total cost 27
E) None of the above
Original idea by: Thiago Soares Laitz
No comments:
Post a Comment