Емкостное минимальное связующее дерево

Емкостное минимальное связующее дерево — это связующее дерево с минимальной стоимостью графа , имеющее назначенный корневой узел. $r$ и удовлетворяет ограничению пропускной способности $c$ . Ограничение емкости гарантирует, что все поддеревья (максимальные подграфы, соединенные с корнем одним ребром), инцидентные корневому узлу $r$ иметь не более $c$ узлы. Если узлы дерева имеют веса, то ограничение пропускной способности можно интерпретировать следующим образом: сумма весов в любом поддереве не должна превышать $c$ . Ребра, соединяющие подграфы с корневым узлом, называются воротами . Найти оптимальное решение NP -трудно . ^[1]

Алгоритмы

Предположим, у нас есть график $G=(V,E)$ , $n=|G|$ с корнем $r\in G$ . Позволять $a_{i}$ быть всеми остальными узлами в $G$ . Позволять $c_{ij}$ быть стоимостью ребра между вершинами $a_{i}$ и $a_{j}$ которые образуют матрицу затрат $C={c_{ij}}$ .

Эвристика Исава-Вильямса

Эвристика Исау-Вильямса находит неоптимальные CMST, которые очень близки к точным решениям, но в среднем EW дает лучшие результаты, чем многие другие эвристики.

Изначально все узлы подключены к корню $r$ (звездный график), а стоимость сети равна $\displaystyle \sum _{i=0}^{n}c_{ri}$ ; каждое из этих ребер является воротами. На каждой итерации мы ищем ближайшего соседа $a_{j}$ для каждого узла в $G-{r}$ и оценим компромиссную функцию: $t(a_{i})=g_{i}-c_{ij}$ . Мы ищем величайшего $t(a_{i})$ среди положительных компромиссов и, если полученное поддерево не нарушает ограничения пропускной способности, удалить вентиль $g_{i}$ подключение $i$ -е поддерево в $a_{j}$ по краю $c_{ij}$ . Мы повторяем итерации до тех пор, пока не сможем внести дальнейшие улучшения в дерево.

Эвристика Исау-Вильямса для расчета неоптимального CMST:

function CMST(c,C,r):
    T = { $c_{1r}$ ,  $c_{2r}$ , ...,  $c_{nr}$ }
    while have changes:
        for each node  $a_{i}$ 
             $a_{j}$  = closest node in a different subtree
             $t(a_{i})$  =  $g_{i}$  -  $c_{ij}$ 
        t_max = max( $t(a_{i})$ )
        k = i such that  $t(a_{i})$  = t_max
        if ( cost(i) + cost(j) <= c)
            T = T -  $g_{k}$ 
            T = T union  $c_{kj}$ 
    return T

Легко видеть, что EW находит решение за полиномиальное время.

^[2]

Эвристика Ахуджи

Эвристика Ахуджи ^[3] использует локальный поиск в большом окружении с несколькими обменами на основе рандомизированного жадного начального решения.

Первоначальное решение

Первоначальное решение находится с использованием рандомизированной версии Исава-Вильямса. Рандомизация достигается за счет выполнения равномерно случайного соединения лучших $p$ вместо лучшего на каждом этапе.

Местный поиск по окрестностям

Позволять $T$ быть начальным решением с корнем $r$ . Окрестность состоит из любой комбинации одного узла или поддерева (общих поддеревьев, а не как во введении к этой статье), перемещающих один из них в другой компонент $T\setminus r$ так, что смещенная структура является следующим вытеснителем, последний вытеснитель вытесняет первый вытеснитель, ни один исходный компонент не имеет более одного вытеснителя и емкость ни в одном результирующем компоненте не превышается.

График улучшений

Граф улучшений — это инструмент для эффективного поиска в очень большой окрестности. Пути по графу улучшений соответствуют изменениям в решении, а стоимость пути — это изменение стоимости решения при применении изменения. Здесь граф улучшения представляет собой ориентированный мультиграф, построенный с использованием двух копий. $i',i''$ каждого узла $i\in V(T)$ и до 4 ребер от любого узла к любому узлу в другом компоненте $T\setminus r$ . Край $i',j''$ соответствует изменению удаления узла $i$ из исходного компонента и заменив поддерево с корнем в $j$ в целевом компоненте. Объединение узлов $i'$ и поддеревья $i''$ дает 4 возможных ребра. Край существует, если соответствующее изменение не приводит к превышению пропускной способности целевого компонента. Стоимость ребра — это разница в стоимости минимальных остовных деревьев вершин целевого компонента до и после смещения. Таким образом, соседям в локальном поиске соответствуют циклы графа улучшения, содержащие не более одного узла из каждого компонента.

Шаг локального поиска

На этапе локального поиска используется подход динамического программирования для поиска минимального цикла затрат на графе улучшения. Формируются пути по графу улучшений с возрастающей длиной и сохраняются только наиболее благоприятные с одинаковым началом и концом, а также задействованными компонентами. С этой целью для хранения путей используется хэш-таблица с кортежем этих трех свойств в качестве ключа. Поскольку в каждом отрицательном цикле существует такой узел, что все пути внутри этого цикла, содержащие этот узел, имеют отрицательную стоимость, вообще необходимо рассматривать только пути с отрицательной стоимостью. Поскольку сравнение наборов задействованных компонентов между путями является одной из наиболее распространенных операций в алгоритме, для скорости оно реализовано как сравнение массивов индикаторных битов, хранящихся в виде целых чисел. Однако это явно связано с большим количеством хеш-коллизий, которые могут быть следствием конкретного выбора хеш-функции и структуры таблицы, а также высокого коэффициента загрузки из-за ограничений пространства (документ 2003 года).

Производительность

На момент написания статьи (2003 г.) этот алгоритм был самым современным в стандартном тесте исследования операций. При выполнении доминировало построение (соответственно обновление) графа улучшения. Количество ребер в графе улучшения эмпирически масштабируется квадратично в зависимости от размера входного графа, и поскольку оно определяет, сколько раз необходимо выполнить сравнительно сложный этап поиска минимального остовного дерева, это наиболее важный фактор. Таким образом, можно заключить, что менее плотные входные графы значительно сокращают время работы, поскольку это уменьшает количество ребер в графе улучшения.

Приложения

Проблема CMST важна при проектировании сети: когда множество терминальных компьютеров к центральному концентратору необходимо подключить , звездообразная конфигурация обычно не является проектом с минимальной стоимостью. Поиск CMST, который объединяет терминалы в подсети, может снизить стоимость реализации сети.

Ссылки

^ Джоти, Раджа; Рагхавачари, Баладжи (2005), «Алгоритмы аппроксимации задачи минимального остовного дерева с емкостью и ее варианты в проектировании сетей», ACM Trans. Алгоритмы , 1 (2): 265–282, doi : 10.1145/1103963.1103967 , S2CID 8302085
^ Исав, ЛР; Уильямс, КЦ (1966). «О проектировании сети телеобработки: Часть II. Метод аппроксимации оптимальной сети». IBM Systems Journal . 5 (3): 142–147. дои : 10.1147/sj.53.0142 .
^ Ахуджа, РК; Орлин, Дж.Б.; Шарма, Д. (2003). «Комплексная очень крупномасштабная структура окрестностей для задачи минимального остовного дерева с емкостью». Письма об исследованиях операций . 31 (3): 185–194. дои : 10.1016/S0167-6377(02)00236-5 .

[1] Джоти, Раджа; Рагхавачари, Баладжи (2005), «Алгоритмы аппроксимации задачи минимального остовного дерева с емкостью и ее варианты в проектировании сетей», ACM Trans. Алгоритмы , 1 (2): 265–282, doi : 10.1145/1103963.1103967 , S2CID 8302085

[ew_alg-2] Исав, ЛР; Уильямс, КЦ (1966). «О проектировании сети телеобработки: Часть II. Метод аппроксимации оптимальной сети». IBM Systems Journal . 5 (3): 142–147. дои : 10.1147/sj.53.0142 .

[3] Ахуджа, РК; Орлин, Дж.Б.; Шарма, Д. (2003). «Комплексная очень крупномасштабная структура окрестностей для задачи минимального остовного дерева с емкостью». Письма об исследованиях операций . 31 (3): 185–194. дои : 10.1016/S0167-6377(02)00236-5 .

[1]

[2]

[3]