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

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

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

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

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

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


graph algorithm topological-sort
person MIMIGA    schedule 13.07.2016    source источник
comment
Я подозреваю, что эта проблема сложна, потому что есть два ее небольших варианта: (1) Если сумму расстояний заменить на максимум расстояний, то вы можете уменьшить NP-жесткая задача минимизации полосы пропускания к этой задаче (начиная с входного графа G, удалите все ребра и добавьте одну корневую вершину с исходящим ребром к каждой другой вершине - это означает, что любой порядок исходных n вершин является допустимым топологическим порядком — и для каждого ребра (u, v) в G (которое вы удалили) добавьте член (u,v) к целевой функции, которую необходимо минимизировать); ...   -  person j_random_hacker    schedule 18.07.2016
comment
... (2) если вместо этого вы сохраните сумму (а не максимум) расстояний между парами, но немного обобщите целевую функцию, чтобы позволить каждому члену (например, (1,3) или (2,4) в вашем примере) умножаться на отдельный вес, то таким же образом можно свести NP-трудную квадратичную задачу о назначениях к этой задаче. Возможно, даже частный случай QAP, где каждый вес равен 1, по-прежнему NP-труден — это означало бы, что ваша проблема тоже — но я не смог подтвердить это с помощью нескольких Google.   -  person j_random_hacker    schedule 18.07.2016
comment
@j_random_hacker. Спасибо за ответ. Я также считаю, что эта задача является NP-сложной. Я понял, что моя проблема похожа на проблему коммивояжера. Я не знаю о проблеме квадратичного назначения и проблеме минимизации пропускной способности. Спасибо за связь. Я уже разработал эвристический метод для этой задачи. Однако я ищу формулировку комбинаторной оптимизации, в которой можно было бы применить метод ветвей и границ для получения оптимального решения для сравнения моего эвристического метода.   -  person MIMIGA    schedule 18.07.2016
comment
Помните, что для демонстрации NP-сложности нам нужно иметь возможность взять произвольный экземпляр какой-нибудь известной NP-сложной задачи (например, QAP) и механически преобразовать его в экземпляр вашей задачи. Для сокращений, которые я дал, мы создаем экземпляр вашей проблемы, где единственным ограничением приоритета является то, что корневая вершина должна быть первой: это допустимый возможный экземпляр вашей проблемы, поэтому алгоритм, решающий вашу проблему, должен быть в состоянии решить ее. . Посмотрите (например, в Google), как можно использовать сокращения из NP-сложных задач, чтобы показать NP-сложность проблемы, если вы запутались.   -  person j_random_hacker    schedule 18.07.2016
comment
(Для ясности: нам нужно больше, чем просто показать, что экземпляры NP-сложной задачи могут быть преобразованы в экземпляры вашей проблемы — но ключевой момент здесь в том, что не имеет значения, допускает ли ваша проблема другие ограничения, которые мы не допускаем. не использовать или полностью использовать в сокращении.)   -  person j_random_hacker    schedule 18.07.2016
comment
Моя цель не в том, чтобы показать NP-жесткость. Я ищу оптимальный алгоритм для сравнения с моим эвристическим методом. Я думаю, что это можно сформулировать как задачу комбинаторной оптимизации. Извините за путаницу.   -  person MIMIGA    schedule 18.07.2016
comment
Точка демонстрации NP-трудности состоит в том, чтобы продемонстрировать, что (весьма вероятно) нет хорошего способа решить эту проблему. То есть смысл в том, чтобы избавить вас и всех, кто читает ваш вопрос, от тяжелой работы по поиску такого алгоритма, который ни к чему не приведет.   -  person j_random_hacker    schedule 18.07.2016

Ответы (2)


arrow_upward
1
arrow_downward

Один из способов решения этой проблемы заключается в следующем:

Сначала мы запускаем алгоритм кратчайшего пути All-Pairs 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 не является плотной, вы также можете оптимизировать топологическое тестирование с помощью соответствующих структур данных.

person Shital Shah    schedule 19.07.2016
comment
Пожалуйста, поправьте меня, если я ошибаюсь. Я думаю, что есть проблема для вашего метода. То есть мое оптимальное решение не обязательно минимизирует путь от начального узла к конечному узлу, т. е. мое оптимальное решение не обязательно входит в множество решений Флоя-Уоршалла. Например, если у нас есть DAG с 3 узлами, ссылка от 1 до 2, от 1 до 3 и от 2 до 3 (1 предшествует 2, 1 предшествует 3 и т. д.), и мы хотим минимизировать (1,3). Единственная возможная топологическая сортировка — [1,2,3] и (1,3)=x_2. Однако легко видеть, что все решения Флойда-Уоршалла имеют число вершин, равное 2. - person MIMIGA; 19.07.2016
comment
Я думаю, что я не очень ясно о вашем примере. В вашем примере возможна только одна топографическая сортировка, поэтому нет способа минимизировать что-либо. Насколько я понимаю, у вас есть DAG с несколькими возможными сортировками топографических данных, и вы хотите выбрать тот, который минимизирует общую стоимость основного пути в отсортированных вершинах. Может быть только путь от x к y, который вы хотите оптимизировать, что можно сделать, установив стоимость других ребер равной 0. Было бы здорово, если бы вы могли привести какой-нибудь нетривиальный полный пример. - person Shital Shah; 20.07.2016
comment
Другими словами, все возможные решения Флойда-Уоршалла могут иметь счет меньше N. Таким образом, ваш метод исключит все и не даст решения в последнем. Но у моей проблемы всегда есть решение, так как это DAG и всегда есть топологическая сортировка. Рассмотрим нетривиальную DAG с 4 узлами, ссылками от A к B, от B к C, от A к D и от D к C. Я хочу минимизировать (A, C) + (B, C). Таким образом, все кратчайшие пути имеют не более 2 отсчетов, и все они исключаются в вашем методе. Однако топологические сортировки дают два возможных решения [A,B,D,C] и [A,D,B,C]. Второе мое оптимальное решение. - person MIMIGA; 20.07.2016

arrow_upward
0
arrow_downward

Вот идея:

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

Возьмите сегмент массива, начинающийся с нижнего (с точки зрения вашего топологического порядка) узла пары, скажем, l, и заканчивая верхним узлом, скажем, h. Для каждого отдельного узла, отсортированного между 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).

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

person shinobi    schedule 13.06.2017