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

Алгоритм AKR основан на ''прямо-двойственной'' схеме (см., например, [22]). Он строит и допустимое прямое решение для (IP), и допустимое двойственное решение для (D). Алгоритм начинает работу с недопустимого прямого решения, снижая степень его недопустимости по мере продвижения. В то же время он создает допустимый набор двойственных подмножеств с большой общей суммой, вводя двойственные переменные для разрезов Штейнера.

Можно рассмотреть выполнение алгоритма 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>. В то же время он увеличивает двойственные значения разрезов Штейнера, соответствующие активным деревьям. Если два активных дерева сталкиваются, они сливаются вместе. Процесс заканчивается, когда все деревья оказываются неактивными и, следовательно, не остается несвязанных пар полюсов. Взаимодействие между прямым (ростом деревьев) и обратным (увеличением двойственных значений) процессами представляет собой довольно тонкое явление.

Ребро <math>e \in E \;</math> является ''плотным'', если соответствующее ограничение (3) выполняется в виде равенства; путь является плотным, если все составляющего его ребра являются плотными. Пусть <math>H^{ \tau} \;</math> – подграф G, порожденный плотными ребрами для двойственного значения <math>y^{ \tau} \;</math>. Связные компоненты <math>H^{ \tau} \;</math> порождают разбиение <math>C^{ \tau} \;</math> на множестве вершин V. Пусть <math>S^{ \tau} \;</math> – множество всех разрезов Штейнера, содержащихся в <math>C^{ \tau} \;</math>, т.е. <math>S^{ \tau} = C^{ \tau} \cap S \;</math>. Алгоритм AKR равномерно увеличивает двойственные значения <math>y_S \;</math> для всех множеств <math>S \in S^{ \tau} \;</math> во все моменты времени <math>\tau \ge > 0 \;</math>. Заметим, что <math>y^{ \tau} \;</math> является допустимым для двойственной задачи. Алгоритм поддерживает инвариант: <math>F^{ \tau} \;</math> в любой момент времени является подграфом <math>H^{ \tau} \;</math>. Рассмотрим событие, при котором путь P между двумя деревьями <math>T_1 \;</math> и <math>T_2 \;</math> в <math>F^{ \tau} \;</math> становится плотным. После этого недостающие ребра P добавляются к <math>F^{ \tau} \;</math> и процесс продолжается. В конечном итоге все деревья <math>F^{ \tau} \;</math> становятся неактивными, в результате чего процесс завершается.