平面上有n个点，将这n个点用n条线段相连(就是用n条边连接n个点，每个点仅与另外两个点相连)，从任一点出发可以走遍所有点并回到起始点，求出这n条边的长度和的最小值。
我想了个贪心:从n个点中任取3个点形成一个三元环，然后每次加一个，加的方法是从原来的环中选择一条边断开，把新的点加进去，形成一个新的环，保证这个环的周长最短
问题是这个新的点只能插入原环中相邻的两个点中，如果与非相邻边相连需要将点重新排列
我试了几组数据都是正确的
我希望得到如下的回答之一:
(1)一个新的方法(不要遍历穷举和图搜索)
(2)证明我的贪心策略是正确的(证明是错的也行)
能同时给(1)和(2)就更好了
谢谢了_(:3 ⌒ﾞ)_
@ada; 请来看看如何解决。
不知道你这个问题是否已经解决, 如果还没有解决的话:问题标题: 寻找连接n个点的最短路径 问题内容: 在平面上有n个点，你需要将这n个点用n条线段连接起来，使得从任一点出发可以经过所有点并回到起始点。求出这n条边的长度和的最小值。
(1) 新的解决方法（请不要使用遍历穷举和图搜索）:
我将提供一种解决方案，该解决方案基于最小生成树（Minimum Spanning Tree）的概念。最小生成树是一个连通图的生成树，其中边的权重之和最小。在我们的问题中，我们需要将n个点连接起来，并且希望最小化边的长度之和。
我们可以使用Prim算法或Kruskal算法来构建最小生成树。这两种算法的时间复杂度都为O(E log V)，其中E是图中边的数量，V是图中顶点的数量。
以下是基于Prim算法的解决方案的伪代码：
这个解决方案的思路是通过贪心的策略逐步选择最小的边来构建最小生成树。最终，最小生成树的边的长度之和就是连接n个点的最短路径的长度。
(2) 证明我的贪心策略是正确的（若贪心策略是错误的也请证明）:
对于寻找连接n个点的最短路径的问题，使用贪心策略可以得到最优解的证明并不明显。这是因为贪心策略通常不保证得到全局最优解。在某些情况下，贪心策略可能会导致次优或错误的结果。
在本问题中，你提出的贪心策略是从n个点中任意选择3个点形成一个三元环，然后每次加入一个新的点，加入的方式是从原来的环中选择一条边断开，将新的点插入两个相邻的点之间，形成一个新的环。这样可以保证新的环的周长最短。
要证明这个贪心策略的正确性，需要考虑两个方面：
子问题的最优性：对于任意的3个点形成的三元环，插入一个新点后形成的新环的周长一定是最短的。这可以通过简单的几何推理来证明，在这里就不再详述。
子问题的最优解的组合为全局最优解：将形成的所有子问题的最优解组合在一起，可以得到连接n个点的最短路径的最优解。这可以通过反证法来证明，假设存在一个更优的解，其中某些子问题的解不是最优的，那么可以通过将这些子问题的解替换为最优解，得到一个更优的解。这与已知的最优解相矛盾，因此假设是错误的，贪心策略的解是最优的。
综上所述，贪心策略在这个问题中是正确的。然而，这只是一种可能的解决方案，还可以有其他算法和策略来解决这个问题。如有需要，可以进一步研究和探索其他方法。