Топологическая сортировка с целевой функцией

У меня есть DAG с N узлами, т.е. 1, 2, ..., N, и каждый node имеет вес (мы можем назвать это время) x_1, x_2, ..., x_N. Я хочу сделать топологическую сортировку, но сложность в том, что у меня есть объективная функция при сортировке. Моя целевая функция заключается в минимизации общего времени между несколькими парами узлов.

Например, у меня есть DAG с 6 узлами, и я хочу определенную топологическую сортировку, такую, что (1,3) + (2,4) минимизируется, где (A,B) обозначает время между двумя узлами A и B. Например, если у нас есть sort [1, 6, 3, 2, 5, 4, 7], (1,3) = x_6 и (2,4) = x_5. Основываясь на DAG, я хочу найти сортировку, которая минимизирует (1,3) + (2,4).

Я думал об этой проблеме некоторое время. Сгенерировать все возможные топологические типы (ссылка ссылка) и вычислять целевую функцию по одному всегда можно, но требуется слишком много времени, если N велико. Мне также предлагалось использовать обрезку, связанную с веткой, при создании всех возможных видов (я не очень хорошо знаком с веткой, но я думаю, что это не приведет к значительному снижению сложности).

Любой (оптимальный или эвристический) алгоритм для такого рода задач? Было бы идеально, если бы алгоритм можно было применить и к другим объективным функциям, таким как минимизация общего времени начала для некоторых узлов. Любое предложение оценивается.

PS: Или, альтернативно, можно ли сформулировать эту проблему как проблему линейной цельной оптимизации?

Ответ 1

Один из способов решить эту проблему:

Сначала мы запускаем алгоритм кратчайшего пути для всех пар Floyd-Warshall. Этот алгоритм может быть закодирован в по существу 5 строк кода и работает в O(V^3) времени. Он генерирует кратчайшие пути между каждой из пары вершин в графе, т.е. Он генерирует матрицу V X V кратчайших путей в качестве ее выхода.

Тривиально модифицировать этот алгоритм, чтобы мы могли также получить количество вершин, включенных в каждый из путей O(N^2). Итак, теперь мы можем устранить все пути, у которых меньше N вершин. Для остальных путей мы заказываем их по их стоимости, а затем проверяем каждую из них, чтобы убедиться, что свойство топологической сортировки не нарушено. Если это свойство не нарушено, то мы нашли желаемый результат.

Последний шаг выше, т.е. тестирование топологической сортировки может выполняться в O (V + E) для каждого из путей O (V ^ 2). Это дает наихудшее время выполнения O(V^4). Однако на практике это должно быть быстрым, потому что Floyd-Warshall может быть очень дружелюбным к кэшу, и в действительности мы будем тестировать только небольшую часть путей O (N ^ 2). Кроме того, если ваша группа DAG не плотна, вы также сможете оптимизировать топологическое тестирование с соответствующими структурами данных.

Ответ 2

Вот идея:

Для простоты сначала предположим, что у вас есть одна пара для оптимизации (я расскажу об общем случае позже), и предположим, что у вас уже есть топологически отсортированный граф в массив.

Возьмите сегмент массива, начиная с нижнего (в терминах вашего топологического порядка) node пары, скажем l и заканчивая на более высоком node, скажем h. Для каждого node, отсортированного между l и h, вычислите, ограничено ли оно снизу на l и/или ограничено сверху h. Вы можете рассчитать прежнее свойство, пометив узлы в "вверх" BFS из l, вырезая узлы отсортированные выше h; и аналогично, последний путем маркировки в "нисходящей" BFS от h, разрезая узлы отсортированные ниже l. Сложность любого прохода будет O (B * L), где B - коэффициент ветвления, а l - количество узлов, первоначально отсортированных между l и h.

Теперь все узлы, которые не ограничены сверху h, могут перемещаться выше h, а все узлы, которые не ограничены снизу на l, можно перемещать ниже l (эти два набора могут перекрытие,), без нарушения топологической сортировки массива при условии, что исходный упорядоченный порядок в каждой группе узлов, перемещенных вверх или вниз, сохраняется.

Эта же процедура может применяться к как можно большему количеству пар при условии, что сегменты, которые они вырезали из первоначального порядка сортировки, не перекрываются.

Если любые две пары перекрываются, скажем (l1, h1) и (l2, h2), так что, например, l1 < l2 < h1 < h2 в исходном отсортированном порядке, у вас есть следующие два случая:

1) В тривиальном случае, когда h1 и l2 не связаны между собой в топологическом порядке, вы должны иметь возможность оптимизировать две пары, в основном независимо друг от друга, только применяя некоторую осторожность для перемещения либо l2 выше h1, либо h1 ниже l2 (но не, например h1 ниже l1, если это окажется возможным).

2) Если l2 < h1 в топологическом порядке, вы можете рассматривать обе пары как одну пару (l1, h2), а затем, возможно, снова применить процедуру к (l2, h1).

Как только неясно, какой полный процесс будет достигнут в нетривиальном перекрывающемся случае, особенно если у вас есть более сложные перекрывающиеся шаблоны, может оказаться лучше обрабатывать все пары равномерно, независимо от перекрытия. В этом случае порядок может обрабатываться повторно, в то время как каждый прогон дает улучшение по сравнению с предыдущим (я не уверен, будет ли процедура монотонной с точки зрения целевой функции, хотя, вероятно, нет.)