Предположим, у меня есть ориентированный ациклический граф с весами действительных чисел в его вершинах. Я хочу найти топологический порядок DAG, в котором для каждого префикса топологического порядка сумма весов неотрицательна. Или, если вы предпочитаете теоретико-порядковую терминологию, у меня есть взвешенный частичный порядок, и я хочу линейное расширение, чтобы каждый префикс имел неотрицательный вес. Что известно об этой проблеме? Это NP-полный или разрешимый за полиномиальное время?
ds.algorithms
directed-acyclic-graph
partial-order
Дэвид Эппштейн
источник
источник
Ответы:
Эта проблема, похоже, очень похожа на ПОСЛЕДОВАТЕЛЬНОСТЬ МИНИМАЛЬНОЙ МАКСИМАЛЬНОЙ СТОИМОСТИ, проблема [SS7] в Garey & Johnson . Для остроумия:
Я не уверен , остается ли проблема NP-полной , когда фиксирована 0. G & J упоминания о том , что проблема остается NP-полной , если для все .c ( t ) ∈ { - 1 , 0 , 1 } t ∈ TK c(t)∈{−1,0,1} t∈T
источник
Ну, мой ответ - мой вопрос, из которого получается, что, если бы вы могли решить эту проблему в P, вы могли бы также решить еще одну открытую проблему: положительное топологическое упорядочение, возьмите 3
Редактировать: Эта проблема также оказалась NP-полной, так что ваша проблема уже NP-полная, если у вашей DAG есть только два уровня, т.е. если нет направленных путей с двумя ребрами.
источник
Если я правильно понимаю проблему, я думаю, что задача планирования одной машины с ограничением приоритета для минимизации взвешенной суммы времен завершения (1 | prec | \ sum wc) может быть сведена к проблеме, которая вас интересует. В задаче 1 | prec | \ sum wc у нас есть n заданий, каждое с неотрицательным весом и временем обработки, набором заданий, и мы хотим, чтобы линейное расширение заданий было таким, чтобы взвешенная сумма времен завершения заданий составляла сведено к минимуму. Проблема является NP-полной, хотя мы предполагаем, что время обработки каждой работы равно 1. Имеет ли это какой-то смысл?
источник
Что если мы всегда берем максимальный элемент (в частичном порядке) с наименьшим весом? После того, как мы исчерпали элементы, мы возвращаем их в обратном порядке в качестве вывода.
источник
Эта проблема напоминает мне много деревьев решений. Я хотел бы рассмотреть этот тип решения, который пытается всегда выбрать наиболее многообещающий путь, но, глядя на весь подграф:
Начиная с приемных узлов, продвигайтесь к источникам, по одному уровню за раз. В то время как вы делаете это, придавайте каждому краю вес. Этот вес должен представлять минимальную сумму, которую вам придется «заплатить», иначе вы «заработаете», пройдя подграф, начиная с узла, на который указывает край. Предположим, мы находимся на уровне i + 1 и продвигаемся до уровня i. Вот что я бы сделал, чтобы назначить вес ребру, указывающему на узел уровня i:
Затем создайте порядок следующим образом:
Идея состоит в том, чтобы обойти те подграфы, которые сначала дадут как можно больше выигрыша, чтобы потом иметь возможность нести стоимость подграфов с отрицательным весом.
источник