Синтез сети минимальной стоимости

Ситуация, в которой некоторое множество точек необходимо соединить так, чтобы каждая пара точек получилась связанной (непосредственно или через другие точки), а общая весовая характеристика связей оказалась минимальной, порождает задачу синтеза сети минимальной стоимости. Например, имеется ряд точек, в которых могут быть расположены пункты телекоммуникационной сети. Известны расстояния между парами точек и стоимость организации одного километра линии связи. Необходимо определить совокупность линий связи, обеспечивающих связность всех пунктов сети и ее минимальную стоимость. Из теории графов и сетей известно, что решением поставленной задачи является сеть с топологией типа "дерево".

О п р е д е л е н и е. Связный граф (связывающая сеть) называется деревом, если в нем отсутствуют циклы.

Говорят, что граф содержит циклы, если в нем можно отыскать замкнутые контуры. Отсутствие циклов определяет особенность графа типа дерево, которая состоит в том, что между любой парой его вершин существует лишь один единственный связывающий их путь, т.е. параметр связности h=1. Количество ребер в дереве всегда на единицу меньше числа его вершин.

О п р е д е л е н и е. Дерево, в которое включены все вершины, называется покрывающим.

Математически задача синтеза сети минимальной стоимости формулируется следующим образом.

Пусть задан неориентированный граф G(N,V), где множество вершин N соответствует множеству пунктов сети, общее число которых равно n, а множество ребер V – расстояниям { l_ij } между парами пунктов. Известна стоимость С_ij организации 1 километра линии связи между пунктами i и j.

Необходимо найти некоторое покрывающее дерево G'(N,V'), для которого достигается минимум целевой функции:

Для решения поставленной задачи существует ряд эффективных алгоритмов. Приведем один из них, который известен как алгоритм Прима и носящий имя автора. Алгоритм реализуется путем присвоения пометок вершинам, которые вводятся в искомый граф G'(N,V'), и последовательного введения в него, наиболее коротких ребер, общее количество которых не должно превышать (n- 1) и обеспечивать связность между всеми n вершинами покрывающего дерева.

Пошаговая форма алгоритма имеет следующий вид:

Шаг 0. Искомая сеть G' (N,V') в исходном состоянии содержит n вершин и не содержит ребер. Выбирается одна произвольная вершина i и помечается как " выбранная ". Остальные (n- 1) вершин помечаются как " невыбранные ".

Шаг 1. Отыскивается ребро (i, j), принадлежащее G (N, V) с минимальным весом, у которого вершина i принадлежит подмножеству "выбранных " вершин, а вершина j к подмножеству " невыбранных " вершин.

Шаг 2. Ребро (i, j) включается в искомую сеть G'(N,V'), а вершина j исключается из подмножества " невыбранных " вершин и включается в подмножество "выбранных " вершин. Если подмножество " невыбранных " вершин оказалось пустым – конец работы алгоритма. В противном случае – переход к шагу 1.

Проиллюстрируем работу алгоритма Прима на примере. Пусть задано семь пунктов сети, расстояния между которыми сведены в матрицу L = ||l_ij||, а именно:

L =	0 10 5 12 9 3 9 10 0 7 2 8 4 6 5 7 0 3 1 5 11 12 2 3 0 10 15 10 9 8 1 10 0 12 9 3 4 5 15 12 0 17 9 6 11 10 9 17 0

На шаге 0 искомый граф G' (N,V') содержит 6 вершин и не содержит ребер. Выберем вершину 3 и пометим ее как ² выбранную ² (рис. 4).

На шаге 1 выбираем ребро (l₃₅) как ребро с наименьшим весом, у которого вершина i = 3 принадлежит подмножеству " выбранных " вершин (оно пока содержит всего лишь одну вершину 3), а вершина j = 5 - подмножеству " невыбранных " вершин (сейчас это все остальные вершины). На шаге 2 ребро l₃₅ вводится в искомый граф G', а вершина 5 включается в подмножество " выбранных " вершин (рис. 5

Поскольку подмножество " невыбранных " вершин не пустое, повторяем шаг 1. Для этого отыскиваем ребро минимального веса, перебирая сочетания каждой пары " выбранной " и " невыбранной " вершин. Таким оказалось ребро l₃₄ (рис. 6). Оно вводится в граф G ', а вершина 4 становится " выбранной ".

Рисунок 4 Рисунок 5

Рисунок 6 Рисунок 7

Следующими выбираются ребра: l₂₆ (рис. 7); l₃₁ (рис. 8); l₂₇ (рис. 9). На этом работа алгоритма заканчивается, так как все вершины оказались помеченными как " выбранные " (т. е. подмножество " невыбранных " вершин – оказалось пустым подмножеством).

Рисунок 10

Получен искомый граф G' (N, V'), представляющий собой покрывающее дерево, так как он включает все вершины, содержит число ребер на единицу меньшее числа вершин (n = 7, v = 6) и обеспечивает связность каждой пары вершин.

Дата добавления: 2014-01-07