Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
Топ:
Генеалогическое древо Султанов Османской империи: Османские правители, вначале, будучи еще бейлербеями Анатолии, женились на дочерях византийских императоров...
Когда производится ограждение поезда, остановившегося на перегоне: Во всех случаях немедленно должно быть ограждено место препятствия для движения поездов на смежном пути двухпутного...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Интересное:
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Дисциплины:
2017-10-16 | 483 |
5.00
из
|
Заказать работу |
|
|
Пусть задан неориентированный простой взвешенный граф в котором множество вершин является объединением двух множеств Вершины множества будем называть терминалами, а вершины из множества – промежуточными вершинами. Каждому ребру , приписана «длина» . Требуется связать все вершины множества деревом минимальной длины, которое называется минимальным деревом Штейнера (МДШ). При этом в искомое дерево могут войти промежуточные вершины из множества .
Рисунок-4.2. Пример дерева Штейнера на графе
На рис. 4.2 пунктирными линиями изображены ребра графа , которые соединяют терминалы – закрашенные вершины и промежуточные (не закрашенные) вершины. Сплошными линиями показано дерево Штейнера, в которое вошли три промежуточные вершины.
Для МДШ на плоскости с евклидовой метрикой справедливы следующие свойства.
Свойство 4.1. Точка Штейнера имеет степень 3.
Свойство 4.2. Если вершина имеет степень 3 в МДШ, то угол между любыми двумя ребрами, инцидентными , равен 120°.
Свойство 4.3. Число точек Штейнера в МДШ равно .
Известно, что задача Штейнера на графах (а также геометрическая задача Штейнера) NP-трудна в сильном смысле [4], поэтому на практике используются различные приближенные алгоритмы для построения МДШ.
Приближенные алгоритмы
Очевидно, МОД является приближенным решением задачи Штейнера. При этом для метрического случая, когда точки (вершины) расположены на плоскости, отношение ,
где – вес минимального остовного дерева, а – минимальная длина дерева Штейнера. Алгоритм Прима (Краскала) строит 2-приближенное решение задачи Штейнера с полиномиальной трудоемкостью.
Известен более сильный результат: , для метрической задачи с евклидовой метрикой. Предложено также несколько алгоритмов, которые строят 2-приближенное решение задачи Штейнера на произвольных графах. Например, достаточно найти кратчайшие пути между каждой парой вершин графа, перейти к вспомогательному графу без промежуточных вершин с длинами ребер, равными длинам кратчайших путей, и построить МОД. Это и будет 2-приближенное решение для исходной задачи Штейнера.
|
Опубликован ряд работ, в которых предложены алгоритмы с меньшей оценкой точности, например, алгоритм строящий 1.55-приближенное решение для точек, расположенных на плоскости, расстояния между которыми задаются прямоугольной (манхэттеновской) метрикой [9]. В этом случае дерево Штейнера состоит из множества вертикальных и горизонтальных отрезков, соединяющих терминалы и промежуточные точки. Однозначно определяется минимальный прямоугольник, в котором находятся все терминалы, и его стороны параллельны осям (прямоугольник ABCD на рис. 3.3). Очевидно, все ребра МДШ не выходят за пределы этого прямоугольника. В 1966 г. Ханан показал [10], что существует МДШ, в которое входят только узлы решетки, полученной от пересечения горизонтальных и вертикальных прямых, проходящих через терминалы, – решетка Ханана (рис. 3.3).
Рисунок-4.3. Минимальное дерево Штейнера (жирные линии) на решетке Ханана
В 1976 г. Хванг [11] показал, что МОД является 3/2-приближен-ным решением. В 1992 г. Зеликовский [12] разработал алгоритм построения прямоугольного дерева Штейнера с оценкой точности 11/8, первый эвристический алгоритм, который строит решение лучше МОД.
|
|
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!