Одним из наиболее известных и распространенных алгоритмов синтеза КСД с ограничениями является алгоритм Исау—Вильямса, известный под названием 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*, в противном случае подключаем все оставшиеся изолированные подграфы напрямую к РЦ, и конец работы алгоритма.

Алгоритм Краскала отдельно рассматривать не стоит, так как он аналогичен уже описанному. Отличительной особенность является то, что в начале все узлы изолированы, на каждом шаге отыскивают наименьшую по стоимости допустимую линию связи различных узлов.

2.2.3 Алгоритм Шарма

Определяют полярные координаты (аi, ri) каждого терминала относительно РЦ. Терминалы (узлы) рассматривают в последовательности, соответствующей возрастанию угла полярных координат ai, так что а1 ≤ а2 ≤ ...≤ ап. Строят минимальную по стоимости древовидную сеть терминалов х1, х2,…хк и РЦ, где х1, х2,…хкудовлетворяют ограничениям, но при добавлении хк+1 к многопунктовой (многоточечной) сети ограничения нарушаются. Вышеуказанную процедуру, начиная с хк+1 повторяют до тех пор, пока все терминалы не будут включены в дерево.

Как следует из описания, все перечисленные алгоритмы близки друг к другу и различаются только очередностью объединения компонент, которая обеспечивается назначением соответствующих весов значимости этим компонентам (узлам).

2.2.4 Алгоритм Фогеля (VАМ)

Для каждого терминала (узла) хiподсчитывают выигрыш Ei как разность Еi= с’ij — сij, где Xj— ближайший к хiподграф; X’j— следующий по порядку ближайший к хiподграф.

Текущая итерация алгоритма заключается в том, что находится i* такой, что Ei*= maxЕi. Проводится проверка по ограничению: если оно выполняется, то хiподключается к ближайшему узлу хj. В результате образуется некоторый подграф Хi = xi⋃xj. Стоимость связи между двумя сегментами определяется как стоимость самой дешевой связи между двумя терминалами (узлами), принадлежащими разным подграфам. Если связь (i, j) нарушает ограничение по ПС, то сij= ∞. Когда все терминалы оказываются подключенными к РЦ, конец работы алгоритма.

2.2.5 Унифицированный алгоритм синтеза КСД

В результате анализа известных алгоритмов синтеза КСД (алгоритмы Прима, Исау — Вильямса, Краскала, Шарма и т. д.) предложен так называемый унифицированный алгоритм синтеза многопунктовых сетей, из которого можно получить как частный случай любой из известных алгоритмов синтеза, приписав определенные значения некоторым формальным параметрам. Для формального описания алгоритма введем следующие обозначения: 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необходимо изменять не всегда, например, в алгоритме Краскала.