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

• Автор: Ейбоженко, Дмитрий Анатольевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Санкт-Петербург
• Количество страниц: 119 с. : ил.

Содержание
1. Введение
1.1. Цели и задачи
1.2. Постановки задачи Штейнера
1.3. Применение
1.3.1. УЬБЬпроектирование
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. Приближенный метод в* для задачи Штейнера на евклидовых графах
4.1. Алгоритм А* поиска кратчайшего пути
4.2. Задача Штейнера на концентрических окружностях
4.3. Алгоритм У* на евклидовых графах
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* на евклидовых графах
5.3. Параллелизация алгоритмов
5.3.1. Параллелизация точного алгоритма решения

5.3.2. Параллелизация алгоритма -кластерной оптимизации
5.3.3. Параллелизация алгоритма аппроксимации 5**
6. Вычислительные результаты
6.1. Сравнение эффективности структур, реализующих приоритетную очередь
6.2. Сравнение эффективности -кластерного метода с другими известными
6.3. Сравнение эффективности метода 5* с другими известными
6.4. Сравнение быстродействия однопоточных и параллельных реализаций методов
6.4.1. Метод динамического программирования
6.5. Метод кластерной оптимизации
6.6. Метод Я*
7. Результаты и выводы

3.1. Определение кластеров в графе
Нам необходимо знать расстояния от начальной вершины Ь до всех остальных вершин в графе. Воспользуемся алгоритмом Дейкстры.
Прежде чем искать кластеры на графе С, построим опорное дерево, ветвлением которого будем руководствоваться при определении кластеров.
3.1.1. Построение опорного дерева
Для построения опорного дерева воспользуемся алгоритмом нахождения приближенного минимального дерева Штейнера на графах, предложенным Такахаши и Мацуямой [55], уже рассматривавшимся в предыдущей главе (стр. 22). Он выглядит следующим образом:
а) В любой момент процесса построения имется подграф = (М*, ЛГ*), первоначально состоящий из единственной вершины Ъ. М* = {Ь}, ./V* = 0.
б) На каждом шаге найдем такую вершину е* Є Е М*, что
е*) = тт{с1(М*, е)еЄЕ М*}.
Тогда Те := ТзиР[М*,е*], где Р[М*,е*] - наименьший из всех возможных путей от вершин М* до е*.
В результате работы алгоритма получим некоторое дерево Штейнера. Способ его ветвления несет в себе информацию, необходимую для разбиения графа на кластеры. Будем компоновать подходящие ветви в отдельные кластеры, учитывая количество содержащихся в них терминалов.