HMMT 二月 2006 · 冲刺赛 · 第 44 题

HMMT February 2006 — Guts Round — Problem 44

On the Euclidean plane are given 14 points: A = (0 , 428) B = (9 , 85) C = (42 , 865) D = (192 , 875) E = (193 , 219) F = (204 , 108) G = (292 , 219) H = (316 , 378) I = (375 , 688) J = (597 , 498) K = (679 , 766) L = (739 , 641) M = (772 , 307) N = (793 , 0) A fly starts at A , visits all the other points, and comes back to A in such a way as to minimize the total distance covered. What path did the fly take? Give the names of the points it visits in order. Your score will be 20 + b the optimal distance c − b your distance c or 0, whichever is greater.

解析

On the Euclidean plane are given 14 points: A = (0 , 428) B = (9 , 85) C = (42 , 865) D = (192 , 875) E = (193 , 219) F = (204 , 108) G = (292 , 219) H = (316 , 378) I = (375 , 688) J = (597 , 498) K = (679 , 766) L = (739 , 641) M = (772 , 307) N = (793 , 0) A fly starts at A , visits all the other points, and comes back to A in such a way as to minimize the total distance covered. What path did the fly take? Give the names of the points it visits in order. Your score will be 20 + b the optimal distance c − b your distance c or 0, whichever is greater. Answer: The optimal path is ACDIKLJM N HGEF B ( A ), or the reverse, of course. In this way the total distance covered by the fly is just over 3591 . 22. Solution: This problem is an instance of the Traveling Salesman Problem, which is NP-hard. There is an obvious algorithm in O ( n !) time (where n is the number of points), but faster algorithms exist. Nonetheless, the best strategy for solving this problem is probably to draw the points and exercise your geometric intuition. 16