Сумма пустых продуктов в DAG

Question

Предположим, у нас есть DAG с краями, помеченными цифрами. Определите значение пути как произведение меток. Для каждого (источника, приемника) -пары я хочу найти сумму значений всех путей от источника до потокового. Вы можете сделать это в полиномиальное время с динамическим программированием, но есть еще некоторые варианты, которые можно сделать в том, как вы разложите проблему. В моем случае у меня есть одна группа DAG, которую нужно многократно оценивать с помощью разных меток. Мой вопрос: для данного DAG, как мы можем предварительно вычислить хорошую стратегию для повторного вычисления этих значений для разных меток? Было бы неплохо, если бы был алгоритм, который находит оптимальный способ, например способ, который минимизирует количество умножений. Но, возможно, это слишком много, чтобы спросить, я был бы очень доволен алгоритмом, который просто дает хорошее разложение.

Answer 1

Пусть S - множество источников, V - множество вершин DAG, E - множество ребер, n = | V |, m = | S |, W - матрица nxn, в которой хранятся веса ребер , а C - матрица mxn, такая, что C [i, j] в конце алгоритма содержит сумму значений всех путей от i до j. Чтобы упростить объяснение и доказательство правильности алгоритма, я предполагаю, что вершины графа от 1 до n являются топологически упорядоченными, в которых узлами от 1 до m являются источники. Это добавляет O (| E | + | V |) к времени работы алгоритма:

Вот псевдокод алгоритма:

1: set C[i,j] to 1 if i=j and i is a source node, and to 0 otherwise. 
2: sort the DAG topologically 
3: for k=1 to n (vertex traversal in the topological order) 
4: foreach predecessor k' of vertex k 
5:  foreach i in S 
6:  C[i,k] += C[i,k']*W[k',k] 

Есть в общей сложности O (| E | + | V |) для двух внешних петель. Поэтому время работы алгоритма O ((| V | + | E |) .m), предполагая, что сложение и умножение принимают постоянное время. Это включает время для топологической сортировки.

Доказательство корректности: доказывается по индукции, что после завершения к-й итерации самого внешнего контура, С [I, K] является суммой значений всех путей от I до к для каждого I в S.
Базовый вариант: очевидно, при к = 1 (поскольку первый элемент не имеет каких-либо предшественников)
Induction: Пусть C [I, J] правильно вычисляется для всех J < к. Все пути от любого источника i до k должны проходить через предшественник k 'of k. Поскольку мы итерируем в топологическом порядке, k 'должно быть меньше k, и согласно нашему предположению индукции C [i, k'] представляет собой сумму значений пути от i до k '. Более того, сумма значений путей от i до k, проходящих через определенный предшественник k ', равна сумме значений путей от i до k', т. Е. C [i, k '], умноженной на W [k », K]. Поэтому сумма значений всех путей от i до k равна сумме C [i, k '] ​​* W [k', k] по всем предшественникам k 'поля k.

Такая же структура графика, другая матрица W: Если нам нужно вычислить матрицу C для разных графов, имеющих одну и ту же структуру, но различную W, мы можем сделать следующее: Пусть C '- матрица, элементы которой являются списком 3-кортежей. Заменить строку 6 выше с

C'[i,k].append((i,k',k)) 

, а затем переборе вершин в топологическом порядке и переборе кортежей в C '[я, к], можно вычислить C [I, K], не смотря на структура графика. Это связано с тем, что кортежи неявно представляют структуру графа. С точки зрения сложности это не лучше или хуже.