Минимальное остовное дерево с емкостью

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

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

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

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

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

функция CMST( c , C , r ): T = { , , ..., } при этом есть изменения: для каждого узла = ближайший узел в другом поддереве = - t_max = max ( ) k = i такой, что = t_max если ( cost (i) + cost (j) <= c ) T = T - T = T union return T${\displaystyle c_{1r}}$${\displaystyle c_{2r}}$${\displaystyle c_{nr}}$${\displaystyle a_{i}}$ ${\displaystyle a_{j}}$${\displaystyle t(a_{i})}$${\displaystyle g_{i}}$${\displaystyle c_{ij}}$ ${\displaystyle t(a_{i})}$${\displaystyle t(a_{i})}$${\displaystyle g_{k}}$ ${\displaystyle c_{kj}}$  

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

^[2]

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

Первоначальное решение находится с помощью рандомизированной версии Эсау-Вильямса. Рандомизация достигается путем выполнения равномерно случайного соединения из лучших вместо лучшего на каждом шаге.${\displaystyle p}$

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

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

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

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

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