Читайте также:
|
Пусть дан связный, неориентированный граф с весами на ребрах G(V, E), в котором V — множество вершин (терминалов), а E — множество их возможных попарных соединений (ребер). Пусть для каждого ребра (u,v) однозначно определено некоторое вещественное число w(u,v) — его вес (длина или стоимость соединения). Задача поиска остовного дерева наименьшего веса графа G состоит в нахождении такого связного ациклического подграфа T ⊂ G, содержащего все вершины, что суммарный вес его ребер будет минимален.
Так как подграф T связен и не содержит циклов, он является деревом и называется остовным или покрывающим деревом. Остовное дерево T, у которого суммарный вес его ребер
w(T) = ∑(u,v)∈T w(u,v) минимален, называется минимальным остовным или минимальным покрывающим деревом.
Минимальное остовное дерево. Суммарный вес дерева равен 37. Это минимальное остовное дерево не уникально: удалением ребра (c,d) и добавлением ребра (a,b) получается новое минимальное остовное дерево.
Аналогичной задаче поиска остовного дерева наименьшего веса является задача Штейнера. Ее существенное отличие состоит в том, что допускается введение при необходимости новых вершин дерева, отличных от терминальных. Эти вершины называются точками Штейнера. Полученное в результате решение является деревом и называется минимальным деревом Штейнера. При этом деревом Штейнера называется любое дерево, покрывающее множество терминалов и, быть может, некоторые точки Штейнера.
Однако эффективных алгоритмов, дающих точное решение задачи Штейнера, не существует. Даже лучшие из алгоритмов, выполняющиеся на самых быстродействующих компьютерах, не в состоянии дать решение для большого множества заданных точек за реально приемлемое время. Более того, задача Штейнера принадлежит к классу задач, для которых, по мнению многих современных исследователей, эффективные алгоритмы, по-видимому, так никогда и не будут найдены. Несмотря на то, что формулировка этой задачи очень проста, её решения трудно поддаются анализу. Крошечное изменение геометрии задачи, кажущееся несущественным, может коренным образом изменить кратчайшую сеть, являющуюся её решением. Однако, часто для решения задача Штейнера используются алгоритмы поиска остовного дерева наименьшего веса, не допускающие введение точек, отличных от терминальных. Поэтому они находят лишь некоторые приближения точного решения. Наиболее известные алгоритмы: алгоритм Краскала, алгоритм Прима.
Алгоритм Прима
Пусть часть остовного дерева уже построена. Это утверждения всегда верно, так как в начале процесса вершина с которой начинается построение уже входит в дерево. Итак, если часть основного дерева уже есть, то множество вершин графа можно разделить на два подмножества: подмножество состоящее из вершин уже построенного остовного дерева и оставшихся вершин графа.
Очевидно, что среди ребер соединяющихся эти два множества существует ребро наименьшего веса. Доказывается, что минимальное дерево проходит через это ребро.
Приведем наиболее общую cхему алгоритма:
1) Множество остовных вершин – исходная веришны
2) Множество оставшихся - все вершины за исключением исходной.
3) Пока множество оставшихся не пусто:
a) Ищем ребро соединяющее множество остовных и множество оставшихся и имеющее наименьший вес.
b) Для найденного ребра, вершину принадлежащую множеству оставшихся:
§ Вычеркиваем из множества оставшихся.
§ Добавляем к множеству остовных.
Алгоритм Краскала
Искомые ребра соединяют вершины. Поэтому возможны две стратегии построения. Можно идти от вершин и для каждой из них искать минимальное ребро (как это сделано в алгоритме Прима) а можно для каждого ребра выяснять можно ли его включить в строящееся дерево. Алгоритм Краскала предлагает делать это следующим образом. Во-первых, ребра графа пронумеровываем в порядке возрастания весов. Затем для каждого ребра начиная с первого проверяем соединяет или нет оно две несвязные вершины, если да, то его можно включить в остовное дерево. Ясно, что если мы имеем V вершин, то работа алгоритма начинается с V несвязных компонент графа (пока из графа все ребра исключаем). Для того, чтобы их связать необходимо найти V-1 ребро.
Другими словами, алгоритм организует процесс роста компонент связности в процессе которого он объединяются друг с другом до тех пор пока не останется одна являющаяся конечным результатом (компонента связности - это такой связный подграф нашего графа, что добавление любой вершины ведет к потере связности).
Схема алгоритма:
1) Множество ребер H искомого остовного дерева полагаем пустым.
2) Формируем множество 
, элементами которого являются множества вершин, соответствующих компонентам исходного остовного леса (множество изолированных вершин исходного графа). Каждая такая компонента состоит из единственной вершины.
3) Сортируем множество ребер Е исходного графа по возрастанию весов и формируем очередь Q, элементами которого являются ребра исходного графа.
4) Если множество содержит более одного элемента (остовной лес состоит из нескольких компонент) и очередь Q не пуста, то переходим на шаг 5, иначе – на шаг 7.
5) Извлекаем из очереди Q ребро е. Если его концы принадлежат различным множествам 
, 
из , то переходим на шаг 6, иначе – отбрасываем ребро и переходим на шаг 4.
6) Обьединяем множества вершин , 
(полагая 
), удаляем множества , из множества и добавляем в множество W. Добавляем ребро е в множество Н. Возвращаемся на шаг 4.
7) Множество H есть множество ребер полученного остовного дерева.
Практическое применение алгоритмов решения задачи
· Разработка сетей (например, при разрешении проблемы о соединении n городов в единую телефонную сеть с минимальной суммарной стоимостью соединений). В более сложных формулировках задачи Штейнера можно учитывать такие факторы, как необходимость избежания определённых географических свойств местности, а также отыскивать кратчайшие соединения между узлами уже существующих сетей.
· Производство печатных плат. По аналогии с сетью: мы хотим соединить n контактов проводами с минимальной суммарной стоимостью.
· Минимальное остовное дерево может использоваться для визуализации многоаспектных, многомерных данных, например, для отображения их взаимосвязи (на картинке ниже продемонстрировано дерево схожести различных животных видов по размеру костей).
Минимальное остовное дерево может нагляднее представить эволюцию животных видов.
· С помощью него можно разбивать животных на группы и классы. Наука, и в частности биология, используют многомерные данные для группировки объектов, растений, животных. Минимальное остовное дерево позволяет разбивать их на взаимосвязанные классы, четко отслеживая близкие по строению и характеристикам группы.
Дата добавления: 2015-02-16; просмотров: 115 | Поможем написать вашу работу | Нарушение авторских прав |