Доставка любой диссертации в формате PDF и WORD за 499 руб. на e-mail - 20 мин. 800 000 наименований диссертаций и авторефератов. Все авторефераты диссертаций - БЕСПЛАТНО
Ейбоженко, Дмитрий Анатольевич
05.13.11
Кандидатская
2012
Санкт-Петербург
119 с. : ил.
Стоимость:
499 руб.
Содержание
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(М*, е)еЄЕ М*}.
Тогда Те := ТзиР[М*,е*], где Р[М*,е*] - наименьший из всех возможных путей от вершин М* до е*.
В результате работы алгоритма получим некоторое дерево Штейнера. Способ его ветвления несет в себе информацию, необходимую для разбиения графа на кластеры. Будем компоновать подходящие ветви в отдельные кластеры, учитывая количество содержащихся в них терминалов.
Название работы | Автор | Дата защиты |
---|---|---|
Разработка интеллектуальной системы для поддержки проектирования человеко-компьютерного взаимодействия в веб-приложениях | Бакаев, Максим Александрович | 2012 |
Доказательство свойств функциональных программ методом насыщения равенствами | Гречаник, Сергей Александрович | 2017 |
Алгоритмическое и программное обеспечение мультипроцессорных систем для распознавания графических образов на основе нейросетевого подхода | Тищенко, Игорь Петрович | 2009 |