欧几里得平面点集最短遍历路径是否必含两条最短线段的技术咨询

你好！先帮你明确一下问题：你说的其实是欧几里得平面上点集的最短哈密顿路径——也就是一条可以任选起点终点、能经过所有点恰好一次的路径，总长度要最短，其中路径里的中间点会连接两条边，起点和终点各连接一条边。你观察到3个点的时候，这条最短路径肯定会包含两条最短的边，现在想问这个规律是不是对任意数量的点都成立。

首先，3个点的情况确实和你说的一样：因为3个点的哈密顿路径就是两条边拼起来，总长度最短的组合自然是两条最短边的和——毕竟拿最长的边加任何一条，总长度都会更长。

对于任意数量的点，我们分两种情况讨论：

• 如果点集里只有一条最短边：那显然没法包含两条，这种情况你的结论自然不适用。
• 如果点集里至少有两条最短边：你的结论是对的——最短哈密顿路径一定会包含至少两条最短边。

你可以这么理解：假设最短路径里只包含0条或者1条最短边，那我们总能通过替换路径里的边，得到一条更短的路径，这就和“最短路径”的定义矛盾了。比如，假设路径里只有一条最短边AB，另一条最短边CD没被用上，那路径里C和D肯定连的是更长的边，我们把其中一条换成CD，调整一下路径结构，总长度肯定会更短；如果一条最短边都没用到，那随便选一条最短边替换掉路径里的一条长边，总长度也会变短。

不过要注意哦，这里说的“两条最短边”是指所有边里长度最小的那些（可能不止两条），最短路径至少会包含其中两条。

备注：内容来源于stack exchange，提问作者AonSoo