Построение маршрута при групповой рассылке сетевых пакетов данных

МИНИСТЕРСТВООБРАЗОВАНИЯ И НАУКИ УКРАИНЫ
Государственныйуниверситет информатики и искусственного интеллекта
Д080403.1.01.03/056.НР
Кафедра программного обеспечения
интеллектуальных систем
ОТЧЕТО НИРС
Тема:«Построение маршрута при групповой рассылке сетевых пакетов данных»
Руководитель:
___________ доц.А.И. Ольшевский
(дата,подпись)
Нормоконтроль:
___________асс. Е.В. Курило
(дата,подпись)
Разработал:
___________ст.гр. ПО-03м Л.В. Карпенко
(дата,подпись)
2008

/>РЕФЕРАТ
Отчет о НИРС: 39 с., 3 таблицы, 14 рисунков, 6 источников.
Объектомисследования является алгоритм построения оптимального маршрута при групповойрассылке данных.
Цель –разработка алгоритма построения маршрута для дальнейшего теоретического ипрактического его применения, а также написание программного продукта какреализации алгоритма.
Предложеноразбиение алгоритма на два этапа, для которых рассмотрены соответствующиетеоретические исследования, проведен анализ предлагаемых подходов.
В итоге быливыбраны методы решения для каждого из этапов алгоритма и представленысхематические результаты построения.
Также былиразработаны структуры для хранения и обработки данных алгоритма, предложеныметоды настройки параметров алгоритма.
СЕТЬ, РЕГИОНАЛЬНЫЕ ЦЕНТРЫ, ДЕРЕВЬЯ ШТЕЙНЕРА, ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ,СТРУКТУРЫ ДАННЫХ
ВВЕДЕНИЕ
В настоящеевремя наиболее эффективным и перспективным методом обучения являетсядистанционное обучение (ДО). Широкое распространение персональных компьютеров иактивное развитие глобальных сетей (ГС) вывело этот процесс на принципиальноновый уровень. Теперь получить образование можно независимо от места жительстваи физических возможностей. Дистанционное образование позволяет получить дипломлюбого ВУЗа, любой специальности.
Но длякачественного обучения требуется как можно более плотное взаимодействиестудента с преподавателями. Необходимо передавать огромные объемы данных:задания, методические указания, выполненные работы.
В связи сэтим одним из актуальных вопросов ДО стал поиск оптимального способа пересылкиданных. Разрабатываются более дешевые и быстрые пути передачи информации.
ГС неявляются стабильными, т.е. изменяется их структура, количество участников,стоимость услуг. Поэтому разработать идеальный маршрут невозможно.
Дляпостоянного пересчета путей ищут алгоритмы их построения. Одним из способовпостроения является использование деревьев Штейнера (ДШ). Эта задача имеетмножество способов решения. В данной работе предлагается решать ее с помощьюгенетических алгоритмов (ГА).
Объектомисследования данной работы является алгоритм построения оптимального маршрутапри групповой рассылке данных по сети. Основным критерием оптимальностиявляется стоимость рассылки по построенному маршруту.
Для этогоалгоритм должен учитывать длину соединений, стоимость пересылки по каждой изветвей, общую стоимость пересылки по всем требуемым направлениям.
Для оценкиработы алгоритма, наглядного представления результатов и их практическогоприменения предполагается написать программный продукт (ПП). Предлагаемые особенностиреализации и настройки этого ПП будут рассмотрены в этом отчете.
/>1 ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ
По своей сутисеть дистанционного обучения (СДО) представляет собой дерево с набором вершин иребер. Построение оптимального маршрута для дерева является достаточно старойзадачей, для решения которой существует множество алгоритмов. Но не следуетзабывать о специфике задачи: в реальной ситуации весьма существенными факторамистановятся стоимость рассылки, протяженность и сложность маршрута, скоростьпередачи данных. Поэтому предлагается модифицировать существующие алгоритмы сучетом этих факторов.
Разрабатываемыйалгоритм делится на две части. На первом этапе построения сеть разбивается наподсети по числу региональных учебных филиалов. Это позволит снизить нагрузкупо рассылке с центрального учебного центра. Каждая подсеть объединятся вокругсвоего регионального центра (РЦ). Этот процесс сродни задаче разделенияобъектов на классы. Абонент приписывается к определенному центру на основании экономическойцелесообразности (стоимости его связи с данным центром).
Для разбиениямножества всех абонентов на подмножества не существует точных методов, но дляконкретной задачи можно выработать специальный алгоритм на основе известныхметодов. При этом следует рассмотреть разные виды структур сетей (радиальные,древовидные), чтобы иметь возможность наиболее эффективно их комбинировать.
Второй этапалгоритма – это построение деревьев внутри каждой подсети. В качестве критериевобычно рассматривается время передачи единицы данных по каналу, расстояние илиденежный эквивалент данного соединения, пропускная способность канала и др.
Для решениятакой задачи существует множество чисто математических методов, но придостаточно большом числе абонентов они не всегда удобны. В реальныхразветвленных сетях часто используют эвристические методы.
Но, так жекак и для предыдущего этапа, универсального решения не существует. Поэтомуследует рассмотреть различные методы построения деревьев и возможности ихкомбинирования.
Задачаразработки программного продукта состоит в том, чтобы он предоставлялнеобходимые возможности. А именно: возможность создания и редактирования сети;визуализация схемы построенного маршрута; вывод результатов расчетов дляпересылки по построенному маршруту; возможность настраивать параметры алгоритмадля получения наиболее оптимального результата и др.
Сложностьгенетических алгоритмов при построении деревьев состоит в кодировке исходныхданных. Для требуемых вычислений и представления структуры сети на экранеиспользуются различные типы данных. Поэтому предполагается совмещатьвещественное представление хромосом с традиционным.
2 МЕТОДЫ СИНТЕЗА СТРУКТУРЫ СЕТИ
 2.1 Размещениецентров и синтез абонентских СДО в классе радиальныхструктур
Точныеметоды для общей задачи структурного синтеза сетей неизвестны, однако для задачспециального вида можно разработать алгоритмы, использующие, например, методветвей и границ.2.1.1 Методветвей и границ
Этот метод является универсальнымметодом дискретной оптимизации и включает следующие процедуры: заданиеисходного множества вариантов, выбор наиболее перспективного множества дляразбиения, ветвление множества на подмножества, определение нижней границызначения критерия на каждом из образовавшихся подмножеств, поиск допустимого решенияв каждом из образованных подмножеств, проверку признака оптимальности. Основнаятрудность метода ветвей и границ состоит в выборе способа ветвления (разбиения)множества на подмножества и задании эффективной нижней границы критерия,позволяющей отбрасывать большое число бесперспективных вариантов.
Рассмотримреализацию метода ветвей и границ для задачи размещения центров и синтезарадиальной структуры сети. Метод состоит из конечного числа однотипныхитераций, на каждой из которых строится совокупность подмножеств вариантов:
/>
гдек —номер итерации.
Каждоеиз подмножеств /> характеризуется следующимимножествами: />— множество пунктов, где РЦ уже построены; /> —множество пунктов, где еще можно строить РЦ; /> — множество пунктов, гденаложен запрет на строительство РЦ, при этом
/>
гдеY — исходноемножество пунктов, в которых допускается строительство РЦ, Y Є Х.
Обозначимчерез Xyi множествоабонентов, подключенных к РЦ уi (у Є Р) покритерию минимума затрат на связь, т. е. х Є Хуi, если />. Каждое из множеств /> характеризуетсявеличиной нижней границы критерия /> для всех структур (решений),определяемых данным множеством. Величина ξ задается следующимсоотношением:
/>
/>
где .
Допустим,что каким-то приближенным методом (например, R-структур) удается построить структуру Х0 на множестве />. При этом в решение должнывойти все РЦ уi Є /> и не должно быть ни одного РЦ уi Є />.
Обозначимвеличину критерия для структуры Х0 через W(Х0). Справедлив следующий признакоптимальности: если W(Х0) = />,то вершина дерева решений /> является конечной идальнейшему разбиению не подлежит; если W(Х0) ≤ min /> для всех висячих вершин /> построенных на k-й итерации, то Х0 — искомоеоптимальное решение (структура). Предположим, что уже проведено k итерацийи еще не найдено оптимальное решение. Опишем произвольную (k + 1)-ю итерацию:
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.
Рассмотримнекоторые наиболее важные работы и алгоритмы решения этой задачи.

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.  Объединяемподграфы /> и /> в один: /> = />.
Наэтом одна итерация метода заканчивается. Таким образом, на каждой итерациичисло изолированных подграфов сокращается. Как только их число N станет равно 1, работаалгоритма заканчивается. Доказано, что данный алгоритм позволяет получитьоптимальное решение. Заметим, что в задаче Прима не вводятся ограничения напропускные способности сети, и поэтому отсутствует ограничение на суммарныйпоток frl, передаваемыйпо произвольной ветви (r,l). Таким образом,алгоритм Прима позволяет синтезировать кратчайшее связывающее дерево (КСД) безограничений. Практически гораздо более важной является задача синтеза КСД сограничениями на суммарный поток frl, определяемый пропускнымиспособностями КС drl.2.2.2Алгоритм Исау-Вильямса
Однимиз наиболее известных и распространенных алгоритмов синтеза КСД с ограничениямиявляется алгоритм Исау—Вильямса, известный под названием 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*
Опишем(k+1)-ю итерацию. Выбираемпроизвольный изолированный подграф Xi.Находим произвольный подграф Xjи проверяем возможность ввода ребра (i,j): Hi + Hj≤. d.
Еслиусловие выполняется, то вычисляем Eij= cij(Hi) — vi.
Находимтакую пару (i*, j*), для которой Ei*j* =;min Еij.
ЕслиEi*j*
АлгоритмКраскала отдельно рассматривать не стоит, так как он аналогичен уже описанному.Отличительной особенность является то, что в начале все узлы изолированы, на каждомшаге отыскивают наименьшую по стоимости допустимую линию связи различных узлов.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
Шаг 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.
Результатыэкспериментов показали, что зависимость логарифма времени работы ЭВМ отлогарифма числа терминалов имеет линейный характер с наклоном кривой, которыйсвидетельствует о квадратичной зависимости вычислительной сложностиунифицированного алгоритма от размерности задачи N. В результате исследованийвыявлено, что время решения задачи почти не изменяется при переходе от одногоправила v к другому и при измененииограничений, в то же время оно сильно зависит от числа соседних терминалов,подключаемых к данному (т. е. числа новых линий, подключаемых к дереву).Зависимость времени работы унифицированного алгоритма синтеза КСД от числасоседних терминалов для сети с 40 терминалами приведена в таблице 2.2.
Таблица2.2 – Зависимость времени работы терминалаЧисло соседних терминалов, К Время работы алгоритма, мин Относительная стоимость связи 1 0,434 7,77 2 0,491 5,26 3 0,522 4,54 4 0,557 4,50 5 0,589 4,48 8 0,691 4,45 10 0,767 4,45 15 0.985 4,45 20 1,240 4,45 25 1,503 4,45 30 1,767 4,45 39 2,245 4,45 2.2.6Алгоритм D-структур
Вмодели многопунктовой ЛС, используемой как в унифицированном алгоритмеКершенбаума — Чжоу, так и в алгоритмах Исау — Вильямса, Мартина, Краскала идругих, учитывают следующее допущение: при подключении очередного АП кмногопунктовой сети стоимость канала передачи данных между узлами i иj /> не зависит от объема информации hi, при этом вводится лишьодно ограничение: fij ≤ d, гдеfij— суммарный поток (трафик)в любой ветви (i, j). Такоедопущение справедливо в случае, когда по всей длине многопунктовой связи ее пропускнаяспособность d остаетсяпостоянной. Вместе с тем использование модемов, работающих с различнымискоростями передачи данных, позволяет организовать многопунктовые связи, вкоторых пропускная способность постепенно изменяется по мере приближения линии кцентру обработки данных.
Такимобразом, для многопунктовых связей с изменяемой (регулируемой) пропускнойспособностью традиционно используемое допущение />(hi) =const оказывается неверным,что исключает возможность использования унифицированного алгоритмаКершенбаума—Чжоу.
Длярешения задачи синтеза структуры древовидной сети при переменной скоростипередачи данных предложен алгоритм D-структур.Важной особенностью алгоритма D-структурявляется то, что на шаге 1 определяются оптимальные места размещения РЦ ирадиальная структура СДО, а затем она преобразуется в древовидную структуру.Рассмотрим описание алгоритма. Введем следующие обозначения: Хi, Xj — подграфы графа X, Xi = {xi*, xi2,…, Xin}; xi* —направляющая вершина подграфа Хi т. е. его концеваявершина на данной итерации, куда сходятся информационные потоки из всех хЄХi. Будем предполагать, чтоподключить Xi к Xj можновведением ветви (i*, j), исходящейтолько из направляющей вершины xi*, причемхjЄХj, и на Xj ограниченияне накладываются; Hi — суммарный объем ИВРподграфа Xi, />,hij — суммарный поток в ветви(i, j); С(Хi)— стоимость передачиинформации во всех ветвях подграфа Xi.
1.Применяемалгоритм синтеза R-структур,находим размещение РЦ Y*= {yi*} и привязки абонентов кРЦ Хyi.Далее предполагаем, что РЦразмещен в пункте 1.
2.Определяемначальные веса всех вершин vi = />(hi,li1) ивыполняем переход на подпрограмму «Оценка» (шаги 3—20).
Подпрограмма«Оценка». В подпрограмме «Оценка» определяем стоимость передачи объемаинформации Hi от подграфа Xi кподграфу Xj принаилучшем варианте подключения. Пусть к началу итерации построено К. подграфов X1, Х2, … Хк.
3.Выбираемизолированный подграф Хi.
4.Проверяемвозможность введения ветви (i, j)
Нi + Нj ≤dmax
Еслиусловие выполняется, то переходим к шагу 5, в противном случае полагаем, чтоэкономия Еij = ∞, переходим к шагу 4 ивыбираем другую пару подграфов Хr, Хl для анализа.
5.Отыскиваемвершину xj1, (xj1 ЄХj), ближайшую к xi*:
/>
6.  Проверяем,является ли xj1 направляющейв подграфе Xj.Если — да, то запоминаем дугу (i*,j*), вычисляем /> = Ci*j*(Hi,li*j*), Н’j=Нj + Нi и переходим к шагу 21,иначе — к шагу 7. Шаги 7—20 предназначены для нахождения наилучшего вариантаподключения Хi кXj.
7.  Определяемнаправленный маршрут из xi* вxj* через вершину xj1. Пустьим окажется πi*j*={xi* – xj1 – xj2 – … xjk}, xjk=xj*.
8.  ВычисляемСi*j1 = /> (Hi,li*j1), находимni*j1 = ]Hi/d[,где ni*j1 — число каналов в ветви (i*, j1);знаком] [ обозначено округление с избытком. Пусть nikjk — число каналов в ветви (ik, jк).
9.  ПринимаемСij =0; Сij = /> (li*j1).
10.Полагаемs = 0, где s — номер итерации.
11.s=s+1.
12.Проверяемусловие, все ли ветви маршрута πi*j*просмотрены. Если s
13.Вычисляем/> (Hi) — приращение стоимости для передачидополнительного объема информации Hi:
/>
единичныхканалов, которые необходимо установить в ветви (js, js+1); dТФ —ПС телефонного канала связи.
14.Вычисляемвеличины
/>
15.ОпределяемCij = Cij + /> (Hi).
16.Вычисляем /> = /> (li*js+i, Hi).
17. СравниваемCij с/>. Если Cij  топереходим к шагу 11, иначе переходим к шагу 18.
18. ПолагаемCij =/>, вводим дугу (i*, js+1)вместо (i*,j).
19.Восстанавливаем прежние значения трафиков hij на всех предыдущих ветвях маршрута πi*j*:
/>
20. Переходим к шагу 11.
21. Вычисляем экономию Еij при подключении Xi кXj по сравнению сподключением Xi к РЦ напрямую: Eij =Сij — vi.
22.  Находимминимальное значение Eiljl = min Eij, где минимум берется повсем подграфам Xi, Xj.
23.  Проверяемусловие Eiljl
24.  Вводимдугу (il, jl) и подключаем Хil к Хjl.Образуем новый подграф Х’jl=Хil ⋃Хjl с направляющей вершиной x’jl*=xjl*, H’jl=Hil+Hjl.
25.  Проводимкоррекцию весов для всех вершин нового подграфа Х’jl:
/>
где /> — стоимость передачи информации из направляющей вершины /> в РЦ у1.
26.  Если подграф Хjl напрямую связан с ВЦy1, то />, и тогда v’jl = 0, v’il = 0. В этом случаеподграф Хjl из дальнейшегорассмотрения исключается.
27.Проверяем условие, все липодграфы подключены к РЦ. Если условие выполняется, то переходим к шагу 28,иначе — к шагу 3.
28.Вычисляемкритерий — суммарные приведенные затраты Wпр — для построенноговарианта D-структуры: Wпр = />
Итак,как следует из описания алгоритма D-структур,объединение изолированныхподграфов проводится до тех пор, пока это экономически целесообразно ивыполняется ограничение, в противном случае соответствующий подграфподключается напрямую к узлу 1 (РЦ). Завершается работа алгоритма построением деревас корнем в узле, соответствующем месту размещения РЦ. Следует отметить, чтоалгоритм D-структур,как и другие алгоритмы синтеза СДО в классе древовидных структур, требуетвычислительных затрат порядка N log N, где N — число узлов.
Работаразличных алгоритмов синтеза КСД иллюстрируется на примере решения задачисинтеза структуры сети, имеющей N = 20 узлов.Прямоугольные координаты узлов (xj,yj) иобъемы информации hj,генерируемые каждым из узлов, приведены в таблице 2.3. Стоимость единицы длиныканала составляет 30 руб./(кан.- км), а ограничение по пропускной способности dmax = 25 бод (бит/c).
Таблица 2.3 –Исходные данные для задачиі
*Г
км у,; км бит/с / км
щ
км бит/о V */-км у,; км бит/с 2 —35 80 5 9 —16 — 12 5 15 20 50 4 3 —39 60 7 10 —23 11 16 53 25 2 4 —20 50 3 11 —10 —16 7 17 70 34 10 5 —4 30 4 12 22 7 5 18 42 62 8 6 -20 25 4 і 13 40 5 8 19 35 78 7 7 -12, 12 9 14 30 20 4 20 17,5 70' 4 8 —40 18 6
Территориальноеразмещение узлов (АП) и решение задачи по алгоритму Прима (КСД без ограничений)показано на рисунке 2.2, а. РЦрасположен в пункте 1. Общаяпротяженность сети L = 366 км,а стоимость W = 10 980 руб. Оптимальнаяструктура с учетом ограничений, полученная по методу ветвей и границ при L = 426 км, W = 12 780 руб.,изображена на рисунке 2.2, б. Цифры,указанные в кружках на ребрах графа, соответствуют суммарному трафику (бит/с),передаваемому по данной связи. Как следует из рисунка 2.2, а, для сети Прима нарушаютсяограничения по пропускной способности для связей 1—12 и 1—7.
/>
Рисунок2.2 – Структура СДО, синтезированная по алгоритму:
а –Прима; б – метод ветвей и границ
На рисунке 2.3, а построенаструктура СДО, синтезированная по алгоритму Исау — Вильямса, на рисунке 2.3, б — поалгоритму Шарма, на рисунке 2.3, в — по алгоритму Фогеля при L = =447 км,W = 13400 руб. и на рисунке 2.3, г — по алгоритму Краскала. Для данной задачииз всех эвристических алгоритмов наилучшие результаты дает решение поалгоритмам Исау — Вильямсаи Шарма (L = 440 км,W = 13 200 руб.),а наихудшим оказался алгоритм Краскала (L — 456 км,W = 13 680 руб.). Далее эта задачарешена методом D-струк-турдля случая, когда имеются каналы двух типов d1 = 25 бит/с,c1 = 30 руб. /(кан.- км) и d2 = 40 бит/с,с2 = = 50 руб./(кан.- км). Онахарактеризуется показателями L = = 387 км,W = 12 330 руб.Синтезированная структура показана на рисунке 2.4.
/>
Рисунок 2.3 – Структура СДО,синтезированная по алгоритму:

/>
а – Исау-Вильямса; б – Шарма; в – Фогеля; г – Краскала.
Рисунок 2.4 – Структура СДО,синтезированная по алгоритму D-структур2.3Разработка структуры для поставленной задачи
В предыдущихразделах были описаны достоинства и недостатки различных способов разработки иоптимизации структур сетей. Приводились доводы за и против использованиякакой-либо структуры для поставленной задачи синтеза сети дистанционногообучения.
В результатепредлагается остановиться на варианте D-структурыкак наиболее универсальной. Она объединяет в себе преимущества радиальной идревовидной структур, и в то же время учитывает специфику сети передачи данных.
В рамкахпоставленной задачи не следует забывать о том, что составляющие элементы сетиуже будут заданы конкретной ситуацией. От разработчиков не зависит расположениеабонентов, существующие связи между ними, а зачастую и расположениепромежуточных узлов.
Такимобразом, сама по себе сеть будет задана внешними условиями, а задача синтезасводится к оптимизации распределения абонентов между региональными центрами.
В концеработы первого этапа алгоритма построения маршрута синтезированная сеть будетприблизительно иметь вид, представленный на рисунке 2.5./> />
Рисунок 2.5 –Схематичное представление синтезированной СДО
Обозначения:
/>/>– ВУЗ
/>/>– региональные центры
/>/>– абоненты
/>3 МЕТОДЫ ПОСТРОЕНИЯ ДЕРЕВЬЕВ
 3.1 ЗадачаШтейнера для построения сети
Задача Штейнера относится к классу так называемых NP-полных задач,поэтому алгоритмы, дающие точные решения, как правило, не могут бытьиспользованы в САПР из-за неприемлемой временной сложности. Это обстоятельствопослужило стимулом для разработки многочисленных эвристических алгоритмов.Наибольший практический интерес представляет алгоритм последовательноговведения дополнительных вершин в дерево Прима-Краскала. Использованиепредложенного алгоритма позволяет строить деревья Штейнера, длина которых всреднем не превышает длину оптимального дерева Штейнера более чем на 0.5процента. Временные характеристики модификаций алгоритма позволяют успешноиспользовать его на данном этапе построения маршрута.
Математическаямодель задачи синтеза структуры сети по критерию стоимости приведена ниже.
Пусть имеетсямножество Х={xj} абонентов сети – источников информации с объемом трафикаабонента h;{gj, wj} – географическиекоординаты пункта, а также места размещения сервера {yi*} и привязки абонентов ксерверу Xyi,i=1..m. Известны приведенныезатраты на передачу информации от пункта i к пункту j: />. Требуетсясинтезировать структуру сети в классе древовидных структур минимальнойстоимости при ограничениях на суммарный поток fij в каждой ветви (i,j): />, где dmax – пропускная способностьлинии связи; fij определяется как сумма информационных потоков от всех узлов,предшествующих узлу i на путях от концевых вершин к корню дерева и потока hi, определяемого абонентомxi.
Для ДШпостановка задачи выглядит следующим образом.
Дано:
– сеть,представленная в виде ненаправленного графа G=(V, E), где V – набор узлов, а Е –набор связей;
– матрицастоимости W,где Wij показывает стоимость использования связи (i,j) /> Е;
– узел-центр s /> V и набор узлов-участниковD /> V;
– каждый узелvi имеет координаты xi и yi на экране, название итип (центр, участник, вершина Штейнера, незадействованный узел).
Нужно найтитакое дерево Т сети G с корнем в s, стягивающее всех членов набора D так, что полнаястоимость ребер дерева Т будет минимальна. В стоимость обычно включается времяпередачи единицы данных по каналу, расстояние или денежный эквивалент данногосоединения, пропускная способность канала или комбинация критериев.
Основнымикритериями оценки алгоритма являются скорость сходимости и близость получаемогорешения к оптимальному.
Основная идея алгоритма заключается в следующем.Достаточно хорошим приближением дерева Штейнера является дерево Прима-Краскала,длина которого не может превышать длину соответствующего дерева Штейнера болеечем в полтора раза. Также для случая ортогональной метрики доказано, что есличерез каждую точку из исходного множества точек провести горизонтальные ивертикальные линии, то решение задачи Штейнера можно получить рассматривая вкачестве возможных дополнительных вершин только точки пересечения полученной сеткилиний. Данный алгоритм последовательно вводит в текущее дерево Прима-Краскалакаждую из дополнительных вершин решеточного графа, строит новое дерево Прима изапоминает полученный выигрыш в длине. После оценки всех дополнительных точек втекущее дерево включается точка с максимальным выигрышем. При этом, чтобыизбежать в процессе преобразования появления избыточных точек, необходимоучитывать, что дополнительные точки в дереве Штейнера могут иметь толькостепень 3 и 4.
Предложен ряд процедур, позволяющих кардинальным образом сократитьвремя работы за счет предварительной «отбраковки» тех вершин, чья вероятностьоказаться штейнеровской точкой равна нулю или крайне мала. Данная процедура внесколько раз уменьшает временную сложность исходного алгоритма и, что не менееважно, в среднем качество получаемых решений не ухудшается.
В данной работе под средними показателями алгоритма(качественными, временными или какими либо другими) следует понимать среднийрезультат для 10.000 задач. Тестовый набор для каждого значения размерностисостоит из 10.000 различных задач, полученных случайным образом. Всерезультаты, приведенные в работе, получены на этих тестовых наборах.
Можно отметить, что для модифицированного варианта алгоритмапроцент улучшения дерева Прима-Краскала немного, всего лишь на несколько сотыхдолей, но все-таки больше, чем тот же самый показатель исходного алгоритма. Этообусловлено сокращением числа локальных неоптимальных минимумов эвристики засчет сокращения числа возможных дополнительных точек.
Однако можно сделать интересное наблюдение, если сравнивать несредние результаты достаточно большого тестового набора, а результаты,полученные двумя различными способами для каждой конкретной задачи. В строке G(«good») приведен процент от общего числа тех задач, в которых вышеописанныймодифицированный алгоритм дает выигрыш в суммарной длине всех ребер дерева посравнению с исходным алгоритмом. В строке B («bad») приведен процент тех задач,в которых модифицированный алгоритм уступает исходному. И, наконец, в строке U(«unchanged») показан процент всех оставшихся задач, для которых результатыработы обоих алгоритмов совпали.
Можно отметить две тенденции. Во-первых, с ростом числа точекуменьшается число задач, в которых оба алгоритма получают один и тот же результат.Во-вторых, число более удачных решений модифицированного алгоритма по отношениюк исходному приблизительно равно числу менее удачных решений. Данноесоотношение справедливо как для задач малой размерности, так и для большихзадач. Объяснение этому достаточно простое. Как и большинство всех известныхэвристических алгоритмов (и не только применительно к задаче Штейнера), даннаяэвристика не всегда сходится к оптимальному решению, а, как раз наоборот, чащесходится к некоторому решению — локальному минимуму, отличному от оптимальногорешения. С ростом числа точек растет количество таких локальных неоптимальныхминимумов, и, соответственно, уменьшается вероятность схождения алгоритма крешению с наилучшим результатом. Также на окончательный результат сильно влияетпервая итерация алгоритма, очень часто именно она задает практическиокончательную конфигурацию дерева, которая уже очень мало изменяется напоследующих итерациях.
Данные рассуждения не являются каким-то таким уж невероятнымоткрытием. Однако, тот факт, что средние результаты двух алгоритмов отличаютсявсего лишь во втором, третьем, а то и большем знаке, ловко маскирует другуютенденцию. А именно, практически абсолютная идентичность средних результатовдостигается не за счет сходимости двух разных алгоритмов к одному и тому жерешению, а за счет, так сказать, статистической схожести этих двух эвристик.Эта интересная тенденция, по-видимому, до сих пор выпадала из поля зренияисследователей, работающих с этим алгоритмом. Сравнивая различные методыулучшения качественных показателей, коллеги ориентировались только на среднийрезультат и стремились получить максимальный выигрыш сразу, за один проход.Яркий пример этого подхода iterated 2-Steiner algorithm, где предлагаетсяоценивать выигрыш от введения сразу двух возможных точек Штейнера в деревоПрима-Краскала. Временная сложность алгоритма в этом случае вырастаетневероятно, что уже не позволяет использовать его на данном этапе.
Данная работа предлагает способ, позволяющий за приемлемое времязначительно улучшить качественные показатели модифицированного алгоритма засчет последующего динамического перестроения дерева Штейнера. Иными словами,использовать данную конфигурацию дерева (близкую к оптимальному решению) не какокончательный результат, а как исходную конфигурацию для следующего этапаэвристики.3.2 Локальноеперестроение дерева Штейнера
Для улучшения начальной конфигурации дерева предлагается длякаждой глобальной точки исходной задачи провести процедуру локальногоперестроения дерева Штейнера. Эту процедуру следует проводить на множестветочек, включающем саму эту точку и инцидентные ей вершины (рисунок 3.1).Поскольку степень точки в дереве Штейнера не может быть выше 4-х, томаксимальная размерность локальной задачи Штейнера, соответственно, не можетбыть больше 5-ти. Для задач же с размерностью до 5-ти точек включительно, какизвестно, существуют быстрые алгоритмы определения оптимальной конфигурациидерева Штейнера.
/>
Рисунок 3.1 – Процесс локального перестроения дерева для глобальнойвершины

Для данного метода перестроения дерева характерно некоторое числоположительных исходов данной процедуры (стратегия A).
Аналогичную процедуру можно провести и для дополнительных точек,локально перестраивая дерево Штейнера на том же множестве точек инцидентныхданной точке, но, в отличие от той же процедуры для глобальной точки, невключая в данное множество рассматриваемую точку (рисунок 3.2). Данный подходтакже позволяет получить некоторое небольшое число положительных исходов(стратегия B).
/>
Рисунок 3.2 – Процесс локального перестроения дерева длядополнительной вершины
Факт наличия выигрыша от использования описываемых алгоритмов исам факт незначительности этого выигрыша объясняются особенностями первогоэтапа модифицированного алгоритма. На этапе предварительной выборкидополнительных точек существует очень маленькая, но все-таки ненулеваявероятность пропустить точку, которая могла бы дать выигрыш при включении ее вдерево Штейнера.
К достоинствам вышеописанных процедур можно отнести линейную отразмерности задачи временную сложность. Недостаток же очевиден – это малоечисло положительных исходов.
Использование совокупности только этих двух алгоритмов в качествепроцедуры перестройки дерева Штейнера неэффективно. Большая часть времени будетзатрачена на такие подготовительные процедуры, как выделение памяти иинициализация переменных, а затем, после отработки алгоритмов, на освобождениезанятой памяти (стратегия 0). Однако использование этих процедур в качествеотдельного этапа (первого среди нескольких) – вполне разумно, тем более, чтомаксимальный эффект от их использования достигается в совместном использованиис другими подходами, что и будет показано немного ниже.
Стоит добавить, что можно не ограничиваться рассмотрением тольколишь инцидентных вершин каждой рассматриваемой точки. Если в построениелокального дерева Штейнера включить инцидентные вершины второго уровня (рисунок3.3) и использовать для определения конфигурации дерева модифицированныйалгоритм, то количество положительных исходов вырастает во много раз за счет,конечно, увеличения временных показателей (стратегии D, E, F).
/>
Рисунок 3.3 – Локальное перестроение дерева Штейнера для вершины 0и инцидентных вершин первого и второго уровней
3.3 Процедураобъединения свободных ребер
Введем понятие свободного ребра. Свободное ребро – это ребро,соединяющее две несовпадающие вершины, причем X и Y координаты первой вершиныне равны соответственно X и Y координатам второй вершины.
Разработчик свободен в выборе окончательной конфигурации этогосоединения, поэтому его будем называть «свободным». Вершины, у которых равныили X координаты, или Y координаты, можно соединить только одним единственнымоптимальным способом − вертикальным или горизонтальным ребромсоответственно (рисунок 3.4). Такие ребра будем называть жесткими илинесвободными.
/>
Рисунок 3.4 – Примеры конфигураций свободного ребра и двух жесткихребер
Предлагается использовать следующий метод перестроения дереваШтейнера. Для каждой пары свободных ребер AB и CD текущего дерева Штейнераищется и добавляется в дерево ребро EF минимальной длины, соединяющее ребра ABи CD. В возникающем в результате такого добавления цикле удаляется самоедлинное ребро (рисунок 3.5). При удалении ребра для избежания появленияизбыточных точек необходимо учитывать, что точки Штейнера могут иметь толькостепень 3 или 4. Если данная процедура дает выигрыш в общей длине дерева, тозапоминается текущая конфигурация дерева, если нет, то восстанавливаетсяисходная конфигурация.
Выигрыш в данном случае составляет 3 условные единицы длины.
Для избежания избыточных вычислений можно воспользоваться простойдополнительной проверкой: расстояние между двумя свободными ребрами должно бытьстрого меньше длины самого большого ребра в текущем дереве Штейнера.
Если два свободных ребра имеют общую вершину, то такую пару реберможно не рассматривать, поскольку ситуация, аналогичная той, которая изображенана рисунке 3.6 (a), принципиально невозможна после работы первого этапа(локальное перестроение дерева Штейнера для точек обоих типов). Остальныеконфигурации, такие как, например, на рисунке 3.6 (b) не могут дать какой-либовыигрыш в суммарной длине дерева.
/>
Рисунок 3.5 – Процесс объединения двух свободных ребер
(a) исходная конфигурация;
(b) в дерево добавляется ребро EF, соединяющее два свободных ребраAB и CD;
(c) в возникшем цикле удаляется самое длинное ребро.

/>
Рисунок 3.6 – Примеры возможных положений свободных ребер, имеющихобщую вершину
Выбор только свободных ребер в описываемом алгоритме не случаен.Экспериментальные исследования показали, что при хорошей начальной конфигурациидерева достаточно ограничиться одним лишь рассмотрением всех пар свободныхребер (стратегия G). Попытка объединить все остальные ребра (горизонтальные ивертикальные) как между собой, так и со свободными ребрами, в общем случаегораздо менее эффективна (стратегия H). Соотношение количества положительныхисходов ко времени счета значительно уступает тому же показателю процедурыобъединения только свободных ребер.3.4 Процедураотсоединения ребра, содержащего дополнительную вершину
В качестве следующего этапа предлагается воспользоваться следующейпроцедурой. В текущем дереве Штейнера убирается одно из ребер. Как минимум однаиз вершин такого ребра должна быть дополнительной. Результатом такого удаленияявляются два поддерева. Оба они перестраиваются с целью достижениямаксимального выигрыша и снова соединяются вместе.
Если в результате данной процедуры есть выигрыш в суммарной длинедерева, то данная конфигурация становится текущей, если – нет, товосстанавливается исходная конфигурация дерева (рисунок 3.7). Данная операцияповторяется в том же виде для каждого следующего ребра, одна из вершин которогодополнительная. Причем для достижения большей эффективности все новые ребра такоготипа, возникающие в результате работы процедуры, следует добавлять в конецсоответствующего списка.
/>
Рисунок 3.7 – Перестроение дерева с использованием процедурыотсоединения ребра с дополнительной вершиной
(a) исходное дерево; формируется список ребер, один конец которых –дополнительная вершина;
(b) перестроение на примере одного из ребер;
(c) выбранное ребро удаляется из дерева;
(d) удаляются дополнительные вершины со степенью меньше трех;
(e) два поддерева перестраиваются с целью минимизации суммарнойдлины ребер;
(f) поддеревья соединяются кратчайшим образом.
Выигрыш в данном случае составляет 2 условные единицы длины.
Для перестроения возникающих в результате удаления ребра двухдеревьев предлагается использовать все выше предложенные подходы. А именно:локальное перестроение дерева для глобальных и дополнительных вершин (стратегияI), то же самое плюс объединение свободных ребер (стратегия J). Рассматриватьследует лишь только те вершины и ребра, которые были изменены или появились врезультате разделения дерева на два поддерева. Действительно, использование техили иных процедур перестроения в качестве самостоятельных этапов перед работойрассматриваемого алгоритма гарантирует то, что их повторное использование неможет дать какой-либо выигрыш. Поэтому, например, в процедуре объединениясвободных ребер поддерева вместо рассмотрения всех пар свободных реберподдерева достаточно ограничиться рассмотрением всех новых свободных ребер состальными. Одно новое ребро обычно возникает при начальном отсоединении ребра(ребра AB и CD на рисунке 3.7d), одно или несколько могут возникнуть послепроцедуры локального перестроения (ребро CE на рисунке 3.7e).
При рассмотрении каждой пары ребер следует учитывать ужеупомянутое условие, а именно, расстояние между ребрами должно быть строгоменьше длины самого длинного ребра поддерева. Все данные ограничения позволяютсущественно сократить общее время счета алгоритма без какой-либо потерикачества. Отсюда вытекает следующий вывод. Если обе вершины удаляемого ребра дополнительные,то следует пытаться перестроить оба поддерева, если же одна вершинадополнительная, а другая глобальная, то поддерево, соответствующее второйвершине можно даже не рассматривать. Характер используемых процедурперестроения не может дать какой-либо выигрыш в суммарной длине второгоподдерева.
Экспериментальные результаты показали, что, если после процедурперестроения поддеревьев суммарный выигрыш так и остался равен длине удаленногоребра, то эти два поддерева можно даже и не объединять, а сразу возвращаться кисходной конфигурации. Вероятность выигрыша в данном случае мала, и этотвыигрыш несопоставим с тем временем, которое требуется на соединение двухдеревьев, поскольку в данном случае приходится вычислять расстояния междукаждым ребром первого дерева и каждым ребром второго дерева.
Все выше приведенные рассуждения, ограничения и экспериментальныеданные объясняют постулированное в самом начале главное ограничение. Удалениеребра, обе вершины которого глобальные вершины, абсолютно неэффективнаяпроцедура.
Для максимального улучшения дерева можно добавить также процедуруобъединения вершины и свободного ребра: сначала в качестве самостоятельногоэтапа, а затем в составе процедуры перестроения поддеревьев (стратегия Kприложения). Этот метод аналогичен процедуре объединения двух свободных ребер (рисунок3.8).
/>
Рисунок 3.8 – Процесс объединения свободного ребра и вершины
(a) исходная конфигурация;
(b) в дерево добавляется ребро CD, соединяющее свободное ребро ABи вершину C;
(c) в возникшем цикле удаляется самое длинное ребро.
Выигрыш в данном случае составляет 1 условную единицу длины.
Жесткие ребра не берутся в рассмотрение по уже указанной причине,а именно, изначально хорошая конфигурация дерева Штейнера дает максимальнуюэффективность только лишь при работе со свободными ребрами. А при работе всоставе процедуры перестроения поддеревьев следует ограничиться следующимимножествами:
-         новыесвободные ребра – все вершины поддерева;
-         всеновые и измененные вершины поддерева – все старые и новые свободные ребра.3.5Стратегии алгоритма
Стратегия 0 – процедура перестроения дерева без каких-либо методовулучшения как таковых. Посчитана отдельно и приведена здесь для того, чтобыпоказать общее для всех стратегий время, затрачиваемое на предварительныемероприятия (выделение памяти, инициализация переменных), и время напоследующее освобождение памяти, дабы отделить это время от непосредственнометодов улучшения.
Стратегия A – локальное перестроение дерева для всех глобальныхточек.
Стратегия B – локальное перестроение дерева для всехдополнительных точек.
Стратегия C – объединение двух вышеописанных стратегий A и B.
Стратегии D, E, F аналогичны стратегиям A, B, C соответственно, нов каждом случае локального перестроения дерева включены в рассмотрениеинцидентные точки второго уровня.
Все нижеследующие стратегии содержат стратегию C в качествепервого этапа (кроме специально оговоренного случая).
Стратегия G – процедура объединения свободных ребер.
Стратегия H – процедура объединения всех ребер (горизонтальных,вертикальных и свободных).
Все нижеследующие стратегии содержат стратегию G в качествевторого этапа.
Стратегия I – процедура удаления ребер с дополнительными точками.В качестве процедуры перестроения поддеревьев используется локальное перестроениедерева для глобальных и дополнительных точек.
Стратегия J – то же самое, что и стратегия I, но в процедуруперестроения поддеревьев добавлена процедура объединения свободных ребер.
Стратегия K – то же самое, что и стратегия J, но добавленапроцедура объединения точек и свободных ребер в качестве отдельного этапа и всоставе процедуры перестроения поддеревьев.
Стратегия L – стратегия максимального улучшения начального дереваШтейнера. Включает в себя все процедуры стратегии K, но во всех местах своего использованияметод локального перестроения дерева заменен той же процедурой, но сиспользованием точек второго уровня инцидентности.3.6Заключительный вид алгоритма
Исходный алгоритм последовательного введения дополнительных точекв дерево ПримаКраскала выглядит теперь следующим образом:
-         1этап: предварительная отбраковка дополнительных вершин;
-         2этап: последовательное введение дополнительных вершин в дерево Прима;
-         3этап: динамическое перестроение дерева Штейнера.
Непосредственно перед работой алгоритма часть дополнительных точекисключается из рассмотрения за счет процедуры «отбраковки». Затем послеотработки основной части алгоритма запускается вышеописанная процедурадинамического перестроения дерева. Она исправляет «огрехи» предварительногоэтапа, поскольку существует маленькая, но все же ненулевая вероятностьисключить из рассмотрения точку, которая дала бы выигрыш в длине при включениив дерево Штейнера. Попутно эта процедура исправляет недостатки основногоалгоритма, трансформируя исходное дерево в дерево с лучшей, а зачастую,оптимальной конфигурацией.
Для этапа перестроения предлагается использовать стратегию J. Этастратегия в сравнении с другими имеет лучшее соотношение числа положительныхисходов ко времени счета. Среднее число положительных исходов при примененииданного метода составляет несколько процентов для задач с 6-ю – 7-ю точками,уже около двух десятков процентов для задач с 10-ю точками и больше 90% длязадач с 60-ю точками.
Совместный итог работы и предложенного подхода – новый алгоритм,временные показатели которого в несколько раз лучше исходного алгоритма.Качество получаемых решений при этом близко к оптимальным показателям./>3.7 Генетические алгоритмы
Генетическиеалгоритмы – есть поисковые алгоритмы, основанные на механизмах натуральнойселекции и натуральной генетики. Их реализовывает сильнейших средирассматриваемых структур формируя и изменяя алгоритм, на основе моделированияэволюций поиска.
Популяция –набор решений.
Эволюцияпопуляции – чередование поколений, в которых хромосомы изменяют свои гены, т.о.чтобы каждая новая популяция наилучшим образом приспосабливалась к новой(внешней) среде.
Основнойсложностью применения ГА для построения ортогональных деревьев Штейнераявляется оптимальное кодирование и выбор эффективных генетических операторов.Повышение эффективности алгоритма достигается за счет введения в процедурупоиска оператора мутации, транслокации и рекомбинации. Оператор транслокации допоследнего времени не применялся при решении задач оптимизации.
Предлагаетсякомбинированный эвристический алгоритм построения дерева Штейнера, использующиймодифицированный метод кодирования, основанный на триангуляции, имодифицированный точечный оператор кроссинговера.
Данноемножество вершин в ортогональной плоскости разбивается на триады в соответствиис расположением вершин на координатной плоскости. Далее происходит построениеДШ для каждой из триад методом горизонтальных или вертикальных столбов (методопределяется случайным образом). Ген в хромосоме будет содержать информацию ободной из триад: номера вершин, вид столба (горизонтальный/вертикальный) и номервершины, через которую проходит столб.
На следующемэтапе проводим отбор. Две хромосомы, имеющие наименьшее значение целевойфункции (суммарной длины ребер) будут участвовать в воспроизводстве далее.Следующим этапом, к отобранным хромосомам применим модифицированный точечныйоператор кроссинговера (точечный оператор кроссинговера). Получение потомковполучается путем замены одного из генов родителей (например, третий ген первогородителя становится на место третьего гена второго родителя, а тот в своюочередь на место первого родителя, в результате, получив двух потомков).Повышение эффективности алгоритма достигается за счет введения в процедурупоиска оператора мутации, транслокации и рекомбинации.
Оператормутации случайно выбирает ген в хромосоме и обменивает его на рядомрасположенный ген.
В процессетранслокации случайным образом производится разрыв в каждой хромосоме вопределенном для обеих хромосом месте. При формировании потомка берется леваячасть до разрыва из одного родителя и инверсия правой части до разрыва извторого родителя. В процессе рекомбинации в результирующую популяциюдобавляются хромосомы являющиеся родителями на этапах кроссинговера, мутации итранслокации. Далее производится элитная селекция. Отбираются две наилучшиехромосомы. В случае, если критерий остановки не достигнут, процедураоптимизации повторяется. Критерием остановки является количество популяций,определяемое пользователем.
Применение ГАдля решения задачи построения ДШ дает, возможно, не самый лучший результат, но,при соответствующем подборе генетических операторов, он может быть достаточнохорошим. Главное достоинство применения генетических алгоритмов – относительнонебольшое время решения. Особенно это важно в условиях очень большого числаабонентов сети, которое постоянно растет, и изменяющихся сетях (их конфигурациии стоимости услуг).3.8Результат работы алгоритма
В итогеработы второго этапа алгоритма построения маршрута должна быть полученаструктура (маршрут рассылки), соответствующая конкретному случаю. Т.е.определены связи, ведущие к нужным абонентам и затрачивающие на это минимумресурсов. В этом случае могут использоваться соединения между абонентами, минуяпромежуточные узлы, к тому же не всегда в рассылке должны быть задействованывсе абоненты.
Примерполученного маршрута для схемы сети, представленной на предыдущем этапе,показан на рисунке 3.9.
/>/>
Рисунок 3.9 –Пример построенного маршрута рассылки

Здесь болеетемным цветом показаны задействованные связи, обычным цветом – связисуществующие, но не участвующие в данной рассылке.
/>4 РЕАЛИЗАЦИЯ АЛГОРИТМА4.1Постановка задачи разработки программного продукта
Задачаразработки программного продукта состоит в том, чтобы он предоставлялнеобходимые возможности. А именно:
– возможностьсоздания и редактирования сети, т.е. добавление и удаление узлов и связей;
–визуализация схемы построенного маршрута;
– выводрезультатов расчетов для пересылки по построенному маршруту;
– возможностьнастраивать параметры алгоритма для получения наиболее оптимального результата;
–предоставление необходимой информации о программе и правилах работы с ней(помощь);
– удобныйпользовательский интерфейс.
С учетом современныхтехнических средств, программа должна иметь графический интерфейс,представляемый на цветном дисплее, совместимость с операционной системой Windows, удобную работу склавиатурой и мышью.
Структура ППдолжна учитывать все перечисленные выше технические и функциональныетребования.
Сложностьгенетических алгоритмов при решении задачи Штейнера состоит в кодировкеисходных данных. В то же время эта кодировка не применима при созданииструктуры сети и ее отображении.
Учитываяспецифику выбранного подхода к решению задачи, нужно разработать удобныеструктуры данных для хранения элементов сети, их обработки в алгоритме и выводарезультатов.
4.2Описание структур данных
Как ужеговорилось ранее, для хранения данных в этой программе необходимо разработатьнесколько структур, в соответствии с процедурой обработки этих данных.
На этапесоздания структуры сети, т.е. добавления узлов и связей между ними, данныехранятся в двух отдельных массивах: массив узлов и массив связей. Эти массивыимеют различную структуру.
Структураузлов:
Point =record
x,y:integer;
t:boolean;
end;
Здесь x и y – координаты узла наплоскости сети, t – его тип (активный или неактивный).
Структура связей:
Link= record
b,e:byte;
t:boolean;
p:real;
end;
Поля b и e обозначают номера начальногои конечного узлов связи соответственно, t – тип связи(используется ли она в построенном маршруте), p – стоимостьпересылки данных по этой связи.
При такомвиде хранения данных можно было бы использовать вещественное представлениехромосом генетических алгоритмов. Но в этом случае хромосома должна бытьдвумерной, так как учитываются координаты х и у. В то же время такие хромосомыпредполагали бы изменение координат, т.е. имеющиеся узлы в большинстве своем небудут задействованы. Поэтому предполагается совмещать вещественноепредставление хромосом с традиционным. Точки Штейнера могут быть добавлены,поэтому для них допустимо использовать вещественные хромосомы. Для заданныхузлов следует работать с их номерами. Целевая функция должна будет объединять всебе обработку этих двух типов хромосом.
Конкретныймеханизм совмещения обработки и представления хромосом будет разработан всоответствии с выбранным алгоритмом.4.3Настройки алгоритма
Дляпрактического применения алгоритма следует учитывать особенности каждойконкретной ситуации. С помощью программы можно воссоздать структуру любойреальной сети, задать ее параметры (например, стоимость каждой связи),расположить и связать узлы сети в соответствии с действительностью.
При этом дляразных ситуаций могут быть оптимальными разные настройки алгоритма. За счеттого, что генетические алгоритмы работают достаточно быстро, можно производитьпересчет маршрута с самыми различными настройками, подбирая наиболееоптимальный вариант.
В данном ППпредполагается предоставить такие возможности по настройке алгоритма построениямаршрута:
– выборметода отбора предков: равномерный, пропорциональный;
– выбороператора кроссинговера: одноточечный или двухточечный;
– выбороператора мутации: сколько генов будет изменяться и как будет происходить ихотбор;
– выборстепени элитизма: какой процент наилучших хромосом попадет в следующуюпопуляцию без изменения.
В результатеподбора различных настроек ПП поможет построить наиболее оптимальный маршрутдля конкретной ситуации.
ВЫВОДЫ
В даннойработе затронута актуальная на сегодняшний день тема дистанционного обучения.Его распространение в разные уголки страны позволит значительно повыситьуровень образования. И для того, чтобы сделать дистанционное обучение болеедоступным, разрабатывается этот проект.
Дляоптимизации построения сетей дистанционного обучения применяется множествометодов. В работе проведен анализ наиболее известных алгоритмов построенияструктуры сети. Предлагается разбить задачу на два этапа: определение общейструктуры и построение маршрута для определенной задачи. Строго математическиеметоды ограничены количеством абонентов. Для растущего числа студентовпостроение сети становится дорогим и длительным процессом, особенно учитываяскорость изменения самих сетей и их услуг. Поэтому существует тенденцияприменения эвристических методов решения данной задачи. Один из таких методов –генетические алгоритмы.
Эволюционноепрограммирование, частью которого есть ГА, является относительно новым идостаточно перспективным направлением среди методов решения подобных задач.Существуют большие возможности по усовершенствованию методов и соответственнорезультатов.
В конечномитоге этой реализацией станет программный продукт, который позволит нагляднопредставить результаты работы алгоритма, применить его для реальных сетейдистанционного обучения.

СПИСОКИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1.        ДюкВ., Самойленко А. Data Mining: учебный курс. – СПб: Питер, 2001. – 386с.
2.        КалашниковР.С. Построение дерева Штейнера методом генетического поиска // Перспективныеинформационные технологии и интеллектуальные системы. – 2005. – № 2 (22).
3.        КурейчикВ.М. Генетические алгоритмы. – Таганрог: изд-во ТРТУ, 1998. – 242 с.
4.        МаршаллУ. Берн, Рональд Л. Грэм Поиск кратчайших сетей. // Scientific American (изданиена русском языке). – 1989. – № 3. – С. 64–70.
5.        ПанченкоТ.В. Генетические алгоритмы: Учебно-методическое пособие / под ред. Ю.Ю.Тарасевича. – Астрахань: АГУ, 2007. – 87 с.
6.        РыженкоН.В. Алгоритм построения минимальных связывающих деревьев с дополнительнымивершинами (деревьев Штейнера) для случая прямоугольной метрики. Труды ИМВС РАН,2002.