Лекции 5-6. Расчет иерархической древовидной конфигурации сети (Электронные лекции), страница 2

Диагональный элемент записывается первымв упорядоченной матрице. Таким образом, при выполнении процедурыупорядочения должны выполняться следующие соотношения:̅̅̅̅̅∀ = ; ̅ 1 ∈ {} , , = 1,(4.8)̅̅̅̅̅∀ ≠ ; ̅ = mini [{m}j \ ⋃i mij ] , = 2,(4.9)где {} – j-й столбец матрицы М.̅Одновременно с получением j-го столбца {̅} упорядоченной матрицы Мформируется j-й столбец {к } матрицы номеров Мк, элементами которогоявляются порядковые номера элементов j-го столбца {} исходной матрицыМ, записанные в соответствии с расположением элементов в столбце {̅ } , т,е.если = ̅̅̅̅̅,то =b(4.10)Каждый j-й столбец суммарной матрицы МС получается в результатепоследовательного суммирования элементов столбца упорядоченной матрицы̅ т.е.М= ∑=1 ̅ (4.11)̅̅̅̅̅где , , = 1,В вычислительном блоке определения группы последовательно выполняютсяследующие операции.1.

Просматривается i-я строка { } .отыскивается минимальный элемент: = min { } .суммарнойматрицыи2. Принимаем, что при элементе располагается центр Ц группы,содержащей в своем составе i узлов.3. По столбу с номером d матрицы номеров {к } определяем номерапервых i (по числу просмотренных строк в Мc ) узлов, входящих в группус центром, разместившимся в .4. Присваиваем i значение = 1 ( ∈ {к } ) .5. Проверяем для найденной группы, содержащей i узлов, ограничение (4.7).Если ограничение (4.7)выполняется, то j увеличивается на единицу, ипереходим к п. 1. Если ограничение (4.7) не выполняется, то принимаем вкачестве решения состав группы, найденный на шаге i -1.После того как состав группы определен (определены номера элементов,входящих в группу) и определено местоположение центра группы (номерстолбца, который соответствует минимальному значению { } ,, переходим кблоку вычеркивания, в котором всем элементам строк и столбцов исходнойматрицы М, номера которых соответствуют элементам, вошедшим в группу Грприсваивается значение ∞ .Далее, в соответствии с алгоритмом (рис.

4.2) проверяют, какое число группуровня получено (оператор 4) . В том случае, если найдена вторая ипоследующие группы, то переходят к этапу улучшения краевых точек.Этап улучшения краевых точек. Этот этап ставит своей целью осуществитьпоследовательный обмен наиболее удаленных элементов улучшаемой группы сэлементами соседних групп, которые наименее удалены от центра улучшаемойгруппы. Обеспечение компактности улучшаемой группы достигаетсякорректировкой в целях получения группы, имеющей односвязную областьопределения.Процедура эвристического этапа улучшения краевых точек начинаетсяпосле того, как найдено не менее двух групп, она включает в себя следующее:1.

Определение центров близлежаших групп {Ц′ }ℎ (оператор 5). Центрысгруппированных элементов уровня h принадлежат множеству, если расстояния{Цу,Цр } от центра Цу улучшаемой группы Гу (которая определена последней)до центров {Ц } ранее определенных групп меньше расстояния от Цу донаиболее удаленного элемента , принадлежащего улучшаемой группе Гу :Ц ∈ {Ц′ }ℎ , если Цу,Цр < Цу,(4.12)2. Определение центра Ц∗ , наименее удаленного от (оператор 6). Элементмножества {Ц′ }ℎ принадлежит множеству {Ц′′ }ℎ , если расстояние Ц′ меньшерасстояния Цу :Ц ∈ {Ц′′ }ℎ , если Ц′ < Цу(4.13)Наименее удаленный центр Ц∗ соответствует такому элементу множества{Ц′′ } , у которого наименьшее значение Ц′′ :ℎЦ∗ = Ц∗ , если = min{Ц′′} Ц′′(4.14)3.

Определение элемента ′ , заменяющего (оператор 7). Элемент ,принадлежащей группе с центром Ц∗ может заменять в улучшаемой группеГу , если расстояние Цу , является наименьшим из всех элементов группы сцентром Ц∗ , т.е. ≔ , если ′ ∈ Гу , ∈ Г∗Ц ;Цу = min∈Г∗ ЦуЦ(4.15)4. Проверка групп ГЦу и Г∗Ц на ограничение по производительности состоитв проверке выполнения ограничения (4.7) на пропускную способность узловдля обеих групп (оператор 5).Если ограничение (4.7) выполняется, то состав групп ГЦу и Г∗Цкорректируется путем взаимного обмена элементов и ;.

Если ограничение(4.7) не выполняется, делается попытка определить следующий элемент ;. изГ∗Ц , используя пп. 3 и 4, затем проверяются все группы, принадлежащиемножеству {Ц"} .Решение по второму этапу продолжается до тех пор, пока все группы,принадлежащие множеству {Ц"} , не будут проверены.После определения групп уровня h переходят к определению групп уровняh+1 (оператор 9). В начале расчета корректируется исходная матрица Мℎ(оператор 10), в которой остаются столбцы и строки, соответствующиенайденным центрам групп уровня h, а также оценивается каждый центр группыпутем суммирования оценок элементов, входящих в соответствующую группу.Процедура расчета завершается, если на уровне H формируется только однагруппа (оператор 11).Изложенная методика использует принцип целенаправленного поиска,обеспечивающий получение решения в точке локального оптимума целевойфункции, которое затем корректируется эвристической процедурой улучшениякраевых точек.

Проведенные исследования [18] показали, что процедураобеспечивает среднюю точность расчета 5%, что соизмеримо с точностьюисходных данных.Пример 4.3Даны узлы (N=9), заданы взвешенные расстояния, представленные в матрицеМ на рис. 4.3.121010 24 21 45 65 60 55 100210 0324 15 0М= 4345678915 11 35 55 50 48 9025 50 70 75 60 10021 11 25 025 45 40 35 60545 35 50 25 040 30 26 70665 55 70 45 40 0760 50 75 40 30 12 0855 48 60 35 26 30 18 09100 90 100 60 70 40 28 40 012 30 4018 2840Рис. 4.3 Матрица М взвешенных расстоянийТребуется построить древовидную иерархическую сеть минимальной длины,обеспечивающую многоуровневое покрытие исходных узлов.

Например, так,как показано на рис. 4.4.Рис. 4.4. Древовидная иерархическая структураИтак, исходные данные для расчета следующие: N=9; количество узлов, zi=1;веса узлов, которые равны количеству информации, передаваемой узлом заединицу времени i  1,9 ,Пh=1=3; пропускные способности центров групп h=1;Пh=2=9, пропускные способности центров групп h=2.Алгоритм решения состоит из двух этапов:определение группы (центр, состав, число элементов),улучшение группы путём обмена наиболее удалённых её элементовс элементами соседних групп.Решение:Определение группы1) Производим преобразование исходной матрицы М и из исходнойматрицы получаем три: M , MK, MC.M (каждыйУпорядоченная матрицастолбец исходной матрицыупорядочивается по возрастанию) представлена на рис. 4.5M1234567891000000000210 10 15 11 25 12 12 18 28321 11 24 21 26 30 18 26 40424 15 25 25 30 40 28 30 40545 35 50 25 35 40 30 35 60655 48 60 35 40 45 40 40 70860 50 70 40 45 55 50 48 90 Рис.

4.5Упорядоченная65 55 75 45 50 65 60 55 100 матрица M9100 90 100 60 70 70 75 60 1007Рис. 4.5 Упорядоченная матрица MПри равенстве взвешенных расстояний элементов, меньшим принимаетсяэлемент с меньшим номером по строке.В матрицу MK номеров записываются порядковые номера элементов,переставленных при формировании упорядоченной матрицы M упорядоченииэлементов, как представлено на рис. 4.6.1 2 3 4 5 6 7 8 911 2 3 4 5 6 7 8 922 1 2 2 4 7 6 7 734 4 1 1 8 8 8 5 643 3 4 3 7 5 9 6 8МК 55 5 5 5 2 9 5 4 468 8 8 8 6 4 4 9 577 7 6 7 1 2 2 2 286 6 7 6 3 1 1 1 199 9 9 9 9 3 3 3 3Рис.

4.6 Матрица MK номеровСуммарная матрица MC, получается путем последовательного суммированияэлементов столбца упорядоченной матрицы, представлена на рис. 4.7.С1234567891000000000210 10 15 11 25 12 12 18 28331 21 39 32 51 42 30 44 68455 36 64 57 81 82 58 74 108М5100 71 114 82 116 122 88 109 1686155 119 174 117 156 167 128 149 2387215 169 244 157 201 222 178 197 3288280 224 319 202 251 287 238 252 4289380 314 419 262 321 357 313 312 528Рис.4.7 Суммарная матрица MC2) Находим состав группы.Просматриваем очередную строку i суммарной матрицы МС и ищемминимальный элемент j. Принимаем, что при этом элементе j располагаетсяцентр группы, состоящей (разумеется) из i узлов.Проверяем ограничение по пропускной способности: zi  Пh=1 или 2 (длясоответствующего уровня h).

Если ограничение выполняется, то увеличиваемномер строки i=i+1 и всё повторяем сначала. В противном случае оставляемсостав группы с предыдущего шага(i-1).В нашем примере задано найти три узла, входящие в группу. Поэтомудойдем до 3-й строки матрицы МС (zi=1, а Пh=1=3), в этой строке минимальнымявляется элемент m32=21.Центр группы располагается при 2-м узле (j=2).

Всего в группе три узла (i=3).По столбцу 2 матрицы номеров МК определяем номера узлов, входящих вгруппу Г1=2,1,4.Корректировка для первой группы не производится.3) Вычёркиваем строки и столбцы из исходной матрицы М с номерамиэлементов, входящих в группу. В данном случае это строки 1,2,4 и столбцы1,2,4. Получаем матрицу М(1), представленную на рис. 4.8.353050 70 75 60 100550 0М(1) 6678940 30 26 7070 40 012 30 40775 30 12 018 28860 26 30 18 09100 70 40 28 40 040Рис. 4.8 Скорректированная матрица М(1),4) Если число групп > 1, переходим к следующему этапу (улучшениегруппы), иначе к шагу 1.В рассматриваемом примере имеем одну группу и опять из исходнойматрицы М(1) формируем три матрицы: упорядоченная M (1) матрица, матрицаМК(1) и суммарная матрица МС(1)M (1)3567893567893 0000003 0000005 50 26 12 12 18 285 50 26 12 12 18 286 60 30 30 18 26 40МС(1) 6 110 56 42 30 44 687 70 40 40 28 30 407 180 96 82 58 74 1088 75 50 40 30 40 708 255 146 122 88 114 1789 100 70 70 75 60 1009 355 216 192 163 174 278Рис.

4.9 Матрица M (1)Рис. 4.10 Матрица МС(1)3 5 6 7 8 933 5 6 7 8 955 8 7 6 7 768 7 8 8 5 676 6 5 9 6 887 3 9 5 9 599 9 3 3 3 3Рис. 4.11 Матрица МК(1)Далее согласно п. 2 определяем группу. Минимальный элемент m67=30.Следовательно, центр группы при 7-м узле, а состав группы Г2=7,6,8.5) Проверяем необходимость корректировки группы Г2=7,6,8Центр улучшаемой группы Гу = Г2 расположен при узле 7. Узлы 6,8 должныкорректироваться, если расстояние от корректируемого узла до центраулучшаемой группы Гу больше расстояния от корректируемого узла до центрагруппы Г1 при узле 2, из которой может выделяться узел, который участвует вкорректировке, т.е. в рассматриваемом примере для корректируемых узлов 6 и8 должны соответственно выполняться условия: m87 > m82 либо m67 > m62По матрице номеров МК, представленной на рис. 4.6, анализируемсоответственно столбцы 8 и 6, как представлено на рис.

4.12.6 816 827 738 545 659 464 972 281 193 3Рис. 4.12. Столбцы матрицы МК номеровВ каждом из этих столбцов узлы 6 и 8находятся выше узла 2. Это означает,что центр Г2 при узле 7 расположен к рассматриваемым узлам 6 и 8 ближе, чемцентр Г1 , расположенный при узле 2. Поэтому корректировку Г2 производитьне следует.6) Находим следующую группу. После вычёркивания из матрицы М(1) строки столбцов, номера которых соответствуют номерам узлов, входящих в Г 2,получаем матрицу М(2), представленную на рис.4.13.3М(2)5305055009100 709100700Рис. 4.13 Скорректированная матрица М(2)Аналогично п.1, формируем три матрицы: упорядоченную матрицу M ( 2) ;матрицу номеров МК(2), суммарную матрицу МС(2).3593 5930005935933 59300050 50 7055 35550 50 70100 70 10099 939150 120 170Рис. 4.14 Матрица M ( 2) Рис.