Лес Штейнера: различия между версиями

Алгоритм основан на следующей формулировке задачи целочисленного программирования для построения леса Штейнера. Пусть I = (G, c, R) – экземпляр задачи построения леса Штейнера. Присвоим переменную-индикатор <math>x_e \in \{ 0, 1 \} \;</math> каждому ребру <math>e \in E \;</math>. Значение <math>x_e \;</math> равно 1, если e является частью леса F, и 0 в противном случае. Подмножество <math>S \subseteq V \;</math> вершин называется [[разрез Штейнера|разрезом Штейнера]], если существует по меньшей мере одна пара полюсов <math>(s_i, t_i) \in R \;</math>, такая, что <math>| \{ s_i, t_i \} \cap S | = 1 \;</math>; говорят, что S ''разделяет'' пару полюсов <math>(s_i, t_i) \;</math>. Пусть S – множество всех разрезов Штейнера. Для подмножества <math>S \subseteq V \;</math> определим <math>\delta (S) \;</math> как множество всех ребер в E, имеющих ровно одну конечную точку в S. Пусть дан разрез Штейнера <math>S \in S \;</math>; любое допустимое решение F для экземпляра I должно содержать по меньшей мере одно ребро, пересекающее разрез S, т.е. <math>\sum_{e \in \delta (S)} x_e \ge 1 \;</math>. Это приводит к следующей формулировке задачи с неориентированными разрезами:

(1) относительно <math>\sum_{e \in \delta (S)} x_e \ge 1 \; \forall S \in S</math>

Двойственная задача для релаксации линейного программирования (IP) включает переменную <math>y_S \;</math> для каждого разреза Штейнера <math>S \in S \;</math>. Существует ограничение: для каждого ребра <math>e \in E \;</math> полная двойственная задача, присвоенная множествам <math>S \in S \;</math>, содержащим только одну конечную точку e, имеет стоимость не более c(e):

(D) максимизировать <math>\sum_{S \in S} y_S</math>

(3) относительно <math>\sum_{S \in S: \; e \in \delta (S)} y_S \le c(e) \; \forall e \in E</math>

(4) <math>y_S \ge 0 \; \forall S \in S</math>

Можно рассмотреть выполнение алгоритма AKR как процесса, зависящего от времени. Пусть <math>x^{ \tau} \;</math> и <math>y^{ \tau} \;</math> обозначают вектор инцидентности прямой задачи и допустимое решение двойственной задачи в момент времени <math>\tau \;</math>, соответственно. Вначале положим <math>x^0_e = 0 \;</math> для всех ребер <math>e \in E \;</math> и <math>y^0_S = 0 \;</math> для всех подмножеств <math>S \in S \;</math>. Пусть <math>F^{ \tau} \;</math> обозначает лес, соответствующий множеству ребер с <math>x^{ \tau} = 1 \;</math>. Дерево T в лесу <math>F^{ \tau} \;</math> называется ''активным'' в момент времени <math>\tau \;</math>, если оно содержит полюс, отделенный от своей пары; в противном случае оно называется ''неактивным''. Интуитивно понятно, что алгоритм AKR растит активные деревья в <math>F^{ \tau} \;</math>. В то же время он увеличивает двойственные значения разрезов Штейнера, соответствующие активным деревьям. Если два активных дерева сталкиваются, они сливаются вместе. Процесс заканчивается, когда все деревья оказываются неактивными и, следовательно, не остается несвязанных пар полюсов. Взаимодействие между прямым (ростом деревьев) и обратным (увеличением двойственных значений) процессами представляет собой довольно тонкое явление.