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

На базе этой теоремы можно показать, что граф сети представляет собой плотный граф, к которому необходимо добавить новое ребро (u, v) для любой пары вершин u, v, такой, что D[u; v] > ф.

В системе могут быть избыточные ограничения. Например, если W[u; w] = W[u; v] + w[v; w] и D[u; v] > ф, то ограничение W[u; w] + r[w] — r[u] > 1 является избыточным, поскольку уже имеются W[u; v] + r[v] — r[u] > 1 и w[v; w] + r[w] — r[v] > 0. Однако проверить все ограничения на наличие избыточных и устранить их может быть непросто.

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

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