找出图中节点的排序，使边长之和最小
Find an ordering of nodes in a graph that minimizes sum of edge lengths
输入：具有 n 个顶点的连通无向图 G。
输出：最小化
的顶点0, 1, ..., n - 1的线性排序
sum(j - i for i in range(n) for j in range(n) if i < j and (i, j) in G).
n可能是1000000左右，边的个数会是一个比n大的常数因子，在5000000左右。稍微一般一点的问题，边可能有小的正整数权重。首选精确解，但不是必需的。
一种方法可能是冒泡排序的变体，如果它能降低总和，则交换元素。但是我不确定这个算法是否会陷入局部最小值。
您的任务似乎是最小线性分配问题。网上有一篇关于该主题的博士论文（Seitz, Hanna - Contributions to the
最小线性 Ar运行gement
Problem ) 具有易于理解的说明（参见第 27 页及以后）。
问题是 NP-hard。引用的资源将最著名算法的复杂性报告为 O(|E| * 2^|V|)（第 29 页及以后）。它还列出了 类 已知高效（多项式）算法的图，并讨论了近似方案。
PS:
不是这里的专家，只是 运行 问题和论文，这似乎是一个很好的起点。
输入：具有 n 个顶点的连通无向图 G。
输出：最小化
的顶点0, 1, ..., n - 1的线性排序
sum(j - i for i in range(n) for j in range(n) if i < j and (i, j) in G).
n可能是1000000左右，边的个数会是一个比n大的常数因子，在5000000左右。稍微一般一点的问题，边可能有小的正整数权重。首选精确解，但不是必需的。
一种方法可能是冒泡排序的变体，如果它能降低总和，则交换元素。但是我不确定这个算法是否会陷入局部最小值。
您的任务似乎是最小线性分配问题。网上有一篇关于该主题的博士论文（Seitz, Hanna - Contributions to the 最小线性 Ar运行gement Problem ) 具有易于理解的说明（参见第 27 页及以后）。
问题是 NP-hard。引用的资源将最著名算法的复杂性报告为 O(|E| * 2^|V|)（第 29 页及以后）。它还列出了 类 已知高效（多项式）算法的图，并讨论了近似方案。
PS:
不是这里的专家，只是 运行 问题和论文，这似乎是一个很好的起点。