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 minimizethe total distance covered. What path did the fly take? Give the names of the points it visitsin order. Your score will be
20 + b the optimal distance c − b your distance cor 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 tominimize the total distance covered. What path did the fly take? Give the names ofthe points it visits in order. Your score will be
20 + b the optimal distance c − b your distance cor 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, whichis NP-hard. There is an obvious algorithm in O ( n !) time (where n is the number ofpoints), but faster algorithms exist. Nonetheless, the best strategy for solving thisproblem is probably to draw the points and exercise your geometric intuition.
16