Определение оптимального расположения районной АТС. Построение оптимальной трассировки магистрального фидера ретрансляционной сети

размещения АТС будет вершина а₅, что при построении абонентской сети обеспечит минимальный расход кабеля на линейные сооружения.

Этап 4. На данном этапе в графе G выделяются кратчайшие пути от медианной вершины а_x ко всем остальным вершинам. Именно эти пути соответствуют оптимальным трассам прокладки абонентского кабеля для подключения распределительных шкафов к районной АТС.

В теории графов указанная задача называется задачей построения дерева кратчайших путей для заданной вершины (в нашем случае это вершина а_x, где планируется установка АТС). Будем использовать алгоритм Дейкстры, который основан на следующем простом факте: если известен кратчайший путь из вершины а_s в вершину а_j и вершина а_k принадлежит этому пути, то кратчайший путь из а_s в а_k является частью указанного пути, который заканчивается в вершине а_j. Имея в виду приведенное соображение, формальное описание алгоритма Дейкстры включает в себя следующие действия:

A) Помечается исходная (корневая) вершина а_x и ей приписывается вес h_x=0. Остальные вершины первоначально не помечены и их веса h_i=¥ (i¹x). Для хранения номера последней из помеченных вершин предусматривается переменная k и на данном шаге k=x.

Б) Для каждой непомеченной вершины а_i делается попытка уменьшить ее вес: h_i=min{h_i, h_k+l_ki), где l_ki – вес ребра b_ki. Если после этих операций окажется, что h_i=¥ у всех непомеченных вершин а_i, то к ним отсутствуют пути из а_k и работа алгоритма заканчивается.

B) Пусть из всех h_i, относящихся к непомеченным вершинам, наименьшим является значение h_r. В этом случае необходимо: пометить вершину а_r и то ребро, ведущее к а_r, вес которого определяет значение h_r; значение r присвоить переменной k, т.е. теперь k=r. При наличии нескольких непомеченных вершин с одинаковым весом, величина которого является минимальной, произвольно выбирается одна из них и только для нее выполняются указанные операции.

Г) Если осталась хотя бы одна непомеченная вершина, то переходим к пункту Б, иначе процедура завершается и ее результатом является дерево кратчайших путей, которое образуется помеченными ребрами.

Построим дерево кратчайших путей для вершины а₄ графа, показанного на рисунке 2. Последовательность действий будет состоять из следующих операций:

1) Весам вершин приписываем начальные значения h₅=0 и h₁=h₂=h₃=h₄=h₆=h₇=h₈=¥. Помечаем вершину а₅ и ее номер присваиваем переменной k, т.е. k=5.

2) Для каждой непомеченной вершины пытаемся уменьшить вес:

h₁=min(h₁, h₅+l₅₁)=min(¥,0+¥)= ¥

h₂=min(h₂, h₅+l₅₂)=min(¥,0+2)=2

h₃=min(h₃, h₅+l₅₃)=min(¥,0+¥)=¥

h₄=min(h₄, h₅+l₅₄)=min(¥,0+3)=3

h₅=min(h₅, h₅+l₅₆)=min(¥,0+¥)= ¥

h₇=min(h₇, h₅+l₅₇)=min(¥,0+1)=1

h₈=min(h₈, h₅+l₅₈)=min(¥,0+¥)=¥

Из полученных величин h₇ является минимальной, поэтому помечаем вершину а₇ и ребро b₅₇, вес которого определяет значение h₇. Полагаем k=1.

3)       h₁=min(h₁, h₇+l₇₁)=min(¥,1+¥)=¥

h₂=min(h₂, h₇+l₇₂)=min(2,1+¥)=2

h₃=min(h₃, h₇+l₇₃)=min(¥,1+¥)=¥

h₄=min(h₄, h₇+l₇₄)=min(3,1+¥)=3

h₅=min(h₅, h₇+l₇₆)=min(¥,1+4)=5

h₈=min(h₈, h₇+l₇₈)=min(5,1+3)=4

Помечаем вершину а₂ и ребро b₇₂, определяющее величину h₂, (см. предыдущий шаг). Полагаем k=2.

4)       h₁=min(h₁, h₂+l₂₁)=min(¥,2+3)=5                   

h₂=min(h₃, h₂+l₂₃)=min(¥,2+2)=4

h₃=min(h₄, h₂+l₂₄)=min(3,2+¥)=3

h₅=min(h₆, h₂+l₂₆)=min(5,2+)¥=5

h₈=min(h₈, h₄+l₂₈)=min(,¥2+4)=6

Помечаем, вершину а₃ ребро b₂₄ определяющее величину h₃(см. шаг 2). После этого k=3

5)       h₁=min(h₁ h₃+l₄₁)=min(5,3+2)=5

h₂=min(h₃, h₃+l₄₃)=min(4,3+5)=4

h₆=min(h₆, h₃+l₄₆)=min(5,3+5)=5

h₈=min(h₈, h₃+l₄₈)=min(6,3+4)=6

Помечаем вершину a₂ и ребро b₄₃ вес которого определяет величину h₂ (см. шаг 3). Полагаем k=4

6)       h₃=min(h₃, h₁ +l₁₃)=min(4,5+5)=4

h₆=min(h₆, h₁+l₁₆)=min(5,5+5)= 5

h₈=min(h₈,h₁+l₁₈)=min(6,5+¥)=6

Помечаем вершину a₃ и ребро b₁₃, определяющее величину h₃ (см. шаг 3). Теперь k=4

7)       h₆=min(h₆, h₃+l₃₆)=min(5,4+5)=5

h₃=min(h₈, h₃+l₃₈)=min(6,4+6)=6

Помечаем вершину a₆, а также ребро b₃₆, которое определяет величину h₆ (см. шаг 4). В результате k=5

8)       h₈=min(h₈, h₆+l₆₈)=min(6,5+6)=6

Помечаем последнюю вершину а и ребро b₅₃, вес которого на шаге 5 определял величину h₃. На этом работа алгоритма заканчивается, а полученное дерево кратчайших путей показано на рисунке 3.

Рисунок 3

Этап 5. Для проводного радиовещания или кабельного телевидения задача построения на рассматриваемой территории города ретрансляционной сети с минимальной стоимостью сводится к выделению из графа G связного подграфа, включающего в себя все вершины из множества А и имеющего наименьшую суммарную длину ребер. Такой подграф всегда является деревом и называется также кратчайшим остовом графа G.

Для получения оптимальной структуры связывающей сети с минимальной общей длиной имеется алгоритм Прима-Краскала, который