Ресинхронизация схемы: различия между версиями

Для построения потока в сети с минимальной стоимостью необходимо вначале вычислить обе матрицы, W и D. Поскольку W[u, v] – кратчайший путь из u в v относительно w, вычисление W можно выполнить при помощи алгоритма нахождения кратчайших путей между всеми парами – например, алгоритма Флойда-Уоршелла [1]. Далее, если упорядоченная пара (w[x, y], —d[x]) используется в качестве веса ребра для каждой пары <math>(x, y) \in E \;</math>, [[алгоритм нахождения кратчайших путей между всеми парами]] можно также использовать для вычисления W и D. Алгоритм будет присваивать веса при помощи покомпонентного сложения и затем сравнивать их посредством лексикографической сортировки.

Первый алгоритм Лейзерсона и Сакса [3] для ресинхронизации с минимальной длительностью был также основан на использовании матриц W и D. Этот алгоритм основывался на том, что ограничения в целочисленной линейной программе для ресинхронизации с минимальной длительности можно эффективно проверять при помощи алгоритма нахождения кратчайших путей Беллмана-Форда [1], поскольку представляют собой просто разностные неравенства. Это позволяет выполнять проверку применимости для любой заданной длительности такта '. После этого бинарным поиском по диапазону возможных длительностей можно найти оптимальную длительность такта. Проверку применимости можно выполнить за время O( j V j3); таким образом, общее время выполнения такого алгоритма составит O(j Vj3 log j Vj).

В своем втором алгоритме авторы избавились от построения матриц W и D, однако по-прежнему использовали проверку применимости длительности такта во время бинарного поиска. Однако проверка применимости в этот раз выполняется при помощи инкрементной ресинхронизации и работает следующим образом. Начиная с r = 0 алгоритм вычисляет время прибытия в каждую вершину при помощи вычисления самых длинных путей в ориентированном ациклическом графе. Для каждой вершины v, время прибытия в которую превышает заданную длительность ', значение r[v] увеличивается на единицу. Процесс вычисления времени прибытия и увеличения r повторяется |V| — 1 раз. Если после этого какое-либо время прибытия остается большим, чем ', то длительность является неприменимой. Проверку применимости можно выполнить за время O(jVjjEj), а полное время выполнения ресинхронизации с минимальной длительностью составляет O(j VjjEj log j Vj).