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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Надр

завах рукописи

Ейбоженко Дмитрий Анатольевич

Приближенные методы решения задачи

штейнера на ориентированных графах

Специальность 05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей.

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата физико-математических наук

з т 2сї2

Санкт-Петербург 2012

'І

005015862

Работа выполнена на кафедре исследования операций математике, механического факультета Санкт-Петербургского государственного универ ситета.

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

доктор физико-математических наук, профессор Романовский Иосиф Владимирович

доктор физико-математических наук, профессор Чирков Михаил Константинович (Санкт-Петербургский государственный университет)

доктор технических наук, профессор Филиппова Анна Сергеевна (Уфимский государственный авиационный технический университет)

Санкт-Петербургский экономико-математический институт РАН

Защита состоится «/Я 2012 г. в -{£ часов на заседании со

вета Д 212.232.51 по защите докторских и кандидатских диссертаци при Санкт-Петербургском государственном университете по адресу: 19850-Санкт-Петербург, Петродворец, Университетский пр., д. 28, математике механический факультет, ауд. 405.

С диссертацией можно ознакомиться в Научной библиотеке имени М. Горькс го Санкт-Петербургского государственного университета по адресу: 19903' Санкт-Петербург, Университетская наб., д. 7/9.

Автореферат разослан 2012 года.

Ученый секретарь диссертационного совета ^ доктор физико-математических наук, доцент

/

С

Кривулин Н.'

^бщая характеристика работы

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

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

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

Актуальность темы

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

Как известно, задача Штейнера в графовой форме является NP-трудной [6]. Большинство исследований данной задачи ставят целью найти приемлемые с точки зрения быстродействия и точности решения приближенные алгоритмы, эвристики и аппроксимации, с применением широкого спектра подходов: жадных алгоритмов, методов динамического программирования, генетических методов, а также различных аппроксимаций, основанных на линеаризации задачи и релаксации полученных условий. Большой вклад в исследование различных постановок задачи Штейнера внесли А. Зеликов-ский, А. Иванов, А. Тужилин, М. Zachariasen, S. Arora, М. Hwang.

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

3

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

Цель работы

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

Методы исследования

При экспериментальных исследованиях точности разработанных алгоритмов и сравнения их с другими распространенными методами были использованы программные реализации их на языке С# 4.0. В качестве тестовой базы использовались задачи из базы задач SteinLib [8], а также сгенерированные автором наборы задач.

Для разработки параллельных реализаций методов была использована библиотека Microsoft Task Parallel Library.

Основные положения, выносимые на защиту

Среди полученных в ходе исследования результатов можно выделить следующие:

1. Разработан и реализован метод fc-кластерной оптимизации для задачи Штейнера на ориентированных графах.

2. Разработан и реализован приближенный метод S* для решения задачи Штейнера на евклидовых ориентированных графах.

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

4. Проведены экспериментальные исследования данных методов и показана их практическая ценность.

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

Научная новизна

Все результаты, выносимые на защиту, являются новыми.

Практическая значимость

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

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

Апробация работы

Основные результаты работы докладывались на российской конференции по проблемам дискретной оптимизации и исследования операций БООИ,-2010, на межвузовской научной конференции но проблемам информатики СПИСОК-2011, международной конференции «Математика, экономика, менеджмент: 100 лет со дня рождения Л. В. Канторовича», а также на семинарах кафедры исследования операций математико-мехапического факультета СПбГУ.

Публикации по теме работы

Материалы диссертации опубликованы в пяти работах [1,2,3,4,5). Из них работы [2,3] — в списке журналов, рекомендованных ВАК. Работа [2] выполнена в соавторстве: соискателю принадлежат доработка и реализация ограниченного метода динамического программирования, доказательство точности, проведение вычислительных экспериментов.

Объем и структура работы

Диссертация состоит из введения, пяти глав, заключения и приложения. Полный объем диссертации — 120 страниц текста с 18 рисунками и 2 таблицами. Список литературы содержит 69 наименований на 9 страницах.

Содержание работы

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

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

Одним из наиболее широко распространенных методов точного решения является алгоритм, основанный на методе динамического программирования и уравнении Беллмана. Задача Штейнера решается одновременно для любых начальных вершин т £ М и любых возможных подмножеств Ер С Е. Обозначим через (г, Ер) — состояние процесса, в котором решается задача Штейнера для начальной точки г и множества терминалов Ер, а через г/(г, Ер) — решение этой задачи. Необходимо найти у(Ь, Е).

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

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

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

Таким образом, получаем уравнение Беллмана:

v(i,EP) = min{fconti(i, Ep{i}),vpBVt(i, £р{г})}, (1)

где vcont — наименьшие затраты при наилучшем переходе по какой-либо дуге:

?W.(i> ЕР) = mm{lj + v(endj, EP)\hegj = г}, (2)

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

?W(г, ЕР) = min{i;(M) +v(i,EP \ А)\А с ЕР}. (3)

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

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

min J2 с«жп, (4)

neN

Е >1, VW 6 р, (5)

пей- (IV)

■ я:« е {0,1}, Vnew, (6)

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

хп > 0, Vrc G N. (7)

7

Здесь р= {Ш С М\ {Ь},\У П Е ф 0}, IV = М \ УГ, а 6'{IV) - это множество дуг [у^уД е Ы, для которых VI 6 IV И V, € IV,

Наиболее широко известный приближенный метод — алгоритм Такахаши-Мацуямы [9], суть которого состоит в том, что на каждом шаге к уже имеющемуся дереву с корнем в Ь, содержащему некоторое подмножество Е добавляется новый терминал из Е вместе с кратчайшим путем, соединяющим дерево и терминал.

В главе также описывается общая схема жадного сокращения, которую используют многие приближенные алгоритмы [11]. В качестве первого приближения берется минимальное остовное дерево на графе й. Рассматриваются все полные (т. е. такие, все терминалы которых являются листьями) деревья Штейнера из определенного класса К, из них выбирается то дерево Т, которое минимизирует некоторую оценочную функцию /(Т), и Т сокращается (уменьшаются до нуля стоимости дуг минимального остовного дерева, заканчивающихся в терминалах, содержащихся в Т). После того, как длина минимального остовного дерево становится равной нулю, из выбранных полных деревьев восстанавливается дерево Штейнера. Разные алгоритмы используют разные классы К (пути, звезды, трехтерминальные графы) и оценочные функции /.

Во второй главе представлен разработанный автором ^-кластерный приближенный алгоритм для решения задачи Штейнера на ориентированных графах.

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

1. В графе й строится опорное дерево, являющееся некоторым деревом Штейнера для заданного множества терминалов. Для построения используется приведенный выше алгоритм Такахаши.

Рисунок 1 - Частичные поддеревья Штейнера

2. На основании опорного дерева строится разбиение на кластеры. Находится самая дальняя от начальной вершины Ь вершина ветвления опорного дерева, такая, что число терминалов в поддереве, ограниченном ей, больше к (это условие гарантирует, что кластеров будет не более к). Соответствующее ей поддерево удаляется из опорного дерева. Такие поддеревья выделяются до тех пор, пока опорное дерево не становится пустым. Затем на основании выделенных поддеревьев строится множество кластеров С.

3. На каждом из кластеров С € С определим индуцированную задачу Штейнера следующим образом: индуцированное множество терминалов Е(С) = ЕГ)М(С), начальная вершина Ь(С) — вершина разветвлении, на основании которой был построен кластер С. Если ^(С)! ^ к, то решаем поставленную задачу на подграфе методом динамического программирования, иначе вновь разбиваем полученный подграф на кластеры.

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

кроме начальной. Поставленная задача решается методом динамического программировании.

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

Также в данной главе доказывается теорема о вычислительной сложности этого алгоритма, которая составляет 0{2кЫ1о£т), где I — число терминалов, п — число дуг, т — число вершин.

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

Напомним, граф называется евклидовым, если его вершинам соответствуют некоторые точки п евклидовом пространстве, а длина дуги равна ев-клидовому расстоянию между точками.

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

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

В главе приведен общий приближенный алгоритм решения, основанный на методе динамического программирования, для произвольного иод-множества всего множества терминальных подмножеств. Кроме того, представлены три способа построения ограниченного множества терминальных подмножеств:

1. Наивный метод. Будем называть множество 3 С Е Ъ-допустимым,, если:

$т.' € Е \ .7 : Э?т?.ь т2 е .7 : /(т^пз) = ¿.{тлЪт') + ¿(тфт'). (8)

Тогда определим множество терминальных подмножеств, получаемое наивным методом построения, как совокупность всевозможных Ь-допустимых подмножеств Е.

Рисунок 2 - Упорядочивание вершин в наивном методе

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

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

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

И

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

Среди заслуживающих упоминания программных особенностей отметим следующие:

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

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

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

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

В главе представлены параллельные версии всех алгоритмов, выполненные с помощью библиотеки Microsoft Task Parallel Library, которые дают

возможность значительно уменьшить время решения задач на компьютерах

12

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

В пятой главе приведены результаты экспериментальных исследований представленных методов и их различных реализаций, производится их сравнение с другими известными приближенными методами решения задачи Штейнера, а также друг с другом. Для исследований использовались как известные наборы задач из библиотеки 81ешЫЬ [8], так и сгенерированые автором наборы задач.

В том числе, произведены следующие эксперименты:

1. Сравнение быстродействия пяти различных реализаций приоритетных очередей в рамках применения алгоритма динамического программирования на наборе из 200 задач с \М\ е [80,040], е [120,204480], |Т| € [6,17] из библиотеки 31ешЫЬ. Наилучшие результаты достигнуты при использовании приоритетных очередей на основе ведерной структуры.

2. Сравнение точности решения алгоритма ¿-кластерной оптимизации с другими известными алгоритмами (алгоритмом Такахаши, алгоритмом Зеликовского [10]) на наборе из 400 задач с |Л/| 6 [80,640], € [120,204480], \Т\ € [0,160] из библиотеки 81ешЫЬ. Коэффициент аппроксимации, достигаемый с помощью /¡.'-кластерного метода оказался в среднем равным 1.05, что меньше, чем полученный в алгоритме Такахаши и алгоритме Зеликовского.

3. Сравнение методов генерации множества терминальных подмножеств на наборе из 50 сгенерированных автором задач с \М\ — 160, £ [1100,7700], |Т| € [10,50]. Решения, получаемые с помощью наивного метода и метода «концентрических окружностей» на 15% и 40 % хуже в сравнении с решением, полученным обобщенным методом.

4. Сравнение точности решения приближенного алгоритма 5* с вышеприведенными алгоритмами, а также с алгоритмом ¿-кластерной онтимиза-

13

ции на сгенерированным автором наборе из 150 задач с|М| Є [160,640], \N\ є [2371,204156], \Т\ Є [20,120]. Точность решений, получаемых методом 5*, оказалась лучшей среди участвовавших в сравнении методов.

[1 160,50 160,60

Число вершин, терминалов

Рисунок 3 - Сравнение быстродействия параллельной и последовательной реализаций метода

5. Проведено сравнение быстродействия последовательных и параллельных версий алгоритмов динамического программирования, ¿¡-кластерной оптимизации и приближенного алгоритма 5* на представленных ранее наборах задач. В результате исследований отмечено увеличение быстродействия до 6 раз на восьмиядерном процессоре. Диаграмма, отображающая отношение среднего увеличения быстродействия в зависимости от параметров задачи для метода 5*, представлена на рисунке 3.

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

Публикации автора по теме диссертации

[1] Ейбоженко Д. А. fc-кластерный метод для задачи Штейнера на графах. // Материалы российской конференции «Дискретная оптимизация и исследование операций», Новосибирск: Институт математики им. С. J1. Соболева, 2010, с. 159.

[2] Романовский И. В., Ейбоженко Д. А. Модификации метода динамического программирования в задачах Штейнера на ориентированных графах. / / Компьютерные инструменты в образовании. Вып. 5, 2010, с. 22-28.

[3] Ейбоженко Д. А. Алгоритм fc-кластерной оптимизации для задачи Штейнера на ориентированных графах. // Вестник СПбГУ. Сер. 10. Прикладная математика, информатика, процессы управления. Вып. 2, 2011, с. 29-39.

[4] Ейбоженко Д. А. Эвристический алгоритм S" для задачи Штейнера на ориентированных евклидовых графах. //' Материалы второй межвузовской научной конференции по проблемам информатики СПИСОК-2011, Санкт-Петербург: СПбГУ, 2011, с. 223-224.

[5] Ейбоженко Д. А. Задача Штейнера на ориентированных графах. // Материалы международной конференции «Математика, экономика, менеджмент: 100 лет со дня рождения JI. В. Канторовича» Санкт-Петербург: СПбГУ, 2012, с. 41.

Цитируемая литература

[6] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. /Пер. с англ. Е.В.Левнера, М. А. Фрумкина, под ред. А. А. Фридмана, М.: Мир, 1982. 416 с.

[7] Hart Р.Е., Nilsson N.J., Raphaël В. A formai basis for the heuristic détermination of minimum cost paths. // IEEE transactions on Systems Science and Cybernetics, Vol. 4, 1968, P. 100-107.

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

[9] Takahashi H., Matsuyama A. An Approximate Solution for the Steint. Problem In Graphs // Math. Japonica, 1980, Vol. 24, N. 6, P. 573-577.

[10] Zelikovsky A. 11/6-approximation algorithm for the Steiner problerr on graphs. // Proc. Fourth Czechoslovakian Symposium on Combinatorics Graphs, and Complexity. 1992, P. 351-354.

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

[12] H. Sutter The Free Lunch Is Over: A Fundamental Turn Towarc Concurrency in Software. // Dr. Dobb's Journal, 30(3), March 2005.

Подписано к печати 06.04.12. Формат 60 х 84 % . Бумага офсетная. Гарнитура Тайме. Печать цифровая. Печ. л. 1,00. Тираж 100 экз. Заказ 5422.

Отпечатано в Отделе оперативной полиграфии химического факультета СПбГУ 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 26 Тел.: (812) 428-4043,428-6919

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ МАТЕМАТИКО-МЕХАНИЧЕСКИЙ ФАКУЛЬТЕТ

61 12-1/1100

Ейбоженко Дмитрий Анатольевич

Приближенные методы решения задачи Штейнера на ориентированных графах

Специальность 05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель: д.ф-м.н. проф. Романовский И. В.

Санкт-Петербург 2012

Содержание

1. Введение 4

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6.6. Метод 5* ..........................105

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

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')) будет называться графом, ограниченным, множеством М'.

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

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

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

Для произвольного графа