Приближенные методы решения задачи Штейнера на ориентированных графах тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Ейбоженко, Дмитрий Анатольевич

• Ейбоженко, Дмитрий Анатольевич
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Ейбоженко, Дмитрий Анатольевич

Содержание

1. Введение

1.1. Цели и задачи

1.2. Постановки задачи Штейнера

1.3. Применение

1.3.1. УЬ81-проектироваиие

1.3.2. Восстановление филогенетических деревьев

1.3.3. Интерактивная телекоммуникация

1.4. Описание работы по главам

1.5. Основные определения и обозначения

2. Состояние дел

2.1. Точные алгоритмы

2.1.1. Алгоритм динамического программирования

2.1.2. Сведение к задаче линейного программирования

2.2. Приближенные алгоритмы

2.2.1. Алгоритм Такахаши-Мацуямы

2.2.2. Приближенные алгоритмы основанные на линейном программировании

2.2.3. Жадные алгоритмы

3. Алгоритм к-кластерной оптимизации

3.1. Определение кластеров в графе

3.1.1. Построение опорного дерева

3.1.2. Разбиение на кластеры

3.2. Построение деревьев Штейнера на кластерах

3.3. Улучшение деревьев Штейнера на кластерах

3.4. Нахождение промежуточного полного дерева Штейнера

3.5. Улучшение промежуточного дерева Штейнера

3.6. Теорема о вычислительной сложности

4. Приближенный метод 5* для задачи Штейнера на евклидовых графах

4.1. Алгоритм А* поиска кратчайшего пути

4.2. Задача Штейнера на концентрических окружностях

4.3. Алгоритм 5* на евклидовых графах

4.3.1. Построение приближенного решения

4.3.2. Построение множества терминальных подмножеств. Наивный метод

4.3.3. Построение множества терминальных подмножеств. Метод «концентрических окружностей»

4.3.4. Построение множества терминальных подмножеств. Обобщенный метод

4.3.5. Теоретические результаты

5. Вычислительные оптимизации

5.1. Общий обзор

5.2. Особенности реализации однопоточных алгоритмов

5.2.1. Алгоритм динамического программирования

5.2.2. /с-кластерный приближенный алгоритм

5.2.3. Приближенный метод Б* на евклидовых графах

5.3. Параллелизация алгоритмов

5.3.1. Параллелизация точного алгоритма решения

5.3.2. Параллелизация алгоритма ^-кластерной оптимизации

5.3.3. Параллелизация алгоритма аппроксимации S*

6. Вычислительные результаты

6.1. Сравнение эффективности структур, реализующих приоритетную очередь

6.2. Сравнение эффективности ^-кластерного метода с другими известными

6.3. Сравнение эффективности метода S* с другими известными

6.4. Сравнение быстродействия однопоточных и параллельных реализаций методов

6.4.1. Метод динамического программирования

6.5. Метод к-кластерной оптимизации

6.6. Метод 5*

7. Результаты и выводы

Введение диссертации (часть автореферата) на тему «Приближенные методы решения задачи Штейнера на ориентированных графах»

1. Введение

Задача Штейнера, или задача о минимальном дереве Штейнера, названная в честь швейцарского математика Якова Штейнера, является задачей комбинаторной оптимизации. Она может быть сформулирована в различных постановках, однако в любой задаче Штейнера, независимо от конкретной формулировки: на евклидовой плоскости или в более общей, графовой, форме, требуется найти кратчайшую сеть, связывающую заданное множество вершин, имея возможность использовать промежуточные вершины.

1.1. Цели и задачи

Основными целями данной работы является:

а) Определить степень востребованности и применимости данной конкретной постановки задачи Штейнера, и актуальности ее исследования.

б) Исследовать и проанализировать имеющиеся способы приближенного решения задачи Штейнера на ориентированных графах, выделить основные направления исследования и перспективы дальнейшего исследования в различных направлениях.

в) Разработать методы для приближенного решения задачи Штейнера на ориентированных графах в общей постановке, и в различных специальных случаях, применимых на практике.

г) Для разработанных методов в случае возможности найти точную теоретически обоснованную оценку трудоемкости и коэф-

фициента аппроксимации.

д) Экспериментально сравнить разработанные методы с наиболее известными и часто применяемыми приближенными методами.

е) Определить возможность параллелизации представленных методов и если она есть, разработать параллельные реализации алгоритмов.

ж) Провести экспериментальные сравнения однопоточных и параллельных версий представленных алгоритмов.

з) Сделать выводы о возможности и целесообразности применения данных методов на практике, а также возможных дальнейших улучшений этих методов.

1.2. Постановки задачи Штейнера

На данный момент распространены несколько постановок задачи

Штейнера:

а) Евклидова (геометрическая). Имея набор точек на евклидовой плоскости, требуется найти кратчайшую сеть, которая соединяет все точки. Сеть может иметь дополнительные точки пересечения, называемые точками Штейнера.

б) Прямоугольная. Частный случай евклидовой задачи Штейнера. В ней для определения расстояний между точками используется прямоугольная метрика Ь\ : р((х\, у\), (^2, У2)) = (1^1 — + \у\ — 2/2!)■ Ее еЩе называют манхеттенской.

в) В сетях (на неориентированных графах). Дан граф G(M, N) с дугами положительной длины (можно говорить, что длина есть функция от дуги d : N —>■ К+), а. также подмножество ТСМ терминалов. Необходимо найти сеть наименьшей длины в графе, соединяющую все терминалы из Т.

г) На ориентированных графах. Пусть G(M,N) — ориентированный граф с заданной на дугах функцией d : N —>• R+. В М выделена начальная вершина Ъ и множество терминальных вершин Е. Требуется найти дерево минимальной длины с корнем в заданной вершине Ь, содержащее пути от b до любого терминала из Е.

Более подробно все определения и обозначения, использующиеся в работе, будут даны в этой главе ниже.

1.3. Применение

Различные вариации задачи Штейнера широко используются на практике, в том числе в схемотехнике, биологии, компьютерных и телекоммуникационных сетях. Опишем подробнее основные области применения задачи.

1.3.1. VLSI-проектирование

Аббревиатура VLSI расшифровывается как Very Large Scale Integration. Это процесс создания сверхбольших интегральных схем (микросхем) путем комбинирования миллионов (а сейчас уже и миллиардов) тран-

зисторов. Всем известные центральные процессоры (CPU) и графические платы (GPU) являются примерами VLSI-устройств.

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

— проектирование логической схемы, которая решала бы задачи, определенные требованиями заказчика;

— физическое размещение транзисторов на плате наиболее эффективным образом;

— проведение соединений между контактами схемы.

Именно на последнем этапе и используется задача Штейнера, а точнее, ее манхеттенская версия. Хотя развитие производства VLSI-плат порождает новые условия на получающиеся пути, но до сих пор именно минимальная длина продолжает оставаться в этом приложении главной целью при прокладке сетей. Для упрощения проектирования и производства VLSI-соединение ограничивается небольшим числом направлений. До недавнего времени проектировщики пользовались манхэттенской метрикой, что вызывало интерес к задаче Штейнера на плоскости с такой метрикой, однако сейчас все более привлекательными становятся неманхэттенекие метрики - У-архитектура (позволяющая углы 0, 120 и 240°), а также Х-архитектура (позволяющая углы в 45° в дополнение к манхэттенским). [46, 51, 37].

В последнее время растет интерес к практическим методам вычисления субоптимальных деревьев Штейнера для задач размером в десятки тысяч, терминалов. Задачи такого рода становятся обычными в современном VLSI-проектировании.

Задача Штейнера применяется также в программируемых пользователем логических матрицах (Field-Programmable Gate Arrays, FPGA) [6, 5, TJ. Они представляют собой многократно используемые прикладные интегральные схемы, конфигурацию которых пользователь может достаточно легко изменить. Есть несколько доступных технологий FPGA, но чаще всего они состоят из симметричной матрицы реконфигурируемых логических блоков.

1.3.2. Восстановление филогенетических деревьев

Филогенетическое дерево - это дерево, отражающее эволюционные взаимосвязи между различными видами или другими сущностями, имеющими общего предка. Один из способов построения таких деревьев — техника, использующая данные о белковых последовательностях [17].

В этом способе для конкретного набора биологических видов, каждому из которых сопоставлены одинаковые протеиновые последовательности, строится дерево. Символами в протеиновой последовательности обычно являются аминокислоты, каждая из которых состоит из упорядоченной тройки нуклеотидов.

Природа использует 4 нуклеотида: А, С, G, U, так что в принципе может быть 64 таких тройки, но существует только 20 аминокислот. Таким образом, каждая последовательность — это строка из символов алфавита размера 20. На множестве таких последовательностей задана метрика, называемая расстоянием Хэмминга: при условии, что число элементов в обеих строках равно, оно определяется как число отличающихся символов в них.

В графе G(M, N) множество М — множество иуклеотидных последовательностей, а N = М х М (полный граф), при этом длины дуг графа задаются расстояниями Хэмминга между соответствующими цепочками.

1.3.3. Интерактивная телекоммуникация

Классический формат телевещания и видеоконференций подразумевает, что все пользователи получают одну и ту же информацию из источника вещания, не имея возможности повлиять на ее выбор и передачу. Однако в последнее время, в связи с развитием волоконных технологий на смену старым форматам приходят новые форматы вещания, такие как интерактивное телевидение и интерактивные видеоконференции, в которых ползователь может выбирать информацию, которую он хочет получать. Такие форматы характеризуются выборочной многоточечной коммуникацией [12].

Примером интерактивной услуги является уже получившая большое распространение услуга Video-on-Demand (видео по требованию). Ее смысл заключен в том, что абонент кабельной телекомпании может в любое время заказать любое доступное видео из каталога, и оно будет ретранслированно на его телевизионную приставку. Другим примером является возможность выбора абонентом желательного качества передаваемого изображения одной и той же транслируемой в данный момент передачи.

Таким образом, перед поставщиком такой услуги ставится задача по установлению оптимальных путей до абонентов для выборочной мультивещательной трансляции. Особенно она актуальна для сетей,

использующих виртуальную цепь путей, таких как ATM и Frame Relay [67]. Данная задача часто моделируется как графовая задача Штейнера в той или иной форме, в зависимости от предоставляемой услуги.

Кроме того, специфика данной области применения часто накладывает на задачу Штейнера дополнительные ограничения и ставит новые вопросы — например, необходимость строить или перестраивать дерево Штейнера оптимальным образом «на лету» при добавлении и удалении того или иного приемника.

Таким образом, нельзя не отметить, что задача Штейнера широко востребована в современных технологичных процессах, как уже давно использующихся и развитых, так и только начинающих развиваться, а значит исследование и построение новых, отвечающих современным требованиям алгоритмов решения по-прежнему необходимо.

1.4. Описание работы по главам

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

В главе «Алгоритм А:-кластер пой оптимизации» представлен раз-

работанный автором эвристический алгоритм для решения этой задачи.

Общая идея данного алгоритма заключается в том, что исходный граф разбивается на не более чем к непересекающихся подграфов, на каждом из которых ставится отдельная задача Штейнера, индуцированная исходной. Задачи Штейнера не более чем с к терминалами решаются с помощью точного метода. Подзадачи с более чем к терминалами в свою очередь вновь разбиваются на более мелкие подзадачи.

После преобразования исходной задачи с учетом найденных частичных решений, с помощью точного метода находится промежуточное дерево Штейнера, которое затем оптимизируется с помощью алгоритма локальных улучшений.

Также в этой главе доказывается теорема о вычислительной сложности этого алгоритма, составляющей 0{2ktn\ogm).

В главе «Приближенный метод й1* на евклидовых графах» представлен разработанный автором эвристический алгоритм для решения ориентированной задачи Штейнера на евклидовых графах, то есть таких, чьим вершинам соответствуют координаты двумерного евклидового пространства.

Данный метод основан на идее алгоритма поиска кратчайшего пути А* [34], который использует некоторую дополнительную эвристическую функцию (например, евклидово расстояние между двумя точками), чтобы оценить расстояние от текущей точки пути до конечной. Представленный алгоритм адаптирует данное соображение к задаче Штейнера, позволяя значительно уменьшить число рассматриваемых подмножеств терминалов в методе динамического про-

граммирования, в том числе сделать их число полиномиальным в приближенном методе.

Кроме того, в главе находится теоретическая оценка вычислительной сложности и доказывается полиномиальность полученного алгоритма решения.

В главе «Вычислительные оптимизации» рассматриваются технологические особенности реализации представленных в работе алгоритмов на языке позволяющие уменьшить время решения и объем занимаемой памяти. Кроме того, представлены параллельные версии всех алгоритмов, которые дают возможность значительно уменьшить время решения задач на компьютерах с многоядерными центральными процессорами.

В главе «Вычислительные результаты» проводятся экспериментальные исследования представленных методов, производится их сравнение с другими известными приближенными методами решения задачи Штейнера, а также и друг с другом, на известных наборах задач из библиотеки 81ет1ЛЬ [68], а также на собственноручно сгенериро-ваных наборах задач.

Кроме того, проводится сравнение быстродействия параллельных и однопоточных реализаций всех представленных в работе алгоритмов.

В главе «Выводы» по результатам исследования делаются выводы о применимости представленных методов на практике, преимуществах и недостатках в сравнении с другими методами, а также приводятся варианты возможных модификаций и улучшений данных методов с целью улучшения их быстродействия и коэффициента аппроксимации, и, наконец, делается вывод о целесообразности

дальнейшего исследования в данном направлении.

1.5. Основные определения и обозначения

Ориентированный граф определяется множеством вершин М и множеством дуг N, причем каждой дуге j £ N сопоставляется упорядоченная пара вершин, называемых соответственно началом и концом этой дуги, beg j и endj/.

Задача Штейнера на ориентированном графе ставится следующим образом:

Пусть G(M,N) — ориентированный граф с заданной на дугах функцией d : N —> R+.

В множестве М выделена вершина Ь, называемая началом, и множество вершин Е, называемых конечными или терминалами.

Любое ориентированное дерево в графе. С, с корнем в Ъ и содержащее пути от Ь до любого терминала из Е, называется деревом, Штейнера.

Длиной графа называется сумма длин всех его дуг: d(G) = EneJV d(n)•

Задача Штейнера на графах состоит в поиске минимального дерева Штейнера, т. е. дерева Штейнера наименьшей длины.

Если задано некоторое подмножество вершин М' С М, положим N(M') = {j е N : beg j, end j G M'}. Граф G(M',N(M')) будет называться графом, ограниченным, множеством М'.

Назовем вершину в ориентированном дереве вершиной разветвления, если из нее выходит не менее двух дуг.

Введем дополнительно следующие обозначения, которые будут

встречаться в тексте работы:

Для произвольного графа Г обозначим через М(Г) множество вершин этого графа, через т(Г) = |М(Г)| — их количество, через N(T) — множество дуг, через п(Г) — их количество. Для произвольной поставленной на графе Г задачи Штейнера обозначим через -Е'(Г) множество терминалов, через 6(Г) — начальную вершину.

Пусть Т — некоторое дерево. Тогда для любых вершин х,у Е Т будем обозначать через Р[х,у] путь от ж до у, если он существует.

Дерево Штейнера Т называется полнымесли все терминалы в этом дереве являются листьями.

2. Состояние дел

Задаче Штейнера, на ориентированных графах уделяется меньше внимания, чем геометрической задаче и задаче в сетях, вследствие этого она обладает меньшим числом известных методов решения. Тем не менее и для данной версии задачи существует немало алгоритмов, как точных, так и приближенных. Эти алгоритмы используют много различных подходов к решению: жадная оптимизация, метод локального поиска, генетические алгоритмы [46], алгоритмы отжига, методы линейного программирования, использующие релаксации, методы искусственного интеллекта, использующие, например, нейронные сети.

Рассмотрим подробнее наиболее известные из имеющихся точных и приближенных методов для решения ориентированной задачи Штейнера на графах.

2.1. Точные алгоритмы

Существует несколько подходов к точному решению задачи Штейнера на ориентированных графах. Наиболее распространенные из них — использование динамического программирования и уравнения Беллмана, а также приведение задачи Штейнера к задаче линейного программирования (точнее, к задаче 0-1-программирования), и использование обширного инструментария, существующего для решения таких типов задач.

Ниже опишем подробнее эти методы, поскольку они будут использоваться в дальнейшем в алгоритмах, описанных в диссертации.

2.1.1. Алгоритм динамического программирования

Для задачи Штейнера на графах известен точный алгоритм решения, основанный на принципе динамического программирования и уравнении Беллмана. Задача Штейнера решается одновременно для любых начальных вершин т Е М и любых возможных подмножеств ЕР С Е.

Принципиально алгоритм выглядит следующим образом:

Будем обозначать через (г, Ер) состояние процесса решения, при котором решается задача Штейнера для начальной точки г и множества терминалов Ер, а через у(г, Ер) - решение этой задачи, т. е. длину минимального дерева Штейнера. Для того, чтобы решить задачу, необходимо найти у(Ь, Е).

Пусть процесс находится в состоянии (г, Ер). Считаем что г ф Ер. В этом состоянии можно выбрать один из вариантов продолжения нахождения решения:

— перейти по какой-либо дуге, начинающейся в г, в другую вершину, скажем, ¿1, и решать задачу {ъ\^Ер)\

— разветвить путь, выбрав разбиение терминального множества Ер — и^ Ерь, и для каждого состояния (г, Еррешить такую же задачу.

Формализуя вышенаписанное, получаем следующее уравнение Беллмана:

г;(г, ЕР) = тт{усопЬ(1, ЕР{{}), ирагЬ(г, ЕР{{})}, (1)

где усопЪ ~ наименьшие затраты при наилучшем переходе по какой-

либо дуге:

Усот{г, ЕР) = + v(endj, EP)\Ъegj = г}, (2)

а ^рал ~ наименьшие затраты при наилучшем разбиении терминального множества Ер на два подмножества А и Ер \ А:

г;рах4(г, ЕР) = тт{г)(г, А) + «(г, \А)\Ас Ер}. (3)

При этом, если Ер состоит из одной вершины, то дерево Штейнера для состояния (г, Ер) — это кратчайший путь между этими вершинами, который можно вычислить по алгоритму Дейкстры.

Технически алгоритм реализуется следующим образом. Имеется таблица размером \М\ х где в ячейке [г, э] хранится текущая длина графа, соединяющего вершину ] £ М с вершинами г-го подмножества Е, т. е. Ег) (нумерация подмножеств может быть любой, для которой выполняется следующее условие: С Sj г <

Выполняется цикл по подмножествам Е, причем на г-й итерации рассчитываются по методу Дейкстры все-длины деревьев для г-го подмножества. Мы имеем ввиду несколько измененный метод Дейкстры: в нем учитывается, что есть вершины из М, для которых уже вычислены промежуточные значения длины. Они помещаются в множество просматриваемых вершин М\ с имеющейся текущей длиной (см. алгоритм Дейкстры), после чего процесс работы алгоритма Дейкстры происходит как обычно.

Далее, для всех уже посчитанных подмножеств («о < г), таких что Ег0 П Ег — 0, рассматривается подмножество Е^ = Е^ и Е1^, и для каждой вершины ] значение соответствующей ячейки [Ьл], т. е.

Д^), пересчитывается по формуле

у{з,Ек) = т + (4)

В результате работы алгоритма в ячейке с индексом [6,2^1] будет содержаться длина искомого минимального дерева Штейнера. Для того, чтобы найти само дерево, достаточно иметь еще одну таблицу такого же размера, в которой будут храниться входящие в каждую вершину дуги, найденные алгоритмом Дейкстры.

Более подробно вычислительная реализация метода динамического программирования будет описана в главе «Вычислительные оптимизации».

2.1.2. Сведение к задаче линейного программирования

Многие алгоритмы дискретной оптимизации основываются тем или иным образом на подходах, связанных с линейным программированием. В общем случае применение линейного программирования к задачам оптимизации заключается в следующем: комбинаторная задача переформулируется как задача целочисленного программирования, с бинарными ограничениями на переменные вида х{ £Е {0,1}, которые затем ослабляются и задача сводится к задаче линейного программирования, решаемой за полиномиальное время. Решение ЛП может быть использовано как верхняя граница возможного решения задачи, в рамках точных (метод ветвей и границ, метод отсечений Гомори и другие) или приближенных методов, задачи линейного программирования.

Примеры применения линейных релаксаций для задачи Штейнера также встречаются в литературе: для нахождения нижних границ

в точных методах, для методов связанных с сокращениями, основанными на граничных значениях [43], и методов связанных с сокращениями, основанными на разбиении [44].

Определим общие положения данного способа решения.

Разрезом в графе С = (М, И) называется разбиение множества вершин М на два дизъюнктных подмножества С = где

(0СШсМк\¥=М \ \¥). Обозначим 5~ (IV) множество дуг € -/V, для которых 7Пг е IV и т^ <Е УУ. 8+{У/) определяется аналогичным образом. Пример разреза представлен на рисунке 1. В нем кругами и крестами отмечены вершины из, соответственно, и IV. Жирным выделены дуги, принадлежащие 8~{\¥).

Рисунок 1 - Пример разреза

Для приведения задачи Штейнера к задаче целочисленного программирования сопоставим каждой дуге [т^ш^] £ N булеву переменную Х[тищ], показывающую, принадлежит дуга решению (т. е. х[т,-,ту] = 1) или нет — 0)- Для любого В С ЛГ, обозначим

Одна из наиболее часто применяемых релаксаций для задачи

О

х{В) = Т;певх>

•пев ^п■

Штейнера является релаксация по ориентированному разрезу.

Обозначим через р множество {W С М\ {fe}, W f]E ^ 0}, назовем его ориентированным разрезом. Таким образом, подмножество вершин графа входит в него, если ему принадлежит хотя бы один терминал, и не принадлежит начальная вершина.

Тогда соответствующая задача целочисленного программирования для задачи Штейнера выглядит следующим образом:

min Е

neN

Е Яп >1, VW £ р, (6)

neJ-(W)

Хп е {о, 1}, Vn 6 N, (7)

а ее релаксация достигается заменой условий (7) на условия:

хп > 0, Vn Е N. (8)

Двойственная задача для этой релаксации выглядит следующим образом:

max Е Vw, (9)

wep

Е Vw < сп, Vn € N, (10)

wepmes-(w)

yw >0, VW e p. (11)

Ограничения (6) называют ограничениями разреза Штейнера. Они гарантируют, что в любом наборе дуг, относящихся к подходящему решению, существует путь от Ь до любого из терминалов. Впервые эту релаксацию предложил Эдмондс в [23] как точную формулировку для задачи об остовном дереве. Вонг [59] позже обобщил

ее для ориентированной задачи Штейнера. Там же он представил приближенный алгоритм, основанный на данной релаксации, который мы приведем ниже.

Также известны дополнительные ограничения, называемые ограничениями баланса потока, которые дают более строгую релаксацию:

х(6~(т)) < х{6+(щ)) щеМ\Е. (12)

Обзор и сравнение этих и других релаксаций даны в [42].

Напомним, что разрывом целочисленности называют максимальное отношение целочисленного и дробного оптимумов среди всех возможных задач.

Ни одна из существующих на данный момент релаксаций не имеет доказанного разрыва целочисленности меньшего, чем 2. Тем не менее, считается, что приведенная выше релаксация по ориентированному разрезу имеет разрыв целочисленности меньший 2.

Как известно, существует достаточное число методов решения задачи целочисленного программирования, например метод ветвей и границ, метод отсечений Гомори, и другие, с помошыо которых можно найти точное искомое решение задачи Штейнера.

2.2. Приближенные алгоритмы

Как известно задача Штейнера является ЫР-трудной [1], и, несмотря на существование точных методов, а также наличие различных техник сокращения графа, позволяющих уменьшить объем входный данных [45], время решения остается большим и редко приемлемым на практике.

В связи с этим большое внимание уделяется построение различных приближенных методов, аппроксимаций и эвристик. Рассмотрим некоторые из них и определим основные направления изучения.

2.2.1. Алгоритм Такахаши-Мацуямы

Один из наиболее известных приближенных алгоритмов поиска кратчайшего дерева Штейнера, (как на ориентированных графах, так и в сетях) был представлен японскими математиками Такахаши и Мацуямой в [55]. Являясь очень простым, он, тем не менее, дает

достаточно хорошую аппроксимацию с доказанным коэффициентом 1

2 • (1 — ——). Суть алгоритма состоит в следующем. \Ь\

Данный алгоритм на каждом шаге строит дерево с корнем в Ь, содержащее некоторое подмножество Е, и добавляет к нему новый терминал из Е вместе с кратчайшим путем, соединяющим дерево и терминал. Обозначим гп) наименьший из всех кратчайших путей между множеством вершин XV С М и т ф. IV.

Обозначим через с(И^,т) стоимость пути р(\¥,т). Тогда алгоритм нахождения приближенного решения задачи Штейнера выглядит следующим образом:

Алгоритм Такахаши-Мацуямы

Инициализация: дерево Т\ — (М1,А^) состоит из одной начальной вершины Ъ\ М\ — {6}, N1 = 0 для всех г = 2,3,..., к делать

найти терминал в{ £ Е \ 1, такой что с(Мг_1,бг) = тт{с(Мг-1, тп^)\rrij £ Е \ М^ 1}.

построить дерево % = (М^, А^), добавив 1,^) к

т. е. Мг = Мг_! и М(р(Мг.ъ е>)) и 7Уг = ЛГ^ и ец)).

конец для всех Вывести

Вычислительная сложность данного алгоритма равна 0(£п2), где п = |]У|, а г = \Е\.

2.2.2. Приближенные алгоритмы основанные на линейном программировании

Алгоритм Вонга является первым в ряду алгоритмов аппроксимации задачи Штейнера, использующих для этого метод одновременного решения прямой и двойственной задач линейного программирования. В данном случае одновременно находится приближенное решение задачи целочисленного программирования и допустимое решение двойственной задачи линейного программирования.

Прежде, чем описать сам алгоритм Вонга, приведем общую схему таких методов.

Рассмотрим условия дополняющей нежесткости для задачи линейного программирования и двойственной к ней. Прямые условия дополняющей нежесткости, относящиеся к прямым переменным:

хп > 0 ^ уш = Сп, (13)

1¥ер:пе5~(Ш)

а также обратные условия дополняющей нежесткости, относящиеся к двойственным переменным:

уш>0=> ^ х* = 1- (14)

пе6~(\¥)

Общая схема метода одновременного решения прямой и двойственной задачи для приближенных алгоритмов выглядит следующим образом [41]:

Общий метод одновременного решения прямой и двойственной задачи для приближенных алгоритмов

Инициализация: двойственное решение у 0; недопустимое решение А С N

пока не существует допустимого целочисленного решения удовлетворяющего прямым условиям дополняющей нежесткости делать найти направление роста для двойственной задачи (двигаясь по направлению к допустимости решения прямой задачи) конец пока

Вернуть допустимое целочисленное решение х, удовлетворяющее прямым условиям дополняющей нежесткости

Метод одновременного решения прямой и двойственной задачи для приближенных алгоритмов отличается от обычного тем, что в нем не обязательно выполнение двойственных условий дополняющей нежесткости. Для ИР-трудных задач мы не можем надеяться на удовлетворение обоих этих условий: выполненение их обоих ведет либо к нахождению оптимального решения, либо к невозможности найти решение. Тем не менее, хотя двойственные условия дополняющей нежесткости и не выполняются, основная идея подобных алгоритмов заключается в том, чтобы как можно меньше эти условия нарушать.

Алгоритм имеет дело с решением двойственной задачи, изначаль-

но равным 0, и недопустимым решением прямой задачи целочисленного программирования А С ЛГ, первоначально являющимся пустым множеством. На каждой итерации алгоритм добавляет дугу к текущему А, пока А не станет допустимым решением. Выбор дуги осуществляется следующим образом:

Если текущее решение А недопустимо, то неравенство (6) не удовлетворяется для некоторых подмножеств из р (напомним, р = {]¥ С М \ {Ь},]¥[)Е ф 0}). Существует двойственная переменная ?/и/. относящаяся к каждому из подмножеств. Идея состоит в том, чтобы выбрать множество подмножеств, нарушающих (6), назовем их Уго1а1е(1{А)) и одновременно увеличить двойственные переменные, соответствующие всем IV Е Vю1сйе(1(А), пока двойственное ограничение не станет выполняться вплотную. Дуга, на которой двойственнное ограничение стало выполняться как равенство, добавляется в А. Отметим, что такой выбор дуги всегда оставляет двойственное решение допустимым, а прямые условия дополняющей нежесткости — выполняющимися.

Прямодвойственный алгоритм (оригинальная версия)

Инициализация: у 0, А 0,1 0 (счетчик) пока А недопустимое делать 1^1 + 1

у <г- Ую1аЬес1(А) (подпрограмма, возвращающая множество подмножеств р, нарушающих ограничения)

Увеличить уцг одновременно для всех XV Е и, пока не найдется дуга ще А такая, что У^ = сщ

А^АЩт} конец пока

Список литературы диссертационного исследования кандидат физико-математических наук Ейбоженко, Дмитрий Анатольевич, 2012 год

Список литературы

1 Гэри М., Джонсон Д. Вычислительные машины и труднорешае-мые задачи. М. : Мир, 1982.

2 Диниц Е. А. Экономические алгоритмы нахождения кратчайших путей в сетях / под ред. Ю. С. Попкова и Б. JI. Шмульяна, Институт Системного Анализа, М., 1978.

3 Романовский И. В. Дискретный анализ. СПб. : Невский Диалект; БХВ-Петербург, 2003.

4 Кристофидес Н. Теория графов : алгоритмический подход. М. : Мир, 1978.

5 Alexander М., Cohoon J. P., Ganley J. L., and Robins G. An architecture-independent approach to FPGA routing based on multi-weighted // EURO-DAC '94 Proceedings of the conference on European design automation, 1994.

6 Alexander M., Robins G. An architecture-independent unified approach to FPGA routing / Dept. of Computer Science, Univ of Virginia, 1993.

7 Alexander M. J., Robins G. New Perfomance-Driven FPGA Routing Algorithms / Technical Report, 1994.

8 Althaus E., Polzin Т., Daneshmand S. V. Improving linear programming approaches for the Steiner tree problem /7 Experimental and Efficient, Algorithms : Second International

Workshop, WEA 2003, Ascona, Switzerland, May 26-28, 2003 / Proceedings, Springer, 2003, P. 620-621.

9 Andrews G. Foundations of Multithreaded, Parallel, and Distributed Programming. Addison-Wesley, ISBN 0-201-35752-6, 2000.

10 Arora S., Barak B. Computational Complexity - A Modern Approach. Cambridge, ISBN 978-0-521-42426-4, 2009.

11 Arora S. Polynomial-Time Approximation Schemes for Euclidean TSP and other geometric problems /7 Journal of the ACM (JACM), 1998. No. 45(5). P. 753-782.

12 Awerbuch В., Azar Y., Gawlick E. Maximal Dense Trees and Competitive On-line Selective Multicast (Extended Abstract) // Computer, 2007.

13 Bishop P., Warren N. Lazy instantiation : Balancing performance and resource usage. 1999. [Электронный ресурс]. URL : http: / / www.j avaworld. com/j avaworld/j avatips/j w-j ava,tip6 7. html (дата обращения: 24.02.2010)

14 Charikar M., Chekuri C., et. al. Approximation algorithms for directed Steiner problems // Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, 1998. P. 192-200.

15 Charikar M. Approximation Algorithms for Directed Steiner Problems. Journal of Algorithms, 1999. No. 33(1). P. 73-91.

16 Cherkassky B. V., Goldberg A. V., Silverstein C. Buckets, heaps, lists, and monotone priority queues /,/ Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, 1997. P. 83-92.

17 Chin L. L., Chuan Y. T., Lee R. The Full Steiner Tree Problem in Phylogeny // Computing and Combinatorics, 2002.

18 Cormen T., Leiserson C., Rivest R., and Stein C. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001.

19 Dearagao M., Uchoa E., and Werneck R. Dual Heuristics on the Exact Solution of Large Steiner Problems // Electronic Notes in Discrete Mathematics, 2001. Vol. 7. P. 150-153.

20 Denardo E., Fox B. Shortest-route methods: 1. reaching, pruning, and buckets // Operations Research, 1979.

21 Dial R. B. Algorithm 360: Shortest Path Forest with Topological Ordering // Comm. ACM, 1969. No. 12. P. 632-633.

22 Dijkstra E. W. A note on two problems in connexion with graphs // Numerische Mathematik, 1959. No. 1. P. 269-271.

23 Edmonds J. Optimum branchings // Journal of Research of the National Bureau of Standards B. 71B, 1967. P. 233-240.

24 Fredman M. L., Tarjan R. E. Fibonacci heaps and their uses in improved network optimization algorithms // Journal of the ACM (JACM), 1987. Vol. 34, No. 3, P. 596-615.

25 Gafni E. M., Bertsekas D. P. Path assignment for virtual circuit routing // Proceedings of the symposium on Communications Architectures & Protocols (SIGCOMM '83), 1983.

26 Gamma E., Helm R., Johnson R., Vlissides J. Design Patterns : Elements of Reusable Object-Oriented Software. Addison-Wesley, 1994.

27 Goldberg A. V., Kaplan H., Werneck R„ Reach for a : Efficient, point-to-point shortest path algorithms // Proceedings of the eighth Workshop on Algorithm Engineering and Experiments and the third Workshop on Analytic Algorithmics and Combinatorics, 2006. P. 129.

28 Goldberg A. V., Shortest path algorithms: Engineering aspects // Algorithms and Computation, 2001. P. 502-513.

29 Goldberg A. V., Silverstein C. Computational Evaluation of Hot Queues // Data structures, near neighbor searches, and methodology : fifth and sixth DIMACS implementation challenges : papers related to the DIMACS challenge on dictionaries and priority queues (19951996) and the DIMACS challenge on near neighbor searches (19981999), 2002. Vol. 59, P. 49.

30 Goldberg A. V., Silverstein C. Implementations of Dijkstra, Algorithm Based on Multi-Level Buckets. Network optimization, 1997. P. 292327.

31 Goldberg A. V. A practical shortest path algorithm with linear expected time // SIAM Journal on Computing, 2008. Vol. 37. P. 1637.

32 Gropl С., Hougardy S., Nierhoff Т., Prornel H. J. Lower bounds for approximation algorithms for the Steiner tree problem // Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science, 2001.

33 Hanan M. On Steiner's problem with rectilinear distance // SIAM Journal Of Applied Mathematics, 30(1), 1966. P. 104-114.

34 Hart P. E., Nilsson N. J., Raphael B. A formal basis for the heuristic determination of minimum cost paths // IEEE transactions on Systems Science and Cybernetics, 1968. No. 4. P. 100-107.

35 Hillar G. Professional Parallel Programming with Сф. Wiley Publishing, 2010.

36 Hwang F. K. A Linear Time Alorithm for Full Steiner Trees. Operations Research Letters, 1986. No. 4(5). P. 235-237.

37 Kahng А. В., Robins G. A New Class Of Iterative Steiner Tree Heuristics With Good Performance // IEEE Transactions Of Computer-Aided Design of Integrated Circuits And Systems, 1992. No. 11(7). P. 893-902.

38 Krazit. T. Intel pledges 80 cores in five years. CNET, 2006. [Электронный ресурс]. URL : http://news.cnet.com/

39 Molle D., Richter S., and Rossmanith P. A faster algorithm for the Steiner tree problem. STACS 2006, 2006. No. 1. P. 561-570.

40 McGregor J. Mobile Processor Review / Technical Review, InStat, 2009.

41 Melkonian V. New primal-dual algorithms for Steiner tree problems // Computers & Operations Research. 34, 2007. P. 2147-2167.

42 Polzin T., Daneshmand S. V. A comparison of Steiner tree relaxations // Discrete Applied Mathematics, 2001. No. 112. P. 241-261.

43 Polzin T., Daneshmand S. V. Improved algorithms for the Steiner problem in networks // Discrete Applied Mathematics, 2001. No. 112. P. 263-300.

44 Polzin T., Daneshmand S. V. Partitioning techinques for the Steiner problem / Research Report MP1-1-2001-1-006. Max-Planck-Institut fur Informatik, Stuhlsatzenhausweg 85, 66123 Saarbrücken, Germany, 2001.

45 Prömel H. J., Steger A. The Steiner tree problem: a tour through graphs, algorithms, and complexity. Vieweg I Teubner, 2002.

46 Rabkin M. Efficient use of Genetic Algorithms for the Minimal Steiner Tree and Arborescence Problems with applications to VLSI Physical Design // Genetic Algorithms and Genetic Programming at Stanford. 2002. No. 1. P. 195-202.

47 Rajagopalan S., Vazirani V. V. On the bidirected cut relaxation for the metric Steiner tree problem / SODA, — 2000.

48 Rayward-Smith. V. The computation of nearly minimal Steiner trees in graphs // International Journal of Mathematical Education in Science and Technology, 1983. No. 14.1.

49 Richter J. CLR via C# (3rd Edition). Microsoft Press, 2010.

50 Robins G., Zelikovsky A. Improved Steiner Tree Approximation in Graphs // Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, 2000.

51 Santos M., Uchoa E. Distributed Dual Ascent Algorithm for the Steiner Problem in Graphs Sequential Wong's Dual Ascent Algorithm // Production Engineering, 2006. P. 1-14.

52 Smith J. M., Lee D. T., Liebman J. S. An 0(nlogn) heuristic for Steiner minimal tree problems in euclidean metrics // Networks, 1981. No. 11. P. 23-29.

53 Stroustrup B. The C++ Programming Language (Third Edition and Special Edition). Addison-Wesley, 2004.

54 Sutter H. The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software // Dr. Dobb's Journal, 2005. No. 30(3),

55 Takahashi H., Matsuyama A. An Approximate Solution for the Steiner Problem In Graphs. Math. Japónica, 1980. No. 6. P. 573-577.

56 Troelsen A. Pro C# 2010 and the .NET 4 Platform, 5th Edition. APRESS, 2010.

57 Vuillemin J. A data structure for manipulating priority queues // Communications of the ACM, 1978. Vol. 21, No. 4. P. 309-315.

58 Wagner R. A. A shortest path algorithm for edge-sparse graphs // J. Assoc. Comput. Math., 1976. No. 23. P. 50-57.

59 Wong R. T. A dual ascent approach for Steiner tree problems on directed graphs // Math. Programming, 1984. No. 28. P. 271-287.

60 Zachariasen M., Winter P. Concatenation-Based Greedy Heuristics for the Euclidean Steiner Tree Problem / Technical Report 97/20, DIKU, Department of Computer Science, University of Copenhagen, 1997.

61 Zachariasen M. Rectilinear Full Steiner Tree Generation / Technical Report 97/20, DIKU, Department of Computer Science, University of Copenhagen, 1997.

62 Zelikovsky A. 11/6-approximation algorithm for the Steiner problem on graphs // Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity. Ann. Disc. Math., 1992. P. 351-354.

63 Zelikovsky A. A Series of Approximation Algorithms for the Acyclic Directed Steiner Tree Problem /./ Framework, 1997. P. 1-10.

64 Zelikovsky A. An 11/6-approximation algorithm for the network steiner problem // Algorithmica, 1993. No. 9. P. 463-470.

65 Zelikovsky A. Better Approximation Algorithms for the Network and Euclidean Steiner Tree Problems / Technical report, Kishinev, 1995.

66 Zelikovsky A. The last achievements in Steiner tree approximations // CSJM v.l, n.l (1), 1993.

67 Zhang Y. Virtual Circuit Routing. Class Report (October 2003), 2003. P. 1-11.

68 SteinLib Testdata Library, 2009. [Электронный ресурс]. URL : http://steinlib.zib.de/steinlib.php (дата обращения : 27.05.2009)

69 The Computer Language Benchmarks Game. [Электронный ресурс]. URL : http://shootout.alioth.debian.org (дата обращения :

01.09.2008)