如何排序笛卡尔坐标数组使相邻点距离最小（n≤10）

因为输入规模极小（n≤10），暴力枚举所有排列是最直接且靠谱的方案，完全不用纠结复杂算法：

• 核心思路：生成数组的所有可能排列，计算每个排列中相邻元素的距离总和，选择总和最小的排列（如果有多个最优解，任选其一即可）。
• 可行性：10个元素的全排列是3628800种，这个计算量对现代计算机来说毫无压力，几毫秒就能跑完，而且能保证拿到全局最优解。相比之下，你提到的类冒泡启发式方法很可能陷入局部最优，没法保证得到真正的最小总距离排列。

代码实现示例 #

import itertools
import math

def distance(p1, p2):
    # 计算两点间欧氏距离
    return math.hypot(p1[0]-p2[0], p1[1]-p2[1])

def find_best_order(points):
    min_total = float('inf')
    best_order = None
    for perm in itertools.permutations(points):
        total = 0
        for i in range(len(perm)-1):
            total += distance(perm[i], perm[i+1])
        if total < min_total:
            min_total = total
            best_order = perm
    return list(best_order)

# 测试输入
array = [(1, 0), (-1, 0), (0, 1), (0, -1)]
print("array =", find_best_order(array))

运行这段代码后，会输出总相邻距离最小的排列，你给出的示例[(1, 0), (0, -1), (0, 1), (-1, 0)]就是其中一种最优解（还有其他等价的最优排列，比如调整部分顺序但总距离相同的情况）。

内容的提问来源于stack exchange，提问作者EmKian