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

Для построения сетевого потока с минимальной стоимостью необходимо вначале вычислить обе матрицы, 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], поскольку представляют собой просто разностные неравенства. Это позволяет выполнять проверку применимости для любой заданной длительности такта <math>\varphi \;</math>. После этого бинарным поиском по диапазону возможных длительностей можно найти оптимальную длительность такта. Проверку применимости можно выполнить за время <math>O(|V|^3) \;</math>; таким образом, общее время выполнения такого алгоритма составит <math>O(|V|^3 \; log \; |V|)</math>.

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