Лес Штейнера: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 29: | Строка 29: | ||
== Родственные работы == | == Родственные работы == | ||
Задача построения дерева Штейнера является NP-полной [ ] и APX-полной [4, 8]. Наилучшая известная нижняя граница достижимого коэффициента аппроксимации для решения этой задачи составляет 1,0074 [21]. Геманс и Уильямсон [11] обобщили результаты Агравала, Клейна и Рави для более широкого класса задач установления соединений, обозначив его как задачу построения леса с ограничениями. В случае построения леса Штейнера их алгоритм достигает того же коэффициента аппроксимации – (2 - 1/k). Алгоритмы Агравала, Клейна и Рави [2] и Геманса и Уильямсона основаны на классической формулировке задачи построения леса Штейнера с использованием неориентированных разрезов [3]. Известно, что разрыв целостности в этой релаксации составляет (2 - 1/k); таким образом, результаты в [2, 11] являются строгими. Джейн [15] представляет алгоритм 2-аппроксимации для задачи построения обобщенной сети Штейнера. | Задача построения дерева Штейнера является NP-полной [10] и APX-полной [4, 8]. Наилучшая известная нижняя граница достижимого коэффициента аппроксимации для решения этой задачи составляет 1,0074 [21]. Геманс и Уильямсон [11] обобщили результаты Агравала, Клейна и Рави для более широкого класса задач установления соединений, обозначив его как задачу построения леса с ограничениями. В случае построения леса Штейнера их алгоритм достигает того же коэффициента аппроксимации – (2 - 1/k). Алгоритмы Агравала, Клейна и Рави [2] и Геманса и Уильямсона основаны на классической формулировке задачи построения леса Штейнера с использованием неориентированных разрезов [3]. Известно, что разрыв целостности в этой релаксации составляет (2 - 1/k); таким образом, результаты в [2, 11] являются строгими. Джейн [15] представляет алгоритм 2-аппроксимации для задачи построения обобщенной сети Штейнера. | ||
Прямо-двойственный алгоритм | == Прямо-двойственный алгоритм == | ||
Основная идея алгоритма Агравала, Клейна и Рави (AKR) изложена ниже. Описание отличается от приведенного в [ ]; подробнее об этом – в | Основная идея алгоритма Агравала, Клейна и Рави (AKR) изложена ниже. Описание отличается от приведенного в [2]; подробнее об этом – в той же работе. | ||
Алгоритм основан на следующей формулировке задачи целочисленного программирования для построения леса Штейнера. Пусть I = (G, c, R) – экземпляр задачи построения леса Штейнера. Присвоим переменную-индикатор | |||
Алгоритм основан на следующей формулировке задачи целочисленного программирования для построения леса Штейнера. Пусть 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>. Это приводит к следующей формулировке задачи с неориентированными разрезами: | |||
(IP) (1) (2) | (IP) (1) (2) | ||
minimize V^ c(e)xe | minimize V^ c(e)xe | ||
| Строка 58: | Строка 60: | ||
Ребро e 2 E является плотным, если соответствующее ограничение (3) выполняется в виде равенства; путь является плотным, если все составляющего его ребра являются плотными. Пусть Hz – подграф G, порожденный плотными ребрами для двойственного значения yT. Связные компоненты Hz порождают разбиение Cz на множестве вершин V. Пусть Sz – множество всех разрезов Штейнера, содержащихся в Cz, т.е. Sz = Cz \ S. Алгоритм AKR равномерно увеличивает двойственные значения yS для всех множеств S 2 Sz во все моменты времени x > 0. Заметим, что yz является допустимым для двойственной задачи. Алгоритм поддерживает инвариант: Fz в любой момент времени является подграфом Hz. Рассмотрим событие, при котором путь P между двумя деревьями T1 и T2 в Fz становится плотным. После этого недостающие ребра P добавляются к Fz и процесс продолжается. В конечном итоге все деревья Fz становятся неактивными, в результате чего процесс завершается. | Ребро e 2 E является плотным, если соответствующее ограничение (3) выполняется в виде равенства; путь является плотным, если все составляющего его ребра являются плотными. Пусть Hz – подграф G, порожденный плотными ребрами для двойственного значения yT. Связные компоненты Hz порождают разбиение Cz на множестве вершин V. Пусть Sz – множество всех разрезов Штейнера, содержащихся в Cz, т.е. Sz = Cz \ S. Алгоритм AKR равномерно увеличивает двойственные значения yS для всех множеств S 2 Sz во все моменты времени x > 0. Заметим, что yz является допустимым для двойственной задачи. Алгоритм поддерживает инвариант: Fz в любой момент времени является подграфом Hz. Рассмотрим событие, при котором путь P между двумя деревьями T1 и T2 в Fz становится плотным. После этого недостающие ребра P добавляются к Fz и процесс продолжается. В конечном итоге все деревья Fz становятся неактивными, в результате чего процесс завершается. | ||
== Применение == | == Применение == | ||