4488
правок
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) мНет описания правки |
||
Строка 10: | Строка 10: | ||
== Объединенный алгоритм маршрутизации, распределения каналов и планирования линий связи == | == Объединенный алгоритм маршрутизации, распределения каналов и планирования линий связи == | ||
Даже подзадача планирования ребер в отсутствие интерференции при наличии потоков по ребрам является NP-полной [5]. Был разработан алгоритм | Даже подзадача планирования ребер в отсутствие интерференции при наличии потоков по ребрам является NP-полной [5]. Был разработан аппроксимационный алгоритм под названием RCL для решения объединенной задачи маршрутизации, распределения каналов и планирования линий связи. Алгоритм выполняет следующие операции в приведенном порядке: | ||
1. '''Решение LP-задачи'''. Вначале необходимо найти оптимальное решение задачи LP-релаксации (релаксации линейного программирования). Результатом является поток управления в управляющем графе, а также не обязательно допустимое распределение каналов для радиостанций в вершинах. В частности, вершине может быть назначено больше каналов, чем у нее имеется радиостанций. Однако это распределение каналов является «оптимальным» с той точки зрения, что оно гарантирует минимальный уровень интерференции для каждого канала. Этот этап также позволяет получить нижнюю границу значения <math>\lambda \;</math>, используемую в формулировке гарантии эффективности в наихудшем случае для алгоритма в целом. | 1. '''Решение LP-задачи'''. Вначале необходимо найти оптимальное решение задачи LP-релаксации (релаксации линейного программирования). Результатом является поток управления в управляющем графе, а также не обязательно допустимое распределение каналов для радиостанций в вершинах. В частности, вершине может быть назначено больше каналов, чем у нее имеется радиостанций. Однако это распределение каналов является «оптимальным» с той точки зрения, что оно гарантирует минимальный уровень интерференции для каждого канала. Этот этап также позволяет получить нижнюю границу значения <math>\lambda \;</math>, используемую в формулировке гарантии эффективности в наихудшем случае для алгоритма в целом. |
правок