Положительный топологический порядок

45

Предположим, у меня есть ориентированный ациклический граф с весами действительных чисел в его вершинах. Я хочу найти топологический порядок DAG, в котором для каждого префикса топологического порядка сумма весов неотрицательна. Или, если вы предпочитаете теоретико-порядковую терминологию, у меня есть взвешенный частичный порядок, и я хочу линейное расширение, чтобы каждый префикс имел неотрицательный вес. Что известно об этой проблеме? Это NP-полный или разрешимый за полиномиальное время?

Дэвид Эппштейн
источник
4
Попробуйте жадный алгоритм на этом графике: 1 -> 2 -> 3, 1 -> 4 -> 5, веса вершин 1: +2, 2: -2, 3: +3, 4: -1 5: -2. Жадный алгоритм должен начинаться с v1, затем выбирать v4 и застрять. Правильный порядок v1, v2, v3, v4, v5.
Робин Котари
2
«Некоторые проблемы расстояния Фреше, на которые Джефф и другие смотрели» - отличная абстракция! Для пользы других, вот одна версия: Предположим, вам дан гранично-взвешенный плоский граф G и две вершины s и tn на внешней грани. Вы хотите преобразовать один граничный путь из s в t в другой с помощью последовательности элементарных движений. Каждое движение заменяет текущий путь с его симметричной разностью некоторой границей грани. Как быстро мы можем найти последовательность mve, которая минимизирует максимальную длину развивающегося пути?
Джефф
3
Цуёси, извините за это, я попытался добавить новую строку во время комментирования, и это вызвало отключение моего комментария. Итак, идея в том, что у вас на запястье плотно завязана веревка, и вы хотите знать, сможете ли вы ее свернуть. Ваше запястье представлено в виде многоугольной сетки, ячейки которой являются элементами частичного порядка (ближе к строке раньше, ближе к выкл позже в заказе). Вес клетки - это разница в длине между ее внутренней и внешней границами.
Дэвид Эппштейн
1
@ Дэвид: Спасибо за объяснение. На этот раз я могу понять, как это связано с текущим вопросом, и это интересно!
Цуёси Ито
3
Не очень полезное, но забавное наблюдение: эта проблема эквивалентна проблеме секвенирования на одной машине с крайними сроками и ограничениями приоритета, когда время обработки каждого задания может быть отрицательным . При неотрицательном времени обработки эта проблема находится в P (Lawler and Mooer 1969 jstor.org/stable/2628367 ), и если решение существует, то существует решение, которое не зависит от времени обработки. Это явно ломается, если некоторые задания имеют отрицательное время обработки.
Цуёси Ито

Ответы:

18

Эта проблема, похоже, очень похожа на ПОСЛЕДОВАТЕЛЬНОСТЬ МИНИМАЛЬНОЙ МАКСИМАЛЬНОЙ СТОИМОСТИ, проблема [SS7] в Garey & Johnson . Для остроумия:

INSTANCE: Установите задач, частичный порядок на , «стоимость» для каждого (если , это можно рассматривать как «прибыль») и константа .T c ( t ) Z t T c ( t ) < 0 K ZTTc(t)ZtTc(t)<0KZ

ВОПРОС: Существует ли однопроцессорный график для который подчиняется ограничениям приоритета и который обладает свойством, что для каждой задачи сумма затрат для всех задач с не более ?Т т Т т ' сг ( т ' ) & le ; сг ( т ) КσTtTtσ(t)σ(t)K

Я не уверен , остается ли проблема NP-полной , когда фиксирована 0. G & J упоминания о том , что проблема остается NP-полной , если для все .c ( t ) { - 1 , 0 , 1 } t TKc(t){1,0,1}tT

mhum
источник
7
Это выглядит хорошо. Тогда я думаю, что можно взять без потери общности, в противном случае можно добавить неограниченное задание с помощью -value (или заданий -value ). C - K K C - 1K=0cKKc1
Daveagp
@mhum: я работаю над техническим отчетом о связанных результатах и ​​хотел бы процитировать вас. Ты бы дал мне свое настоящее имя? Если вы хотите, вы можете
написать
9

Ну, мой ответ - мой вопрос, из которого получается, что, если бы вы могли решить эту проблему в P, вы могли бы также решить еще одну открытую проблему: положительное топологическое упорядочение, возьмите 3

Редактировать: Эта проблема также оказалась NP-полной, так что ваша проблема уже NP-полная, если у вашей DAG есть только два уровня, т.е. если нет направленных путей с двумя ребрами.

domotorp
источник
3

Если я правильно понимаю проблему, я думаю, что задача планирования одной машины с ограничением приоритета для минимизации взвешенной суммы времен завершения (1 | prec | \ sum wc) может быть сведена к проблеме, которая вас интересует. В задаче 1 | prec | \ sum wc у нас есть n заданий, каждое с неотрицательным весом и временем обработки, набором заданий, и мы хотим, чтобы линейное расширение заданий было таким, чтобы взвешенная сумма времен завершения заданий составляла сведено к минимуму. Проблема является NP-полной, хотя мы предполагаем, что время обработки каждой работы равно 1. Имеет ли это какой-то смысл?

monaldo
источник
Это определенно интересная возможность. Но как сделать сокращение таким образом, чтобы критерий оптимизации (минимизировать сумму времени завершения) трансформировался в ограничения (неотрицательные префиксы)?
Дэвид Эппштейн
Я не знаю этого результата NP-полноты задачи планирования, но я думаю, что это относится к проблеме решения вопроса о том, существует ли линейное расширение, такое, что взвешенная сумма времени выполнения задания не превышает K, поэтому я не думаю, что здесь важно различие между критерием оптимизации и ограничением. Однако я не понял, как представить ограничение на взвешенную сумму времени завершения в текущей задаче.
Цуёси Ито
Я думаю, что сокращение не так просто, как я думал в начале. Я больше не уверен в своем ответе.
Мональдо
Я только что понял ошибку в моем предыдущем комментарии. Когда я публиковал его, я думал, что представить ограничение на невзвешенную сумму было легко (отсюда акцент на взвешенном ), но это было совершенно неправильно.
Цуёси Ито
2

Что если мы всегда берем максимальный элемент (в частичном порядке) с наименьшим весом? После того, как мы исчерпали элементы, мы возвращаем их в обратном порядке в качестве вывода.

Даниэль Мартин
источник
Задача инвариантна при преобразовании обращения частичного упорядочения и отмены всех весов. Так что я не понимаю, как это может отличаться от алгоритма жадности, который Робин К дал в качестве примера в комментариях.
Дэвид Эппштейн
Но этот метод работает для его примера: сначала будет выбрана вершина 5, затем вершина 4, затем 3, 2 и, наконец, 1. Таким образом, окончательный порядок будет 1, 2, 3, 4, 5. На самом деле, я надеваю Не думаю, что трудно доказать, что этот метод работает. Предположим, у вас есть решение, в котором максимальный элемент (сток) не имеет минимального веса в последней позиции. Затем вы можете найти другое решение, которое обладает этим свойством, просто изменив положение такого элемента на последний и сохранив остальное как есть. Продолжайте по индукции на том, что осталось, и вы получите формальное доказательство.
Даниэль Мартин
Да ... это не работает ... 1 -> 2 -> 3, 1 -> 4 с весами 4, -7, 6, 3 соответственно.
Даниэль Мартин
1

Эта проблема напоминает мне много деревьев решений. Я хотел бы рассмотреть этот тип решения, который пытается всегда выбрать наиболее многообещающий путь, но, глядя на весь подграф:

Начиная с приемных узлов, продвигайтесь к источникам, по одному уровню за раз. В то время как вы делаете это, придавайте каждому краю вес. Этот вес должен представлять минимальную сумму, которую вам придется «заплатить», иначе вы «заработаете», пройдя подграф, начиная с узла, на который указывает край. Предположим, мы находимся на уровне i + 1 и продвигаемся до уровня i. Вот что я бы сделал, чтобы назначить вес ребру, указывающему на узел уровня i:

  1. edge_weight = указывающий_узел_вес.
  2. Найти ребро, начиная с «указывающего узла» с максимальным весом. Пусть этот вес будет следующим.
  3. edge_weight + = next_edge_weight

Затем создайте порядок следующим образом:

  1. Пусть S будет границей поиска, то есть набором узлов для выбора из следующего.
  2. Выберите узел так, чтобы (node_weight + maximum_edge_weight) был максимальным.
  3. Удалите узел из графа и S. Добавьте «детей» узла в S.
  4. Если график не пустой, перейдите к шагу 1.
  5. Halt.

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

chazisop
источник