Методы и алгоритмы автоматизированного проектирования проводных телекоммуникационных сетей минимальной стоимости

• Автор: Читаев, Илья Владимирович
• Шифр специальности: 05.13.12
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Рязань
• Количество страниц: 201 с. : ил.

СОДЕРЖАНИЕ

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

Введение
Глава 1. Анализ существующих методов и алгоритмов построения телекоммуникационных сетей минимальной стоимости.

1.1 Описание алгоритмов построения сетей минимальной стоимости

1.1.1 Алгоритмы построения минимальных остовных

деревьев

1.1.2 Алгоритмы построения деревьев Штейнера.

1.1.3 Алгоритмы построения минимальных гамильтоновых контуров

1.1.4 Анализ предложенных алгоритмов

1.2 Алгоритмы определения маршрута трассы

1.2.1 Конструкторская трассировка.
V 1.2.2 Строительная трассировка.
1.2.3 Анализ алгоритмов трассировки.
1.3 Анализ близких задач.
Выводы по первой главе.
Глава 2. Разработка математического аппарата соединения двух точек на взвешенной плоскости.
2.1 Соединение точек, расположенных в соседних полуплоскостях
с различной стоимостью прокладки.
2.1.1 Решение уравнений третьей степени метод Кардано
2.1.2 Решение уравнений четвертой степени метод Феррари.
2.2 Соединение точек, расположенных в полуплоскости с высокой
ф стоимостью прокладки.
2.3 Соединение точек, расположенных в соседних областях
взвешенной плоскости, разделенных произвольной кривой
2.4 Соединение точек, расположенных в удаленных областях
взвешенной плоскости, границами которых являются параллельные прямые.
2.5 Соединение точек, расположенных в удаленных областях взвешенной плоскости, границами которых являются две
. непараллельные прямые.
2.6 Соединение точек, расположенных в соседних областях
взвешенной плоскости, разделенных тремя прямыми,
сходящимися в одной точке.
2.7 Соединение точек, расположенных в соседних областях
взвешенной плоскости, разделенных двумя прямыми,
сходящимися в одной точке.
Выводы по второй главе
Глава 3. Разработка алгоритмов соединения точек на взвешенной плоскости и объединение п точек в сеть заданной топологии
Ч 3.1 Разработка алгоритма соединения двух точек на взвешенной
плоскости.
3.1.1 Предварительный этап соединения двух точек на взвешенной плоскости.
Вариант 1
Вариант 2
Вариант 3
3.1.2 Улучшение пути, соединяющего две точки на взвешенной плоскости
3.2 Разработка алгоритма объединения точек на взвешенной плоскости в сеть заданной топологии.
3.3 Разработка алгоритма построения телекоммуникационной й я
сети заданной топологии без вычисления всех расстоянии между
каждой парой узлов на взвешенной плоскости
Выводы по третьей главе
Глава 4. Экспериментальная проверка работы разработанных
алгоритмов
4.1 Разработка автоматизированной системы построения сети заданной топологии на взвешенной плоскости.
4.2 Описание вычислительного эксперимента. ИЗ
4.3 Анализ полученных результатов
Выводы по четвертой главе
Заключение.
Библиографический список
Приложения
Приложение 1. Листинг программных модулей
Приложение 2. Копии актов о внедрении

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность


Таким образом, на каждом шаге строящееся множество состоит из одной или более нетривиальных компонент, каждая из которых является подграфом некоторого минимального остова. В последнее время (с -х годов) было предложено много различных подходов для оптимизации и улучшения скорости работы известных алгоритмов [,,]. Одним из таких подходов является использование при построении МОД диаграмм Вороного [,,]. МОД можно улучшить, вводя него дополнительные вершины и перестраивая связи между нами [8]. Полученное после введения дополнительных вершин дерево называют деревом Штейнера (рисунок 1. Рисунок 1. Изучение минимальных сетей Штейнера, т. Штейнера или одномерной проблемы Плато, представляет собой активно развивающуюся область современной математики, стоящей на стыке дифференциальной и вычислительной геометрии, топологии, комбинаторики и вариационного исчисления []. Впервые интерес к подобной задаче возник задолго до Штейнера. В своем простейшем варианте задача была поставлена Ферма, а именно, он предложил найти на плоскости точку S, сумма расстояний от которой до трех фиксированных точек А, В и С наименьшая. Торричелли обнаружил следующее геометрическое решение. Построим на сторонах треугольника ABC правильные треугольники ABC', ВСА' и САВ', каждый из которых пересекается с ABC лишь по соответствующей стороне. Опишем окружность вокруг каждого из этих трех правильных треугольников. Тогда эти три окружности пересекутся в одной точке, которая и является решением задачи Ферма. Эта точка часто называется точкой Торричелли. Кавальери выяснил, что точка Торричелли обладает следующим важным свойством: углы между отрезками, соединяющими вершины треугольника ABC с точкой Торричелли, равны между собой и поэтому равны 0е. Общая задача, охватывающая произвольное количество точек, была предложена в веке математиком Якобом Штейнером. Задача нахождения Евклидового дерева Штейнера», а оптимальные решения этой задачи называются минимальными деревьями Штейнера. Самыми первыми алгоритмами для решения общей задачи в графах являются алгоритм Хакими (Hakimi) [], основанный на переборе всех стягивающих деревьев, и алгоритм динамического программирования Дрейфуса (Dreyfus) и Вагнера (Wagner) []. Более современные алгоритмы используют формулировки целочисленного программирования и решают задачу с помощью метода “расширяй и урезай” (brunch and cut) []. Еще один точный алгоритм построения на плоскости локально минимальной сети данного топологического типа с данной границей был предложен Мелзаком для случая деревьев []. Этот алгоритм за время, экспоненциально зависящее от числа граничных точек, или строил требуемое минимальное дерево, или получал ответ, что такого дерева не существует. Однако, т. Штейнера является NP-сложной, время работы данных алгоритмов экспоненциально зависит от числа исходных точек, на которых строится минимальная сеть. Поэтому с увеличением числа граничных точек точные алгоритмы теряют свою эффективность. В связи с этим большое внимание уделяется второму подходу к решению данной проблемы, а именно, к созданию приближенных алгоритмов. К приближенным алгоритмам построения дерева Штейнера относятся алгоритм Вайнера-Зайцева-Лившица [8] и эвристический алгоритм, разработанный Псиолом [,]. Топология «дерево» является минимальной связывающей топологией, однако, она, в свою очередь, является и самой ненадежной []. В связи с этим возникает задача построения более надежной топологии телекоммуникационной сети. На языке теории графов минимальной сетью со степенью связности 2 («кольцо») является гамильтонов контур (рисунок 2. Решение задачи поиска гамильтонова контура минимальной длины на графе сводится к решению задачи о коммивояжере. Задача коммивояжера была поставлена в году и является одной из знаменитых задач теории комбинаторики [8,]. Постановка задачи следующая. Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,4,3п и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?