Предположим, у нас есть DAG с ребрами, помеченными числами. Определите значение пути как произведение меток. Для каждой пары (источник, приемник) я хочу найти сумму значений всех путей от источника к приемнику. Вы можете сделать это за полиномиальное время с помощью динамического программирования, но есть еще некоторые варианты, которые можно сделать при декомпозиции задачи. В моем случае у меня есть один DAG, который нужно многократно оценивать с разными метками. Мой вопрос: для данного DAG, как мы можем предварительно вычислить хорошую стратегию для многократного вычисления этих значений для разных меток? Было бы неплохо, если бы существовал алгоритм, который находит оптимальный путь, например способ, минимизирующий количество умножений. Но, возможно, это слишком много, я был бы очень доволен алгоритмом, который просто дает хорошую декомпозицию.
Сумма продуктов пути в DAG
Ответы (1)
Пусть S — множество источников, V — множество вершин DAG, E — множество ребер, n = |V|, m = |S|, W — матрица размера n x n, в которой хранятся веса ребер, а C — множество ребер. матрица размера m x n такая, что 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), если предположить, что сложение и умножение занимают постоянное время. Это включает время топологической сортировки.
Доказательство правильности: мы доказываем по индукции, что после завершения k-й итерации самого внешнего цикла C[i,k] является суммой значений всех путей от i до k для каждого i в S.
Базовый случай: очевидно для k = 1 (поскольку у первого элемента нет предшественников)
Индукция: предположим C[i, j] вычисляется правильно для всех j ‹ k. Все пути из любого источника i в k должны проходить через предшественника k' источника k. Поскольку мы итерируем в топологическом порядке, k' должно быть меньше k, а согласно нашему предположению индукции C[i,k'] есть сумма значений пути от i до k'. При этом сумма значений путей из i в k, проходящих через конкретного предшественника k', равна сумме значений путей из i в k', т. е. C[i,k'], умноженной на W[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'[i,k], вы можете вычислить C[i,k], не глядя на структуру графа. Это потому, что кортежи неявно представляют структуру графа. С точки зрения сложности, это не лучше и не хуже.
