где {} — множество висячих вершин на k-й итерации, то — искомое решение и конец работы алгоритма. В противном случае переходим на (k+2)-ю итерацию, переобозначив для всех висячих вершин

Весь процесс решения реализуется в виде некоторого дерева вариантов.

Как показывают проведенные исследования, реализация метода ветвей и границ для структурного синтеза сетей ЭВМ требует больших вычислительных затрат уже при числе возможных пунктов размещения РЦ т ≥ 40. Поэтому основная область применения точных методов для структурного синтеза и оптимизации — это проверка асимптотической эффективности приближенных методов и степени близости получаемых решений к оптимальным. В связи с этим основное внимание в книге уделено приближенным инженерным методам проектирования структур сетей ЭВМ и систем передачи данных, представляющих наибольший интерес для проектировщиков.

2.1.2 Алгоритм R-структур для синтеза абонентских СДО

Пусть необходимо решить задачу при определенных ограничениях. Следует определить пункты размещения РЦ и множество абонентов Хy , привязанных к РЦ.

Рассмотрим эвристический алгоритм решения указанной задачи (алгоритм R-структур), позволяющий за сравнительно небольшое число шагов найти субоптимальное решение. Алгоритм состоит из предварительного этапа и не более, чем N — 1 итераций, где N — число узлов.

Предварительный этап. 1. Находим для каждого yi множество абонентов Хyi, подключенных к нему радиальными КС по критерию минимума затрат на связь: х Є Хуi если

2. Определяем суммарный объем ИВР, выполняемых ВЦy

Рис 2.1 – Дерево решений при синтезе структуры методом ветвей и границ

Основной этап состоит из ряда итераций. Целью каждой итерации является уменьшение суммы приведенных затрат W за счет объединения нескольких мелких ВЦ в один. Как только оказывается, что дальнейшее объединение не приводит к уменьшению критерия W, работа алгоритма прекращается.

Рассмотрим (k+1)-ю итерацию. Пусть в результате k итераций определено множество наиболее целесообразных мест размещения ВЦ у (k) и найдены привязки , а соответствующее этому решению значение критерия Wk определяется формулой.

1. Проранжируем y ЄY(k) в порядке убывания величин Ну.

2. Выберем yk такой, что НУк = min НУi. Удалим yk из множества У (k). Обозначим Уост (k) = Y (k)\yk.

3.Осуществим привязку абонентов ХУк к оставшимся ВЦ по критерию минимума затрат на связь. Новое значение критерия

4.Сравним величины W‘ и Wk. Возможны два случая: 1) W‘≤Wk; 2) W‘>Wk.

В 1-м случае принимаем Y(k+1) = Yост(k), и итерация заканчивается. Во 2-м случае выбираем следующий по порядку пункт ук-1 и переходим к шагу 3.

Шаги 3 и 4 повторяются многократно до тех пор, пока либо очередной шаг 4 не закончится 1-м случаем, что означает конец итерации, либо множество Y(k) будет просмотрено полностью и ни один вариант укрупнения не приведет к улучшению величины критерия. Это является признаком окончания работы алгоритма.

2.2 Оптимизация структуры абонентских СДО в классе

древовидных сетей

Распространенный класс абонентских СДО для централизованных сетей ЭВМ составляют так называемые древовидные, структура которых представляет собой дерево или совокупность деревьев с корнями, которые соответствуют местам размещения РЦ. Такая структура получается, когда абонентские пункты (АП) подключают друг к другу по так называемой многопунктовой схеме. Применение многопунктовых сетей позволяет сократить капитальные затраты на создание СДО, повысить коэффициент использования каналов передачи данных, сократить общую протяженность сетей по сравнению с СДО радиальной структуры, в которой используются выделенные каналы для всех АП.

Задача синтеза абонентской СДО в классе древовидных сетей формулируется следующим образом. Заданы множество абонентов X = {xj}, характеризуемых своими географическими координатами местонахождения {δj, wj} и объемами информации hj, а также места размещения РЦ и привязки абонентов к РЦ Хyi., i = 1, т. Известны приведенные затраты на передачу информации от пункта i к пункту j: . Требуется синтезировать структуру абонентской СДО в классе древовидных структур минимальной стоимости при ограничениях на суммарный поток (трафик) fij в каждой ветви (i, j): fij ≤ dmax, где dmax— пропускная способность многопунктовой сети; fij определяется как сумма информационных потоков от всех узлов, предшествующих узлу i на путях от концевых вершин к корню дерева, и потока hi, определяемого абонентом xi.

Рассмотрим некоторые наиболее важные работы и алгоритмы решения этой задачи.

2.2.1 Алгоритм Прима

Задача синтеза древовидной сети впервые рассмотрена в работе Прима, в которой предложен точный алгоритм синтеза сети минимальной стоимости.

Первоначально рассмотрим исходное множество несвязанных узлов (вершин) X = {xi}.

1. Выбираем произвольный узел (подграф) xi и отыскиваем стоимость ввода ребра (i, j), связывающего xi с некоторым подграфом xjcij. Если подграфы хiи xj состоят из нескольких узлов, то отыскиваем ребро, связывающее ближайшую пару узлов xj и xil , принадлежащих к разным подграфам.

2. Среди всех пар (i, j) находим такую (i*, j*), чтосi*j* = min cij.

3. Объединяем подграфы и в один: = .