Найти порядок узлов в графе, который минимизирует сумму длин ребер

Question

Вход: связанный неориентированный граф G с n вершинами.

Выход: линейное упорядочение вершин 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. В чуть более общей задаче ребра могут иметь небольшие положительные целые веса. Точное решение является предпочтительным, но не обязательным.

Одним из подходов может быть вариант пузырьковой сортировки, который меняет местами элементы, если это приведет к уменьшению суммы. Но я не уверен, что этот алгоритм застрянет в локальном минимуме.

Answer 1

Похоже, у вас есть задача с минимальным линейным назначением. Существует кандидатская диссертация на эту тему c, доступная онлайн ( Зейтц, Ханна - вклад в задачу минимального линейного расположения ), которая имеет доступную экспозицию (см. Стр. 27 и далее).

Проблема NP-трудна. Цитируемый ресурс сообщает о сложности самого известного алгоритма как O(|E| * 2^|V|) (стр. 29 и далее). В нем также перечислены классы графов, для которых известны эффективные (полиномиальные) алгоритмы, и обсуждаются схемы аппроксимации.

PS:
Здесь не эксперт, просто натолкнулся на проблему и тезис, который представляется хорошим отправная точка.