4551
правка
Ресинхронизация схемы: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 49: | Строка 49: | ||
Поскольку в ограничения входят только разностные неравенства с целочисленными константными термами, решение ослабленной линейной программы (без целочисленных ограничений) даст только целочисленные решения. И более того, можно показать, что эта задача является двойственной к задаче нахождения потока с минимальной стоимостью | Поскольку в ограничения входят только разностные неравенства с целочисленными константными термами, решение ослабленной линейной программы (без целочисленных ограничений) даст только целочисленные решения. И более того, можно показать, что эта задача является двойственной к задаче нахождения сетевого потока с минимальной стоимостью и, таким образом, имеет эффективное решение. | ||
'''Теорема 1. Целочисленная линейная программа для задачи ресинхронизации с минимальной площадью является двойственной к следующей задаче нахождения потока с минимальной стоимостью | '''Теорема 1. Целочисленная линейная программа для задачи ресинхронизации с минимальной площадью является двойственной к следующей задаче нахождения сетевого потока с минимальной стоимостью:''' | ||
'''Минимизировать <math>\sum_{(u, v) \in E} w[u, v] * f[u, v] + \sum_{D[u, v] > \phi} (W[u, v] - 1) * f[u, v]</math> так, чтобы выполнялись соотношения''' | '''Минимизировать <math>\sum_{(u, v) \in E} w[u, v] * f[u, v] + \sum_{D[u, v] > \phi} (W[u, v] - 1) * f[u, v]</math> так, чтобы выполнялись соотношения''' | ||
<math>in[v] + \sum_{(v, w) \in E \vee D[ | <math>in[v] + \sum_{(v, w) \in E \vee D[v, w] > \phi} f[v, w] = out[v] + \sum_{(u, v) \in E \; \; D[u, v] > \phi} f[u, v] \; \; \forall v \in V</math> | ||
<math>f[u, v] \ge 0 \; \; \forall (u, v) \in E \; \; D[u, v] > \phi</math> | <math>f[u, v] \ge 0 \; \; \forall (u, v) \in E \; \; D[u, v] > \phi</math> | ||
| Строка 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. Алгоритм будет присваивать веса при помощи покомпонентного сложения и затем сравнивать их посредством лексикографической сортировки. | ||