Аноним

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

Материал из WEGA
м
Строка 67: Строка 67:




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


== Применение ==
== Применение ==
4551

правка