Построение маршрута при групповой рассылке сетевых пакетов данных (стр. 2 из 8)
1.Среди всех множеств
, построенных в результате k-й итерации, выбираем наиболее перспективное множество , т. е. такое, что 
.2.Ветвление. Выбираем некоторый РЦ yr Є
и разбиваем на два подмножества и так, что на подмножестве РЦ yr, переводится в разряд действующих, а на подмножестве накладывается запрет на строительство РЦ в пункте уr. Таким образом, 
Будем выбирать уrтак, чтобы подмножество
с наибольшей вероятностью содержало искомое решение, а не содержало. Тогда 
3.Вычисление оценок
и . В частности, для множества можно использовать следующую рекуррентную формулу:  |
4.На каждом из подмножеств
и находим допустимое решение, которое обозначим 
и соответственно.5. Проверка признака оптимальности. Пусть
≤ 
. Если 
где {
} — множество висячих вершин на 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.Рассмотрим некоторые наиболее важные работы и алгоритмы решения этой задачи.
Задача синтеза древовидной сети впервые рассмотрена в работе Прима, в которой предложен точный алгоритм синтеза сети минимальной стоимости.
Первоначально рассмотрим исходное множество несвязанных узлов (вершин) X = {xi}.
1. Выбираем произвольный узел (подграф) xi и отыскиваем стоимость ввода ребра (i, j), связывающего xi с некоторым подграфом xjcij. Если подграфы хiи xj состоят из нескольких узлов, то отыскиваем ребро, связывающее ближайшую пару узлов xj и xil , принадлежащих к разным подграфам.
2. Среди всех пар (i, j) находим такую (i*, j*), чтосi*j* = min cij.
3. Объединяем подграфы
и в один: 
= 
.На этом одна итерация метода заканчивается. Таким образом, на каждой итерации число изолированных подграфов сокращается. Как только их число N станет равно 1, работа алгоритма заканчивается. Доказано, что данный алгоритм позволяет получить оптимальное решение. Заметим, что в задаче Прима не вводятся ограничения на пропускные способности сети, и поэтому отсутствует ограничение на суммарный поток frl, передаваемый по произвольной ветви (r, l). Таким образом, алгоритм Прима позволяет синтезировать кратчайшее связывающее дерево (КСД) без ограничений. Практически гораздо более важной является задача синтеза КСД с ограничениями на суммарный поток frl, определяемый пропускными способностями КС drl.