Главная

Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






АЛГОРИТМИ ПОШУКУ ШЛЯХІВ В МЕРЕЖАХ


Основне призначення мережі зв'язку полягає в тому, щоб надавати абонентам сполучні шляхи для передачі повідомлень відповідно до адрес і необхідних якісних показників (якістю обслуговування, швидкістю передачі, надійністю і т. д.); при цьому вибір сполучних шляхів повинен здійснюватися так, щоб забезпечити найефективніше використання устаткування мережі, мінімально можливу довжину шляхів, число транзитних ділянок в шляхах, необхідне число каналів в шляхах і т.д. [6].

При розв’язанні різних задач аналізу і синтезу мереж зв'язку виникає необхідність в пошуку безлічі шляхів, існуючих між заданою парою вузлів мережі (вершин графа). Всі методи пошуку безлічі шляхів в мережі можна розділити на два класи - матричні і мережеві. Матричні методи засновані на перетворенні різних матриць - топологічних або матриць характеристик ребер графа, мережеві - на привласненні вершинам графа деяких позначень, які називають позначками (або індексами).

2.1Алгоритми пошуку безлічі шляхів

2.1.1. Матричні алгоритми пошуку безлічі шляхів

Розкладання булевого визначника структурної матриці В. Якщо в мережі є можливість передачі інформації з вузла i у вузол j (по прямих каналах або через проміжні вузли), то говорять, що існує зв'язок від i до j . Для здійснення зв'язку повинен існувати відповідний шлях або шляхи.

Введемо наступні позначення: µij - шлях з вузла i у вузол j (з вершини i у вершину j графа); mij - безліч шляхів з i в j .

Шлях µij - це впорядкований набір ребер, його складових.

Довжина шляху µij - Lij- це сума довжин lxy ребер, його складових:

 

Lij =

Ранг шляху R ij -число ребер, утворюючих шлях.

Для графа, зображеного на рис. 2.1, для шляху µ14 = а12, а25, а53, а34 ранг R14 = 4, для шляху µ14 = а14 ранг R14= 1, для шляху µ14 = а12, а23, а34 ранг R14 = 3.

Структурна матриця графа рис. 2.1, представлена в табл. 2.1, може розглядатися як булева матриця, оскільки її елементами є булеві змінні. Дійсно, будь-який елемент матриці В - це змінна, її інверсія, константи 0 або 1. Таким чином, шлях як послідовність ребер може бути представлений кон’юнкцією (логічним множенням) ребер, його складових.

 

 

Таблиця 2.1 – Структурна матриця графа, зображеного на рис. 2.1

 

В =

Рисунок 2.1 – Зображення графа структурної матриці табл. 2.1

Розглянуті шляхи µ14 запишемо у формі

 

µ14 = agfc, µ14 =h, µ14 =abc .

Безліч шляхів можна записати в диз'юнктивній нормальній формі, застосувавши операцію диз'юнкції (логічного складання) до шляхів, що становлять множину.

Так, в даному прикладі

 

m14 = agfc + h + abc .

Тут для позначення логічного множення і складання застосовуються символи алгебраїчного множення і складання . Окрім вказаних символів, використовуються також символи: ٨ - для позначення кон'юнкції, ٧ - для позначення диз'юнкції.

 

Безліч шляхів mij може бути одержане розкладанням визначника матриці В, з якої заздалегідь викреслюється стовбець з номером i і рядок з номером j ,тобто [7]:

(2.1)

Розкладання визначника матриці В іj проведено по рядку з номером k. Розкладання (2.1) можна проводити по будь-якому рядку (стовбцю). Тут В іj - матриця, одержана з початкової структурної матриці після викреслювання i -го стовпця і j -го рядка.

У стовпцях кожної вершини графа записані ребра, що в неї входять; у рядках кожної вершини графа записані ребра, які виходять з вершини.

Викресливши стовпець i і рядок j, ми тим самим виключимо ті ребра, які не можуть утворювати шляхів множини mij. |Вkl |- визначник, одержаний з det В іj після викреслювання k -го рядка і 1-го стовпця.

Розкладання визначника(2.1) слід проводити за відомими правилами лінійної алгебри, проте операції алгебраїчного множення і складання замінюються на операції логічного множення і складання, відповідно.

При перетворенні матриці і визначників слід використовувати основні правила і закони булевої алгебри :

 

1) 1 + а = 1; 1·а = а;

2) 0 + а= а; 0·а = 0;

3) а + а = 1; а · а = 0;

4) а + а = а; а·а = а - закон повторення;

5) а + ab = а - закон поглинання;

6) (а + х) · (а + у) = а + ху - розподільний закон.

 

При розкладанні булевих визначників необхідно також користуватися наступними правилами:

1) визначник, що має одиницю в кожному рядку і стовпці, тотожно рівний одиниці;

2) якщо який-небудь рядок або стовпець складається з нулів, то визначник тотожно рівний нулю;

3) якщо перед визначником записаний множник «а», то всі елементи «а» у визначнику можна замінити на «1», а всі елементи «а» у визначнику можна замінити на «0»;

4) якщо у визначнику поміняти місцями два рядки або два стовпці або виробити його транспонування, то значення визначника не зміниться.

Розглянемо отримання безлічі шляхів m14 з матриці В (див. табл 2.1):

 

m14 = det В іj =

Розкладання визначника проведемо по стовпцю з номером 4:

 

m14 =

Упорядкуємо одержані шляхи по рангу, врахувавши послідовність ребер в шляхах. Одержимо:

 

m14 =

 

Той же результат одержимо, розклавши визначника, наприклад, по першому рядку:

 

m14 =

 

 

Зведення структурної матриці В в степінь. Початкова структурна матриця В є матрицею прямих зв'язків, тобто в ній записані всі шляхи першого рангу, існуючі в графі. При зведенні матриці в квадрат кожен її елемент представлятиме безліч шляхів до другого рангу включно, існуючих між вершинами i і j . Зведення матриці В в степінь Rmax= n - 1 приводить до отримання всіх шляхів, існуючих між кожною парою (і, j)вершин графа, тобто

 

 

Тут n - число вершин графа, Rmax - максимально можливий ранг шляхів в графі. Rmax = n - 1 у разі, коли який-небудь шлях проходить через всі вершини графа.

При зведенні матриці в степінь користуються відомими правилами лінійної алгебри:

 

В(2) = В(1) · В(1) ,

В(3) = В(2) · В(1) і т.д.

 

Елемент матриці-співмножників С = A· D в лінійній алгебрі одержують відповідно до виразу

 

(2.2)

n- загальний розмір матриць А і D (число стовпців матриці А і рядків матриці D, у разі зведення квадратної матриці B в степінь n- число вершин).

Оскільки матриця В - булева, зведення її в степінь здійснюється з використанням законів і тотожностей булевої алгебри. Крім того, у виразі (2.2) операції алгебраїчного множення і складання замінюються на операції логічного множення і складання, відповідно. При зведенні матриці В в степінь q кожен елемент bij (q) матриці В(q) обчислюється за наступними правилами:

1)елементи і-го рядка матриці В(q-1) логічно умножаються на відповідні елементи j-го стовпця матриці В(1);

2) одержані логічні співмножники логічно складаються, утворюючи шукане значення елементу bij (q) . Якщо при зведенні в деяку степінь q виявиться, В(q) = В(q-1) обчислення слід припинити. При цьому В(q) = В(q-1) = В(Rmax) .

Покажемо процес отримання матриці B(2) для графа рис. 2.1, матриця В якого представлена в табл. 2.1.

Для отримання елементу необхідно використовувати елементи першого рядка і другого стовпця матриці В(1) :

 

= − I рядок В(1) ─ II рядок В(1)

Аналогічно одержимо решту елементів матриці B(2) :

 

і т.д.

Одержані результати зведемо в матрицю B(2) (табл 2.2)

Таблиця 2.2 – Матриця B(2)

З порівняння B(2) іB(1) (табл.2.2 і 2.1) витікає, що одержана матриця B(2) не є результуючою, оскільки B(2)B(1) і процес обчислень слід продовжувати, а саме:

1. Обчислити B(3) =B(2) · B(1).

2. Якщо B(3)= B(2) ,то B(3)= В(Rmax) , результат одержаний.

Якщо B(3)B(2) , продовжити обчислення, тобто одержати B(4)

Оскільки Rmax = 4 для даного графа мережі, матриця буде результуючою у будь-якому випадку, навіть якщо B(4)B(3).

У одержаній результуючій матриці В(Rmax) ,як указувалося раніше, кожен елемент bij(Rmax) = mij ,тобто визначає множену всіх шляхів з вершини i у вершину j.

Так,

і т.д.

2.1.2. Мережевий алгоритм пошуку безлічі шляхів

Мережеві методи визначення множини шляхів між заданими вузлами мережі являються графічним еквівалентом матричних методів

Визначення безлічі шляхів засноване на побудові дерева шляхів з фіксованої вершини-витоку (коріння дерева ) у всю решту вершин-стоків графа. Мережеві методи визначення множини шляхів між заданими вузлами мережі являються графічним еквівалентом матричних методів.

Для побудови дерева шляхів необхідно перш за все відзначити «яруси» дерева. На ярусі R = 0 поміщається вершина-виток - «корінь» дерева. На ярусі R = 1 розташовуються вершини, суміжні вершині-витоку, тобто вершини, шляхи в які з вершини-витоку мають ранг, рівний одиниці .На ярусі R = 2 розташовуються вершини, суміжні вершинам, розташованим на ярусі R = 1, і т.д.

При записі вершин на ярус R = 2 і подальші яруси необхідно стежити за тим, щоб шляхи рангів, що утворюються, 2, 3 і т.д. були простими (самонепересічними), тобто щоб жодна вершина в шляху не повторювалася більше одного разу.

Максимальне значення ярусу (рангу шляху) Rmaх = n-1 (n -число вершин графа).

Дерево шляхів містить всі шляхи з фіксованої вершини-витоку у всю решту вершин. При цьому на ярусі 1 містяться всі шляхи першого рангу, на ярусі 2 – всі шляхи другого рангу і т.д.

Таким чином, на деякому k-му ярусі міститься інформація про всі шляхи k -гo рангу з фіксованої вершини-витоку графа у всю решту вершин.

Для графа рис. 2.1 побудуємо дерево шляхів з вершини 1. Дана вершина є корінням дерева і поміщається на нульовий ярус .Значение рангу шляху тут R = 0. На перший ярус R= 1 поміщаються вершини 2, 4, 5, що мають безпосередній зв'язок з вершиною 1. Далі на другий ярус від вершини 2 поміщаються вершини, пов'язані з вершиною 2, а саме 3 і 5. Вершина 1 виключається з розгляду, оскільки шлях у вершину 2 пройшов через вершину 1.

Від вершини 4 на другий ярус записуються вершини 3 і 5, від вершини 5-вершини 4 і 3. Аналогічно записуються вершини на решту ярусів дерева.

Побудоване дерево для вершини-витоку 1 представлене на рис. 2.2. Як видно, в дереві є три шляхи першого рангу (R=1): а, h, e; шість шляхів другого рангу (R = 2):

ab, ag, hс, hd, e , e , на третьому ярусі (R = 3) записані шляхи третього рангу: ab , abc, ag , ag , hc , hсf, hd , e , e c, e . Нарешті, шляхичетвертого рангу (R = 4): ab , abсd, ag с, ag , hс g, hd b, e .

Звичайно, з дерева можна одержати безліч шляхів з фіксованої вершини в будь-яку вершину графа послідовним переглядом ярусів дерева. Так,



Последнее изменение этой страницы: 2016-06-10

headinsider.info. Все права принадлежат авторам данных материалов.