Одним из наиболее известных и распространенных алгоритмов синтеза КСД с ограничениями является алгоритм Исау—Вильямса, известный под названием CNDP. Предположим, что рц обработки данных расположен в пункте х1, а пропускная способность всех ветвей одинакова и равны d.
Пусть первоначально имеется некоторое множество изолированных узлов X — {x1,… хn}. Для каждого узла i вычисляем стоимость его подключения к РЦ сi1 = vi, а также стоимость связи сij двух узлов i и j между собой. В общем случае cij = cij(hi), где hi — поток информации в узле i. Вычисляем экономию от подключения узла i к j вместо подключения его к РЦ: Eij = cij — ci1 = cij — vi. Находим такую пару (i*, j*), для которой Ei*j* = min Еij при условии, что hi*-hj*≤d. Если Ei*j* < 0, то вводим ветвь (i*, j*) и объединяем два узла xi* и xj* в один: Xi*H = xi*⋃xj*, при этом определяем новое значение потока информации Нi* = hi*. Пусть проведено k итераций и построено k обобщенных узлов (подграфов) X1 Х2, ... , Хк и пусть Hk = H(Xk) — суммарный информационный поток всех узлов, входящих в Xk.
Опишем (k+1)-ю итерацию. Выбираем произвольный изолированный подграф Xi. Находим произвольный подграф Xj и проверяем возможность ввода ребра (i, j): Hi + Hj ≤. d.
Если условие выполняется, то вычисляем Eij = cij(Hi) - vi.
Находим такую пару (i*, j*), для которой Ei*j* =; min Еij.
Если Ei*j* < 0, то объединяем пару подграфов Xi и Xj в один: Xi* = Xj* = Xi* ⋃Xj*, в противном случае подключаем все оставшиеся изолированные подграфы напрямую к РЦ, и конец работы алгоритма.
Алгоритм Краскала отдельно рассматривать не стоит, так как он аналогичен уже описанному. Отличительной особенность является то, что в начале все узлы изолированы, на каждом шаге отыскивают наименьшую по стоимости допустимую линию связи различных узлов.
Определяют полярные координаты (аi, ri) каждого терминала относительно РЦ. Терминалы (узлы) рассматривают в последовательности, соответствующей возрастанию угла полярных координат ai, так что а1 ≤ а2 ≤ ...≤ ап. Строят минимальную по стоимости древовидную сеть терминалов х1, х2,…хк и РЦ, где х1, х2,…хкудовлетворяют ограничениям, но при добавлении хк+1 к многопунктовой (многоточечной) сети ограничения нарушаются. Вышеуказанную процедуру, начиная с хк+1 повторяют до тех пор, пока все терминалы не будут включены в дерево.
Как следует из описания, все перечисленные алгоритмы близки друг к другу и различаются только очередностью объединения компонент, которая обеспечивается назначением соответствующих весов значимости этим компонентам (узлам).
Для каждого терминала (узла) хiподсчитывают выигрыш Ei как разность Еi= с’ij — сij, где Xj— ближайший к хiподграф; X’j— следующий по порядку ближайший к хiподграф.
Текущая итерация алгоритма заключается в том, что находится i* такой, что Ei*= maxЕi. Проводится проверка по ограничению: если оно выполняется, то хiподключается к ближайшему узлу хj. В результате образуется некоторый подграф Хi = xi⋃xj. Стоимость связи между двумя сегментами определяется как стоимость самой дешевой связи между двумя терминалами (узлами), принадлежащими разным подграфам. Если связь (i, j) нарушает ограничение по ПС, то сij= ∞. Когда все терминалы оказываются подключенными к РЦ, конец работы алгоритма.
В результате анализа известных алгоритмов синтеза КСД (алгоритмы Прима, Исау — Вильямса, Краскала, Шарма и т. д.) предложен так называемый унифицированный алгоритм синтеза многопунктовых сетей, из которого можно получить как частный случай любой из известных алгоритмов синтеза, приписав определенные значения некоторым формальным параметрам. Для формального описания алгоритма введем следующие обозначения: vi — вес терминала i; Хi— подграф (набор терминалов), содержащий терминал i; (i, j) — линия, соединяющая терминалы i и j; Еij— экономия, соответствующая линии (i, j); cij— стоимость связи (i, j); N — число терминалов.
Шаг 0. 1. Задаем начальные значения величины vi для i = 1,2…N, используя соответствующее правило из таблицы 2.1.
2.Устанавливаем Хi = {i}, i = 1,2…N.
3.Определяем Еij =cij-vi для (i, j), если сij существует и терминалы (узлы) i и j не объединены.
Таблица 2.1 – Инициализация и коррекция весов
| Алгоритм | Инициализация весов | Коррекция весов при вводе связи (i, j) |
| Прима | vi = 0, i = 1 vi = - ∞, i = 2,…,N | 0 -> vj, vi = 0 |
| Исау-Вильямса | vi = ci1, i = 2,N | vi = vj |
| Краскала | vi = 0, i = 1,N | Нет |
| Фогеля | v*i = bi - ai | v**i = bi - ai |
* Для определения bi, аi см. описание алгоритма.
** Величины bi, аi определяются с учетом вновь введенных компонент.
Шаг 1. Определяем Еi*j* = minЕij. Если Еi*j* = ∞, то заканчиваем поиск, в противном случае переходим к шагу 2.
Шаг 2. Оцениваем выполнение ограничений для Хi* ⋃Xj* (объединения подграфов). Если любое из них нарушено (например, ограничение, что Нi+ Hj < d), то устанавливаем Еi*j* = ∞ и возвращаемся к шагу 1. В противном случае переходим к шагу 3.
Шаг 3. 1. Вводим ветвь (i, j).
2.Изменяем величины vi для i = 1,2…N(таблица 1 и примечание 4).
3.Еij =cij-vi для тех i, для которых vi изменено.
4.Сформируем новый подграф Хi* ⋃Xj*. Повторно пересчитываем ограничения и возвращаемся к шагу 1.
Примечания:
1.Для простоты изложения принимаем, что центр обработки данных находится в пункте 1.
2. Правила оценки весов viиспользуют для назначения терминалам весов значимости. Они приписывают им числовые значения, соответствующие степени желаемого использования линий, исходящих из каждого терминала.
3. Величина Еijможет быть определена только в том случае, если имеется ветвь (ij) и компоненты, содержащие терминалы iи j, можно соединить без нарушения каких бы то ни было ограничений. В противном случае значение Еijявляется неопределенным и для удобства расчетов полагаем Еij= ∞.
4. Значения viнеобходимо изменять не всегда, например, в алгоритме Краскала.
Связь между унифицированным алгоритмом и частными алгоритмами синтеза КСД отображается в таблице 1, где указаны решающие правила для вычисления начальных весов vi и их коррекция при вводе связи (i, j). Меняя правило задания и коррекции весов vi, можно получить любой из алгоритмов, причем одни правила во многих случаях дают лучшие результаты, чем другие. Однако пока не найдено такое универсальное правило, которое бы давало наилучшие результаты во всех случаях. Поэтому применяют параметрический способ определения весов. Рассмотрим один из таких способов. Запишем веса узлов в виде
vt= a(bci0 + (l — b)ci2),
где ci0, ci2 — стоимости соединения терминала i с центральным узлом и с его ближайшим соседним терминалом соответственно; а и b— некоторые константы, причем а ≥ 0, 0 ≤ b ≤ 1. При а = 0 получаем алгоритм Краскала; при а = b = 1 — алгоритм Исау — Вильямса; при а = 1, b = 0 — алгоритм Фогеля. Наконец, придавая а и b некоторые промежуточные значения, можем получить одновременно свойства всех вышеперечисленных алгоритмов.
На практике обычно параметрам а и b придают некоторые начальные значения и затем, варьируя их по очереди и оценивая получаемые результаты, последовательно приближаются к наилучшему. Такой способ позволяет получить результаты на 1—5 % лучше, чем при использовании алгоритмов Исау— Вильямса и Фогеля. Указанный способ параметризации можно применять для одновременного решения задач группирования и размещения терминалов, если в выражении для vi под сi0 понимать стоимость соединения терминала i с ближайшим центральным узлом. При этом никакого предварительного разбиения терминалов на группы не производится, а оно выполняется автоматически в процессе работы алгоритма.
Рассмотрим эффективность реализации унифицированного алгоритма синтеза КСД. Сложность алгоритма — время вычислений и необходимый объем памяти — зависит от размерности графа N. В общем случае граф должен быть полным, что требует просмотра всех пар узлов. Однако при большом количестве терминалов можно без значительного снижения точности результатов решать задачу с помощью разреженного графа, в котором каждый терминал связан лишь с некоторым ограниченным числом соседних терминалов. Например, в сети с 40 узлами достаточно рассматривать соединения каждого терминала с пятью соседними. Дальнейшее увеличение числа терминалов К лишь незначительно улучшает результаты. Для сети терминалов, однородно распределенных вокруг центрального узла, можно игнорировать около 75 % возможных соединений. Для быстрой оценки приближенного значения К всю область, содержащую терминалы, разбивают на прямоугольники, в пределах каждого из которых находят К ближайших соседей заданного терминала. Благодаря такому правилу число операций для повторного вычисления Eij при включении новой ветви в дерево можно снизить с N (N — 1)/2 до N х К. Кроме того, учитывая, что Еij =vi-cij, где cij— константа, пересчет Еijможно свести к пересчету vi, т. е. вместо N х К повторных вычислений Eij достаточно пересчитать N раз значение vi.
В общем случае сложность алгоритма оценивается выражением: AN2 + BKN + CKN log2K, где А ,В и С — константы. При этом предполагается, что программа обеспечивает возможность реализации любого правила v. Однако, если правило v таково, что не требуется пересчет vi для каждого терминала, то членом AN2 можно пренебречь. Для многих практических целей сложность алгоритма имеет вид BKN + CKN log2К. Время работы ЭВМ и требуемый объем оперативной памяти при реализации алгоритма экспериментально оценены в сетях, содержащих 20, 40, 60, 80, 120, 200 узлов при учете только пяти соседних терминалов, использовании правила изменения v по алгоритму Исау — Вильямса и суммарном графике в ветви, ограниченном значением Н ≤ N/4.