Точный алгоритм для задачи маркировки ребер в DAG

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

Задача: Нам дан ориентированный ациклический граф . Без ограничения общности предположим, что имеет ровно одну исходную вершину и ровно одну стоковую вершину ; Пусть обозначает множество всех направленных путей от до в . Мы также дали множество вершин . Задача состоит в том, чтобы назначить неотрицательные целочисленные веса ребрам , поэтому любые два пути в имеют одинаковый вес, если и только если они содержат одинаковое подмножество вершин в $G=(V,E)$ $G$ $s$ $t$ $P$ $s$ $t$ $G$ $R \subseteq V$ $G$ $P$ . (Вес пути - это сумма весов его ребер.) Диапазон весов путей в должен быть как можно меньше. $R$ $P$

В настоящее время мой подход не кажется эффективным; Я просто ищу ссылки на литературу или хорошие идеи. Все остальное также ценится.

Изменить: Есть ли доказательства твердости для этой проблемы? Всегда ли существует компактная нумерация?

ds.algorithms reference-request co.combinatorics graph-algorithms directed-acyclic-graph user5153
источник

уточните, пожалуйста, «Диапазон весов путей в P должен быть оптимальным». Веса только целые числа? Разрешены ли нам отрицательные веса? Оптимальный означает «как можно меньший диапазон» или это что-то еще?

Артем Казнатчеев

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

user5153

Простая стратегия для нахождения правильного решения состояла бы в том, чтобы назначить различную степень два каждой вершине v в R, использовать это число в качестве веса всех входящих ребер для v и присвоить нулевой вес всем оставшимся ребрам. Очевидно, что это не может быть оптимальным, но, по крайней мере, дает верхнюю границу необходимого диапазона. Является ли когда-либо улучшением то, что разные ребра через одну и ту же вершину в R имеют разные веса друг от друга, или вы можете упростить задачу, заставив веса идти с вершинами, а не с ребрами?

Дэвид Эппштейн

O (2^{| R |})

$O(2^{|R|})$

G = (V, E)

$G = (V, E)$

V = [n] \cup {s, t}

$V = [n] \cup \{s, t\}$

E = {(i, j) : i < j} \cup {(s, 1), (n, t), (s, t)}

$E = \{(i, j): i<j\} \cup \{(s, 1), (n, t), (s, t)\}$

R = [n]

$R = [n]$

2^{n}

$2^n$

R

$R$

2^{n} - 1

$2^n -1$

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

Сашо Николов

Я не слышал об этой проблеме именно в литературе [возможно, кто-то другой], однако, как «соседняя проблема», мне кажется, что минимальное связующее дерево будет иметь полезные свойства для решения вашей проблемы. например, возможно, создание двух минимальных остовных деревьев, начиная с исходной вершины и вершины синхронизации, и распространение их наружу, пока они не коснутся и т. д., может решить проблему или дать точный ответ. прежде чем кто-нибудь скажет мне об этом, пожалуйста, поймите, что я немного расширяю идею MST, которая будет сгенерирована, начиная с заданной вершины [обычно она начинается с самого короткого ребра во всем графе]. если это не работает, мне было бы любопытно по этой причине.

ВЗН
источник

Извините, но я не вижу актуальности этого ответа на этот вопрос.

Дэвид Эппштейн

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

ВЗН

Ему нужно назначить веса для ребер. Как вычисление MST поможет этому?

Николас Манкузо

хорошо, когда вы его прочитали, и, когда никто другой не предложил ответ, казалось, что проблему можно преобразовать в две части: (1) назначить веса на основе критериев / ограничений, (2) найти кратчайшие пути на основе этих весов. кажется MST может быть полезным на (2). а может и нет! (например, может быть 1/2 тесно связаны)

vzn

Нет. Минимальные связующие деревья только для неориентированных графов; входной граф направлен. Более того, минимальные остовные деревья поверхностно связаны только с кратчайшими путями.

Джефф

Точный алгоритм для задачи маркировки ребер в DAG

Ответы: