IBM Ponder This #060 · 2003 年 4 月

在平面单位圆盘内任意放置 N 个点，称为一个点配置。从某点出发，恰好访问其余每个点一次，再返回起点，构成哈密顿巡游。

相邻两点间的费用定义为欧氏距离的平方，例如距离 0.8 的费用为 0.64。巡游总费用是 N 条边费用之和；一个点配置的“价格”是其所有哈密顿巡游中的最小费用。

平方距离不满足三角不等式，因此除起终点外，不允许重复访问任何点。

研究所有点配置价格的最大可能值。给出与 N 无关的上界 U，证明任何配置的价格都不超过 U；再给出尽量大的下界 L，并构造价格至少为 L 的配置。希望 U 和 L 尽可能接近。

官方 4 月 18 日补充：一些读者用内接正三角形给出了 L=9。出题人指出，一种常见的上界证明有漏洞：不能因为删去钝角 ABC 的顶点 B 会使某条 N-1 点巡游更昂贵，就断言新点配置的最优巡游也更昂贵；它的最优巡游未必包含边 AC。

解答

认真尝试后再打开

待补充。