Методи маршрутизації на прикладі таблиці маршрутів

ЗМІСТ

• ВСТУП
• 1. РОЗРОБКА СИСТЕМИ ПІДТРИМКИ ПРИЙНЯТТЯ РІШЕНЬ (СППР) ДЛЯ ПРОЕКТУВАННЯ КОМП’ЮТЕРНОЇ МЕРЕЖІ
• 1.1 Нечітка логіка
• 1.2 Розробка нечіткої експертної системи, що діє на основі алгоритму Мамдані для 2-х умов
• 1.3 Вибір маршрутизатора і опис його характеристик
• 2. РОЗРАХУНОК ОПТИМАЛЬНОГО МАРШРУТУ
• 2.1 Матричний алгоритм пошуку найменших шляхів
• 2.2 Програма роботи алгоритму в Microsoft Excel
• 3 РОЗРОБКА НЕЙРОМЕРЕЖНОГО АЛГОРИТМУ
• 3.1 Основні характеристики штучних нейронних мереж
• 3.2 Методи навчання штучних нейронних мереж
• 3.3 Розробка програми навчання нейронної мережі на основі таблиць маршрутизації в пакеті Microsoft Excel
• ВИСНОВКИ
• СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ

ВСТУП

Найважливіша особливість нейронної мережі, яка свідчить про її широкі можливості і величезний потенціал, полягає в паралельній обробці інформації всіма ланками. При величезній кількості міжнейронних зв’язків це дозволяє значно прискорити процес обробки інформації. У багатьох випадках стає можливим перетворення сигналів в реальному часі. Крім того, при великому числі міжнейронних з'єднань мережа набуває стійкість до помилок, що виникають на деяких лініях. Функції пошкоджених зв’язків беруть на себе справні лінії, в результаті чого діяльність мережі не зазнає суттєвих втрат.

Інша не менш важлива властивість — здатність до навчання та узагальненню накопичених знань. Нейронна мережа має риси штучного інтелекту. Натренована на обмеженій множині даних мережа здатна узагальнювати отриману інформацію і показувати хороші результати на даних, що не використовувалися в процесі навчання.

Характерна особливість мережі полягає також у можливості її реалізації із застосуванням технології надвеликого ступеня інтеграції. Різниця елементів мережі невелика, а їх повторюваність величезна. Це відкриває перспективу створення універсального процесора з однорідною структурою, здатного обчислювати різноманітну інформацію.

Використання перерахованих властивостей на тлі розвитку пристроїв з надвеликим ступенем інтеграції (VLSI) і повсюдного застосування обчислювальної техніки викликало в останні роки величезне зростання інтересу до нейронних мереж і істотний прогрес в їх дослідженні. Створено базу для вироблення нових технологічних рішень, що стосуються сприйняття, штучного розпізнавання та узагальнення відеоінформації, управління складними системами, обробки мовних сигналів і т. п. Штучні нейронні мережі в практичних додатках, як правило, використовуються в якості підсистеми управління або вироблення рішень, що передає виконавчий сигнал іншим підсистемам, які мають іншу методологічну основу. Функції, що їх мережами, підрозділяються на кілька груп: апроксимація; класифікація і розпізнавання образів; прогнозування; ідентифікація та оцінювання; асоціативне управління.

В даному курсовому проекті будуть розглянуті та вивчені традиційні методи маршрутизації на прикладі таблиці маршрутів.

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

Маршрутизація — процес визначення маршруту проходження інформації в мережах зв’язку між вузлами. Маршрути можуть задаватися адміністративно, або обчислюватися за допомогою алгоритмів маршрутизації, базуючись на інформації про топологію і стан мережі, отриманої за допомогою протоколів маршрутизації.

Послідовність процедур та (чи) етапів проектування називають маршрутом проектування. У залежності від того, у якій послідовності виконуються процедури й етапи, розрізняють два способи проектування (два типи маршрутів) — спадне (зверху вниз) та висхідне (знизу вверх) проектування.

Комп’ютерна мережа — це сукупність безлічі складових, яка являє собою складну структуру з компонентів та вузлів. Для створення комп’ютерної мережі важливо провести велику підготовчу роботу, встановити які функції і завдання вона має виконувати, вибрати топологію мережі, середовище і протоколи передачі даних. Така інформація дозволить вибрати способи реалізації мережі та розрахувати вартість. Тому важливим етапом у створенні комп’ютерної мережі є її проектування. Тільки добре спроектована і продумана комп’ютерна мережа дозволить уникнути максимально більшу кількість проблем.

Алгоритми маршрутизації застосовуються для визначення найкращого шляху пакетів від джерела до приймача і є основою будь-якого протоколу маршрутизації. Для формулювання алгоритмів маршрутизації мережа розглядається як граф. При цьому маршрутизатори є вузлами, а фізичні лінії між маршрутизаторами — ребрами відповідного графа. Кожній грані графа присвоюється певне число — вартість, що залежить від фізичної довжини лінії, швидкості передачі даних по лінії або фінансової вартості лінії.

Їх можна розділити на алгоритми пошуку множини шляхів і алгоритми пошуку найкоротших шляхів, а вони в свою чергу діляться на матричні і мережеві алгоритми.

До алгоритмів пошуку множини шляхів відносять:

— розкладання булевого визначника структурної матриці графа і зведення її до ступеня;

— побудови дерева шляхів з фіксованою вершиною — джерела.

До алгоритмів пошуку найкоротших шляхів відносять:

— зведення в ступінь максимального рангу матрицю довжин;

— алгоритм Флойда;

— алгоритм Дейкстри;

— ефективний алгоритм «трьох відміток».

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

Основні проблеми, які вирішуються штучними нейронними мережами:

— класифікація образів;

— кластеризація / категоризація;

— апроксимація функцій;

— передбачення / прогноз;

— оптимізація.

1. РОЗРОБКА СИСТЕМИ ПІДТРИМКИ ПРИЙНЯТТЯ РІШЕНЬ (СППР) ДЛЯ ПРОЕКТУВАННЯ КОМП’ЮТЕРНОЇ МЕРЕЖІ

Система підтримки прийняття рішень (СППР) (англ. Decision Support System, DSS) — комп’ютерна автоматизована система, метою якої є допомога людям, що приймають рішення в складних умовах для повного і об'єктивного аналізу предметної діяльності. СППР виникли в результаті злиття управлінських інформаційних систем і систем управління базами даних.

Для аналізу та виробок пропозицій в СППР використовуються різні методи. Це можуть бути: інформаційний пошук, інтелектуальний аналіз даних, пошук знань в базах даних, міркування на основі прецедентів, імітаційне моделювання, еволюційні обчислення і генетичні алгоритми, нейронні мережі, ситуаційний аналіз, когнітивне моделювання та ін. Деякі з цих методів були розроблені в рамках штучного інтелекту. Якщо в основі роботи СППР лежать методи штучного інтелекту, то говорять про інтелектуальну СППР або ІСППР.

До інформаційних систем нового покоління належать системи підтримки прийняття рішень (СППР) та інформаційні системи, побудовані на штучному інтелекті (інтелектуальні АС).

СППР — це інтерактивна комп’ютерна система, яка призначена для підтримки різних видів діяльності при прийнятті рішень із слабоструктурованих або неструктурованих проблем. Інтерес до СППР, як перспективної галузі використання обчислювальної техніки та інструментарію підвищення ефективності праці в сфері управління економікою, постійно зростає. У багатьох країнах розробка та реалізація СППР перетворилася на дільницю бізнесу, що швидко розвивається.

Штучний інтелект — це штучні системи, створені людиною на базі ЕОМ, що імітують розв’язування людиною складаних творчих завдань. Створенню інтелектуальних інформаційних систем сприяла розробка в теорії штучного інтелекту логіко-лінгвістичних моделей. Ці моделі дають змогу формалізувати конкретні змістовні знання про об'єкти управління та процеси, що відбуваються в них, тобто ввести в ЕОМ логіко-лінгвістичні моделі поряд з математичними. Логіко лінгвістичні моделі - це семантичні мережі, фрейми, продукувальні системи — іноді об'єднуються терміном «програмно-апаратні засоби в системах штучного інтелекту».

Розрізняють три види інтелектуальних АС:

1) інтелектуальні інформаційно-пошукові системи (системи типу «запитання — відповідь»), які в процесі діалогу забезпечують взаємодію кінцевих користувачів — непрограмістів з базами даних та знань професійними мовами користувачів, близьких до природних;

2) розрахунково-логічні системи, які дають змогу кінцевим користувачам, що не є програмістами та спеціалістами в галузі прикладної математики, розв’язувати в режимі діалогу з ЕОМ свої задачі з використанням складаних методів і відповідних прикладних програм;

3) експертні системи, які дають змогу провадити ефективну комп’ютеризацію областей, у яких знання можуть бути подані в експертній описовій формі, але використання математичних моделей затруджене або неможливе.

В економіці України найпоширенішими є експертні системи. Це системи, які дають змогу на базі сучасних персональних комп’ютерів виявляти, нагромаджувати та коригувати знання з різних галузей народного господарства (предметних областей).

СППР виникли на початку 70-х років завдяки подальшому розвитку управлінських інформаційних систем (ІС) і являють собою системи, розроблені для підтримки процесів прийняття рішень менеджерами в складних ситуаціях, пов’язаних із розробкою і прийняттям рішень. На розвиток СППР істотний вплив зробили вражаючі досягнення в галузі інформаційних технологій, особливо в галузі телекомунікаційних мереж, ПЕВМ, динамічних електронних таблиць, експертних систем. Термін СППР (DSS — Decision Support System) виник у 70-х роках і належить Геррі та Мартону, хоча перше покоління СППР мало чим відрізнялося від традиційних управлінських інформаційних систем, і тому замість СППР часто використовувався термін «системи управлінських рішень».

Дотепер немає єдиного визначення СППР. Наприклад, деякі автори під СППР розуміють «інтерактивну прикладну систему, що забезпечує кінцевим користувачам, що приймають рішення, легкий і зручний доступ до даних і моделей із метою прийняття рішень у ситуаціях різних галузей людської діяльності.

Нарешті, існує твердження, відповідно до якого СППР являє собою специфічний клас систем, що добре описується, на базі ПЕВМ.

Така розмаїтість визначень СППР відображає широкий діапазон різних форм, розмірів, типів СППР. Але практично усі види цих комп’ютерних систем характеризуються чіткою структурою, що включає 3 головних компонента:

— підсистему інтерфейсу користувача;

— підсистему керування базами даних (СУБД);

— підсистему керування базою моделі.

Специфічні особливості й основи побудови цих компонентів забезпечують у СППР реалізацію ряду важливих концепцій побудови ІС: інтерактивність, інтегрованість, потужність, доступність, гнучкість, надійність, керуємість.

Аналіз еволюції систем СППР дає можливість виділити 2 покоління СППР:

— перше покоління розроблялося в період із 1970 до 1980 р.;

— друге — з початку 1980 р. і дотепер.

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

— керування даними — велика кількість інформації, внутрішні і зовнішні банки даних, обробка та оцінювання даних;

— керування обчисленням (моделюванням) — моделі, розроблені спеціалістами в галузі інформатики для спеціальних проблем;

— користувацькі інтерфейси (мова спілкування) — мови програмування, розроблені для великих ЕОМ, що використовуються винятково програмістами.

СППР другого покоління вже мають принципово нові ознаки:

— керування даними — необхідна і достатня кількість інформації про факти згідно з прийняттям рішень, що охоплюють сховані припущення, інтереси і якісні оцінки;

— керування обчисленням і моделюванням — гнучкі моделі, що відображають засіб мислення особи, приймаючої рішення, у процесі прийняття рішень;

— інтерфейс користувача — програмні засоби дружні користувачу;

— звична мова, безпосередня робота кінцевого користувача.

Ціль і призначення СППР другого покоління можна визначити так:

— допомога у розумінні розв’язуваної проблеми. Сюди належить структуризація проблеми, генерування постановок задач, визначення переваг, формування критеріїв;

— допомога у рішенні задач: генерування і вибір моделей і методів, збір і підготування даних, виконання обчислень, оформлення і видача результатів;

— допомога у проведенні аналізу типу «Що… Коли?» і т. п., пояснення ходу рішення;

— пошук і видача аналогічних рішень у минулому і їхні результати.

Дружні людині СППР дають можливість вести рівноправний діалог із ПЕВМ, використовуючи звичайні мови спілкування. Системи можна підбудовувати під стиль мислення користувача, його знань і фахової підготовки, а також під засоби роботи.

Для сучасних СППР характерно наявність таких характеристик.

СППР дає керівнику допомогу у процесі прийняття рішень і забезпечує підтримку у всьому діапазоні контекстів задач. Думка людини та інформація, що генерується ЕОМ, являють єдине ціле для прийняття рішень СППР підтримує і посилює (але не змінює і не відміняє) міркування та оцінку керівника. Контроль залишається за людиною. Користувач «почуває себе комфортно» і «як удома» у системі.

СППР підвищує ефективність прийняття рішень. На відміну від адміністративних систем, де робиться акцент на аналітичному процесі, у СППР важливійшою є ефективність процесу прийняття рішень.

СППР виконує інтеграцію моделей і аналітичних методів із стандартним доступом до даних і вибіркою з них. Для надання допомоги при прийнятті рішень активується одна або декілька моделей. Вміст БД охоплює історію поточних і попередніх операцій, а також інформацію зовнішнього характеру та інформацію про середовище.

СППР проста в роботі для осіб, що мають досвід роботи з ЕОМ.

Системи дружні для користувачів не потребують глибоких знань про обчислювальну техніку і забезпечують просте пересування по системі.

СППР побудовані за принципом інтерактивного рішення задач. Користувач має можливість підтримувати діалог із СППР у безперервному режимі.

СППР орієнтована на гнучкість і адаптивність для пристосування до змін середовища або підходів до рішення задач, що обирає користувач. Керівник повинен пристосуватися до змінюваних умов сам і відповідно підготувати систему.

СППР не повинна нав’язувати користувачу визначеного процесу прийняття рішень.

Користувач повинен мати вибір можливостей, щоб вибирати їх у формі і послідовності, що відповідають стилю його пізнавальної діяльності - стилю «моделей, що подаються».

СППР вирішує два основні завдання:

— вибір найкращого рішення з безлічі можливих (оптимізація);

— впорядкування можливих рішень по перевагу (ранжування).

Системи підтримки прийняття рішень:

— допускають, щоб користувачі управляли входом і виходом;

— забезпечують підтримку для рішень і проблем, які не можуть бути визначені заздалегідь;

— використовують складний аналіз та інструментальні засоби моделювання.

СППР мають велику аналітичну потужність, ніж інші системи:

— вони побудовані з низкою моделей, щоб аналізувати дані;

— системи СППР інтерактивні;

— користувач може змінювати припущення і включати нові дані.

1.1 Нечітка логіка

Нечітка логіка (англ. fuzzy logic) — розділ математики, що є узагальненням класичної логіки і теорії множин, базується на понятті нечіткої множини, вперше введеного Лотфі Заде в 1965 році як об'єкта з функцією приналежності елемента до безлічі, приймаючої будь-які значення в інтервалі [0, 1], а не тільки 0 або 1. На основі цього поняття вводяться різні логічні операції над нечіткими множинами і формулюється поняття лінгвістичної змінної, в якості значень якої виступають нечіткі множини.

Предметом нечіткої логіки вважається дослідження міркувань в умовах нечіткості, розмитості, схожих з міркуваннями в звичайному сенсі, та їх застосування в обчислювальних системах.

В даний час існує, принаймні, два основних напрямки наукових досліджень в області нечіткої логіки:

— нечітка логіка в широкому сенсі (теорія наближених обчислень);

— нечітка логіка у вузькому сенсі (символічна нечітка логіка).

Оскільки нечіткі множини описуються функціями належності, а — норми і - норми звичайними математичними операціями, можна уявити нечіткі логічні міркування у вигляді нейронної мережі. Для цього функції приналежності треба інтерпретувати як функції активації нейронів, передачу сигналів як зв’язку, а логічні - норми і - норми, як спеціальні види нейронів, що виконують математичні відповідні операції. Існує велика різноманітність подібних нейронечітких мереж neuro-fuzzy network (англ.). Наприклад, ANFIS (Adaptive Neuro fuzzy Inference System) — адаптивна нейронечітка система виводу.

Вона може бути описана в універсальній формі аппроксіматоров як

(1)

крім того, цією формулою можуть бути описані також деякі види нейронних мереж, такі як радіально базисні мережі (RBF), багатошарові персептрони (MLP), а також вейвлети і сплайни.

Характеристикою нечіткої множини виступає функція приналежності (Membership Function). Позначимо через — ступінь приналежності до нечіткої множини C, що представляє собою узагальнення поняття характеристичної функції звичайної множини. Тоді нечіткою безліччю С називається безліч впорядкованих пар виду. Значення означає відсутність приналежності до безлічі, 1 — повну приналежність.

Проілюструємо це на простому прикладі. Формалізуємо неточне визначення «гарячий чай». В якості (область міркувань) виступатиме шкала температури в градусах Цельсія. Очевидно, що вона буде змінюється від 0 до 100 градусів. Нечітка безліч для поняття «гарячий чай» може виглядати наступним чином:

Так, чай з температурою належить до безлічі «Гарячий» зі ступенем приналежності 0,80. Для однієї людини чай при температурі може виявитися гарячим, для іншого — не надто гарячим. Саме в цьому і проявляється нечіткість завдання відповідної множини.

Для нечітких множин, як і для звичайних, визначено основні логічні операції. Самими основними, необхідними для розрахунків, є перетин і об'єднання.

Перетин двох нечітких множин (нечітка «І»): .

Об'єднання двох нечітких множин (нечітке «АБО»): .

У теорії нечітких множин розроблено загальний підхід до виконання операторів перетину, об'єднання і доповнення, реалізований в так званих трикутних нормах і конормах. Наведені вище реалізації операцій перетину і об'єднання — найбільш поширені випадки — норми і - конорми.

Для опису нечітких множин вводяться поняття нечіткої і лінгвістичної змінних.

Нечітка змінна описується набором, де — це назва змінної, — універсальна безліч (область міркувань), — нечітка множина на .

Значеннями лінгвістичної змінної можуть бути нечіткі змінні, тобто лінгвістична змінна знаходиться на більш високому рівні, ніж нечітка змінна. Кожна лінгвістична змінна складається з:

— назви;

— безлічі своїх значень, яке також називається базовою терм-множиною. Елементи базової терм-множини являють собою назви нечітких змінних;

— універсальної множини ;

— синтаксичного правила, за яким генеруються нові терми із застосуванням слів природної або формальної мови;

— семантичного правила, яке кожному значенню лінгвістичної змінної ставить у відповідність нечітку підмножину безлічі .

Розглянемо таке нечітке поняття як «Ціна акції». Це і є назва лінгвістичної змінної. Сформуємо для неї базову терм-безліч, яка складатиметься з трьох нечітких змінних: «Низька», «Помірна», «Висока» і задамо область міркувань у вигляді. Останнє, що залишилося зробити — побудувати функції приналежності для кожного лінгвістичного терма з базової терм-множини .

Існує понад десяток типових форм кривих для завдання функцій приналежності. Найбільшого поширення набули: трикутна, трапецеїдальна і гаусова функції приналежності.

Трикутна функція приналежності визначається трійкою чисел, і її значення в точці обчислюється відповідно до виразу:

(2)

При маємо випадок симетричної трикутної функції приналежності, яка може бути однозначно задана двома параметрами з трійки .

Аналогічно для завдання трапецеїдальної функції приналежності необхідна четвірка чисел :

При трапецеїдальна функція приналежності приймає симетричний вигляд.

Рисунок 1 — Типові кусочно-лінійні функції приналежності.

Функція приналежності гаусова типу описується формулою:

(4)

і оперує двома параметрами. Параметр С позначає центр нечіткої множини, а параметр відповідає за крутизну функції.

Рисунок 2 — Гаусова функція приналежності

Сукупність функцій приналежності для кожного терма з базової терм-множини зазвичай зображаються разом на одному графіку. На рисунку 3 наведено приклад описаної вище лінгвістичної змінної «Ціна акції», на рисунку 4 — формалізація неточного поняття «Вік людини». Так, для людини 48 років ступінь приналежності до безлічі «Молодий» дорівнює 0, «Середній» — 0,47, «Вище середнього» ??- 0,20.

Рисунок 3. Опис лінгвістичної змінної «Ціна акції»

Рисунок 4. Опис лінгвістичної змінної «Вік»

1.2 Розробка нечіткої експертної системи, що діє на основі алгоритму Мамдані для 2-х умов Умова 1: ЯКЩО швидкість передачі пакетів ВИСОКА І пропускна здатність каналу ВИСОКА, ТО затримка передачі відеосигналу НИЗЬКА.

Умова 2: ЯКЩО швидкість передачі пакетів СЕРЕДНЯ І пропускна здатність каналу СЕРЕДНЯ, ТО затримка передачі відеосигналу СЕРЕДНЯ.

Виконання програми за допомогою програми MatLab та інструментів Fuzzy Logic Toolbox.

Fuzzy Logic Toolbox — інтуїтивне графічне середовище для розробки інтелектуальних систем.

Пакет Fuzzy Logic володіє простим і добре продуманим інтерфейсом, що дозволяє легко проектувати і діагностувати нечіткі моделі. Забезпечується підтримка сучасних методів нечіткої кластеризації та адаптивні нечіткі нейронні мережі. Графічні засоби пакета дозволяють інтерактивно відстежувати особливості поведінки системи.

Основні властивості:

— визначення змінних, нечітких правил і функцій належності;

— інтерактивний перегляд нечіткого логічного висновку;

— сучасні методи: адаптивний нечіткий висновок з використанням нейронних мереж, нечітка кластеризація;

— інтерактивне динамічне моделювання в SIMULINK;

— генерація переносного C коду за допомогою Real-Time Workshop®.

Найважливіші особливості:

1) Простота у використанні. Пакет Fuzzy Logic створений для того, щоб користувач мав можливість швидко оволоділи нечіткою логікою і застосовували її для вирішення практичних завдань. Тим, хто вже добре знайомий з нечіткою логікою, пакет пропонує сучасні методи і можливість створювати власні методи.

2) Графічне проектування. Пакет Fuzzy Logic містить п’ять графічних редакторів для представлення необхідної інформації в процесі проектування, створення та тестування нечітких моделей.

Рисунок 5 — Схема нейрона

3) Сучасні методи. Пакет Fuzzy Logic включає сучасні методи нечіткого моделювання, включаючи:

— адаптивний нечіткий висновок з використанням нейронних мереж для автоматичного формування функцій належності в процесі навчання їх на вхідних даних;

— нечітка логіка і кластеризація для задачі розпізнавання образів;

— можливість вибору широко відомого методу Мамдані або потужного методу Сугено для створення гібридних нечітких систем.

Схема нейрона (рисунок 5) буде складатися з:

— двох входів (Швидкість передачі пакетів, Пропускна здатність каналу);

— одного виходу (Затримка передачі відеосигналу);

— блоку з заданими правилами, працюючого на основі алгоритму Мамдані.

Далі задаємо експертні значення функції приналежності для входів та виходу. Входи вимірюються в Мбіт/с, а вихід — в мілісекундах.

Рисунок 6 — Функція приналежності швидкості передачі пакетів

Рисунок 7 — Функція приналежності пропускної здатності каналу

Рисунок 8 — Функція приналежності затримки передачі відеосигналу

Рисунок 9 — Правила в нечіткій експертній системі

Рисунок 10 — Відображення результатів роботи алгоритму по завданим значенням

Рисунок 11 — Діаграма затримки передачі пакетів відеосигналу відносно Пропускної здатності каналу та Швидкості передачі пакетів

Далі розрахуємо нечітку експертну систему вручну.

1) Проведення фазифікації (побудова функції належності вхідних і вихідних параметрів).

Рисунок 12 — Функції приналежності вхідних та вихідних параметрів.

2) Етап визначення ступеня істинності вхідних параметрів для отримання нечіткої безлічі.

3) Етап агрегування — етап визначення ступеня істинності вхідних умов виходячи з логічних операцій між ними.

6) Акумулювання — процедура об'єднання області вихідних змінних.

4) Дефазифікації - операції знаходження чіткого вихідного значення.

1.3 Вибір маршрутизатора і опис його характеристик

Маршрутизатор (англ. router) — електронний пристрій, що використовується для поєднання двох або більше мереж і керує процесом маршрутизації, тобто на підставі інформації про топологію мережі та певних правил приймає рішення про пересилання пакетів мережевого рівня (рівень 3 моделі OSI) між різними сегментами мережі.

Для звичайного користувача маршрутизатор (роутер) — це мережевий пристрій, який підключається між локальною мережею та інтернетом. Часто маршрутизатор не обмежується простим пересиланням даних між інтерфейсами, а також виконує й інші функції: захищає локальну мережу від зовнішніх загроз, обмежує доступ користувачів локальної мережі до ресурсів інтернету, роздає IP-адреси, шифрує трафік і багато іншого.

Маршрутизатори працюють на мережному рівні моделі OSI: можуть пересилати пакети з однієї мережі до іншої. Для того, щоб надіслати пакети в потрібному напрямку, маршрутизатор використовує таблицю маршрутизації, що зберігається у пам’яті. Таблиця маршрутизації може складатися засобами статичної або динамічної маршрутизації.

Крім того, маршрутизатори можуть здійснювати трансляцію адреси відправника й одержувача (англ. NAT, Network Address Translation), фільтрацію транзитного потоку даних на основі певних правил з метою обмеження доступу, шифрування/дешифрування передаваних даних тощо.

Маршрутизатори не можуть здійснювати передачу широкомовних повідомлень, таких як ARP-запит.

Маршрутизатором може виступати як спеціалізований пристрій, так і звичайний комп’ютер, що виконує функції простого маршрутизатора.

Мною був обраний маршрутизатор Cisco RV016-G5.

Рисунок 13 — Маршрутизатор Cisco RV016-G5.

Таблиця 1 — Описання технічних характеристик маршрутизатора

2. РОЗРАХУНОК ОПТИМАЛЬНОГО МАРШРУТУ

2.1 Матричний алгоритм пошуку найменших шляхів

Матричний метод визначення найкоротших шляхів дозволяє знайти довжини (ранги) найкоротших шляхів між всіма вершинами графа одночасно, ґрунтується на застосуванні алгебраїчних операцій над матрицею довжин L (матрицею рангів R).

Нехай задана мережа комп’ютерного зв’язку у вигляді графа, зображеного на рисунку 14, числа біля ребер якого відповідають довжинам гілок (ліній) мережі. Тоді матриця довжин L буде мати вигляд показаний в таблиці 2.

Таблиця 2 — Матриця довжин.

Власне кажучи, матриця L — це матриця відстаней безпосередніх зв’язків, тобто шляхів першого рангу. Позначимо матрицю. Зведемо матрицю у квадрат:. Елемент матриці визначається за правилом:

(5)

Інтерпретуючи тепер множення як послідовне, а додавання — як паралельне з'єднання гілок (за аналогією зі зведенням структурної матриці В у ступінь), легко зрозуміти, що добуток відповідає двохтранзитному шляху (шляху другого рангу), що проходить із вершини і у вершину j через проміжну вершину k (рисунок 15, а), а сума, наприклад, чотирьох добутків — чотирьом двохтранзитним шляхам (рисунок 15, б):

(6)

Помітимо, що добутки фактично відповідають однотранзитним шляхам (тобто шляхам першого рангу, що включають тільки одну гілку).

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

При наявності декількох паралельних одноі двохтранзитних шляхів (див. рисунок 14, б) для визначення довжини найкоротшого шляху необхідно операцію додавання у вираженні (5) замінити на операцію вибору мінімуму з довжин усіх одноі двохтранзитних шляхів, тобто замість (5) будемо мати:

(7)

Рисунок 14 — Граф мережі комп’ютерного зв’язку

Рисунок 15 — а) двохтранзитний шлях; б) чотири двохтранзитних шляхи

Таким чином, елемент матриці дорівнює довжині шляху з і в j, найкоротшого серед всіх одноі двохтранзитних шляхів.

При зведенні матриці у ступінь q при використанні операції (7) одержимо елемент якої (для) визначає довжину найкоротшого шляху між вершинами i і j серед усіх шляхів першого, другого, q-го рангу.

Зведення матриці у ступінь максимального рангу приводить до одержання матриці найкоротших по довжині шляхів між всіма парами вершин графа, або матриці оптимальних шляхів Якщо при зведенні матриці у деякий ступінь q виявиться, що

(8)

процес обчислень варто припинити, тому що при рівності (8) завжди виконується рівність .

Таким чином,

Таблиця 3 — обчислення матриці

Тому що й показник ступеня «2» <, процес обчислення

необхідно продовжити, обчисливши .

Таблиця 4 — Обчислення матриці :

З порівняння й видно, що. Таким чином,. Матрицю називають також дистанційною й позначають .

2.2 Програма роботи алгоритму в Microsoft Excel

Microsoft Excel (повна назва Microsoft Office Excel) — програма для роботи з електронними таблицями, створена корпорацією Microsoft для Microsoft Windows, Windows NT і Mac OS. Программа входить до складу офісного пакету Microsoft Office. Вона надає можливості економіко-статистичних розрахунків, графічні інструменти і, за винятком Excel 2008 під Mac OS X, мова макропрограмування VBA (Visual Basic для додатків). Microsoft Excel входить до складу Microsoft Office і на сьогоднішній день Excel є одним з найбільш популярних додатків в світі.

Рисунок 16 — Загальний вигляд роботи програми в Microsoft Excel

3. РОЗРОБКА НЕЙРОМЕРЕЖНОГО АЛГОРИТМУ

3.1 Основні характеристики штучних нейронних мереж

Штучні нейронні мережі (ШНМ) — математичні моделі, а також їхня програмна та апаратна реалізація, побудовані за принципом функціонування біологічних нейронних мереж — мереж нервових клітин живого організму. Системи, архітектура і принцип дії базується на аналогії з мозком живих істот. Ключовим елементом цих систем виступає штучний нейрон як імітаційна модель нервової клітини мозку — біологічного нейрона. Цей термін виник при вивченні процесів, які відбуваються в мозку, та при спробі змоделювати ці процеси. Першою такою спробою були нейронні мережі Маккалока і Піттса. Як наслідок, після розробки алгоритмів навчання, отримані моделі стали використовуватися в практичних цілях: в задачах прогнозування, для розпізнавання образів, в задачах керування та інші.

ШНМ представляють собою систему з'єднаних і взаємодіючих між собою простих процесорів (штучних нейронів). Такі процесори зазвичай достатньо прості, особливо в порівнянні з процесорами, що використовуються в персональних комп’ютерах. Кожен процесор схожої мережі має справу тільки з сигналами, які він періодично отримує, і сигналами, які він періодично посилає іншим процесорам. І тим не менш, будучи з'єднаними в досить велику мережу з керованою взаємодією, такі локально прості процесори разом здатні виконувати достатньо складні завдання. З точки зору машинного навчання, нейронна мережа являє собою окремий випадок методів розпізнавання образів, дискримінантного аналізу, методів кластеризації тощо З математичної точки зору, навчання нейронних мереж — це багатопараметрична задача нелінійної оптимізації. З точки зору кібернетики, нейронна мережа використовується в задачах адаптивного управління і як алгоритми для робототехніки. З точки зору розвитку обчислювальної техніки та програмування, нейронна мережа — спосіб вирішення проблеми ефективного паралелізму. А з точки зору штучного інтелекту, ШНМ є основою філософської течії коннективізму і основним напрямком в структурному підході з вивчення можливості побудови (моделювання) природного інтелекту за допомогою комп’ютерних алгоритмів. Нейронні мережі не програмуються в звичайному розумінні цього слова, вони навчаються. Можливість навчання — одна з головних переваг нейронних мереж перед традиційними алгоритмами. Технічно навчання полягає в знаходженні коефіцієнтів зв’язків між нейронами. У процесі навчання нейронна мережа здатна виявляти складні залежності між вхідними даними і вихідними, а також виконувати узагальнення. Це означає, що у разі успішного навчання мережа зможе повернути вірний результат на підставі даних, які були відсутні в навчальній вибірці, а також неповних та/або «зашумленних», частково перекручених даних.

Рисунок 17 — Схема простої нейронної мережі. Зеленим кольором позначенні вхідні нейрони, голубим приховані нейрони, жовтим - вихідний нейрон.

Біологічна нейронна мережа складається з групи або декількох груп хімічно або функціонально пов’язаних нейронів. Один нейрон може бути пов’язаний з багатьма іншими нейронами, а загальна кількість нейронів та зв’язків між ними може бути дуже великою. Зв’язки, які називаються синапсами, як правило формуються від аксонів до дендритів, хоча дендро-дендритичні мікросхем та інші зв’язки є можливими. Крім електричної передачі сигналів, також є інші форми передачі, які виникають з нейротрансмітерної (хімічний передавач імпульсів між нервовими клітинами) дифузії, і мають вплив на електричну передачу сигналів. Таким чином, нейронні мережі є надзвичайно складними.

Штучний інтелект і когнітивне моделювання намагаються імітувати деякі властивості біологічних нейронних мереж. Хоча аналогічні в своїх методах, перша має на меті вирішення конкретних завдань, а друга спрямована на створення математичних моделей біологічних нейронних систем.

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

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

Розуміння функціонування нейрона і картини його зв’язків дозволило дослідникам створити математичні моделі для перевірки своїх теорій. У перших же роботах з’ясувалося, що ці моделі не тільки повторюють функції мозку, але і здатні виконувати функції, що мають свою власну цінність. Тому виникли й залишаються до сьогодні дві взаємнозбагачуючі цілі нейронного моделювання:

— перша — зрозуміти функціонування нервової системи людини на рівні фізіології і психології;

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

Перший крок був зроблений у 1943 р. з появою статті нейрофізіолога Уоррена Маккалоха (Warren McCulloch) і математика Волтера Піттса (Walter Pitts) про роботу штучних нейронів і представлення моделі нейронної мережі на електричних схемах.

У 1950;ті - 1960;ті роки група дослідників, об'єднавши ці біологічні і фізіологічні підходи, створила перші штучні нейронні мережі. В 1950;х рр. з’являються програмні моделі штучних нейромереж. Перші роботи провів Натаніел Рочестер (Nathanial Rochester) з дослідної лабораторії IBM. І хоча пізніші реалізації були успішними, його модель зазнала невдачі, оскільки бурхливе зростання традиційних обчислень залишило нейронні дослідження в тіні.

Перші успіхи викликали вибух активності й оптимізму. Мінскі, Розенблат, Відроу і інші розробили мережі, що складалися з одного прошарку штучних нейронів, які назвали перцептронами. Ці мережі застосовували для розв’язання широкого класу задач: прогноз погоди, аналіз електрокардіограм, штучний зір.

В 1956 Дартмутський дослідний проект з штучного інтелекту забезпечив розвиток дослідження штучного інтелекту, зокрема, нейронних мереж. Стимулювання досліджень штучного інтелекту розгалузилось у двох напрямках:

— промислові застосування систем штучного інтелекту (експертні системи);

— моделювання мозку.

Проте декілька найбільш наполегливих вчених, таких як Тейво Кохонен, Стів Гросберг, Джеймс Андерсон (James A. Anderson) продовжили дослідження. Поступово з’явився теоретичний фундамент, на основі якого сьогодні конструюються найпотужніші багатошарові мережі. Оцінка Мінскі виявилася надто песимістичною, багато з поставлених в його книзі задач розв’язуються зараз мережами за допомогою стандартних процедур.

Наприкінці 1980;х років теорія стала застосовуватися в прикладних областях і з’явилися нові корпорації, що займалися комерційним використанням цієї технології. Наростання наукової активності носило вибуховий характер. У 1987 було проведено чотири великих наради зі штучних нейронних мереж і опубліковано понад 500 наукових статей.

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

Це відродження інтересу було викликане як теоретичними, так і прикладними досягненнями. Несподівано відкрилися можливості використання обчислень в сферах, які до цього відносились лише до області людського інтелекту, можливості створення машин, здатність яких вчитися і запам’ятовувати дивним образом нагадує процеси мислення людини, і наповнення новим значним змістом терміну «штучний інтелект».

Класифікація за типом вхідної інформації:

— аналогові нейронні мережі (використовують інформацію у формі дійсних чисел);

— двійкові нейронні мережі (оперують з інформацією, представленою в двійковому вигляді).

Класифікація за характером навчання:

— навчання з учителем — відомі вихідні результати нейронної мережі;

— навчання без вчителя — нейронна мережа опрацьовує тільки вхідні дані та самостійно формує вихідні результати. Такі мережі називають самоорганізаційними;

— навчання з підкріпленням — система призначення штрафів і заохочень від середовища.

Класифікація за характером налаштування синапсів:

— мережі з фіксованими зв’язками (вагові коефіцієнти нейронної мережі вибираються відразу, виходячи з умов завдання, при цьому: dW / dt = 0, де W — вагові коефіцієнти мережі);

— мережі з динамічними зв’язками (для них в процесі навчання відбувається налаштування синаптичних зв’язків, тобто dW / dt? 0, де W — вагові коефіцієнти мережі).

Класифікація образів. Завдання полягає у визначенні приналежності вхідного образу (наприклад, мовного сигналу або рукописного символу), представленого вектором ознак до одного або декількох попередньо визначеним класам. До відомих додатків ставляться розпізнавання букв, розпізнавання мови, класифікація сигналу електрокардіограми, класифікація клітин крові.

Кластеризація / категоризація. При вирішенні задачі кластеризації, навчальна множина не має міток класів. Алгоритм кластеризації заснований на подобі образів і поміщає схожі образи в один кластер. Відомі випадки застосування кластеризації для видобутку знань, стиснення даних і дослідження властивостей даних.

3.2 Методи навчання штучних нейронних мереж

Характерною властивістю ШНМ є її здатність до навчання, що полягає у виробленні правильної реакції на подані їй різні вхідні сигнали. Існують такі можливості навчання ШНМ:

— зміна конфігурації мережі шляхом утворення нових або виключення деяких існуючих зв’язків між нейронами;

— зміна елементів матриці зв’язку (ваг);

— зміна характеристик нейронів (виду й параметрів активаційної функції й т. д.).

Найбільшого поширення сьогодні отримав підхід, при якому структура мережі задається апріорно, а мережа навчається шляхом настроювання матриці зв’язків (вагових коефіцієнтів) W. Від того, наскільки вдало побудована ця матриця, залежить ефективність даної мережі. У цьому випадку навчання полягає у зміні за певною процедурою елементів матриці W при послідовному поданні мережі деяких векторів, що навчають.

У зв’язку з цим штучний нейрон може бути представлений у такий спосіб (рисунок 18).

Рисунок 18 — Модель штучного нейрона.

У процесі навчання ваги стають такими, що під час надходження вхідних сигналів мережа виробляє відповідні необхідні вихідні сигнали. Розрізнюють навчання з учителем і без учителя. Перший тип навчання припускає, що є «учитель», що задає пари, які навчають — для кожного вхідного вектору, що навчає, необхідний вихід мережі. Для кожного вхідного вектору, що навчає, обчислюється вихід мережі, порівнюється з відповідно необхідним, визначається помилка виходу, на основі якої й коректуються ваги. Пари, що навчають, подаються мережі послідовно й ваги уточняються доти, поки помилка за такими парами не досягне необхідного рівня.

Цей вид навчання неправдоподібний з біологічної точки зору. Дійсно, важко уявити зовнішнього «учителя» мозку, що порівнює реальні й необхідні реакції того, кого навчають, і коригує його поведінку (поведінку нейронів) за допомогою негативного зворотного зв’язку. Більш природним є навчання без учителя, коли мережі подаються тільки вектори вхідних сигналів, і мережа сама, використовуючи деякий алгоритм навчання, підстроювала б ваги так, щоб при поданні їй досить близьких вхідних векторів вихідні сигнали були б однаковими. У цьому випадку в процесі навчання виділяються статистичні властивості безлічі вхідних векторів, що навчають, і відбувається об'єднання близьких (подібних) векторів у класи. Подання мережі вектору з даного класу викликає її певну реакцію, яка до навчання є непередбаченою. Тому в процесі навчання виходи мережі мають трансформуватися в деяку зрозумілу форму. Це не є серйозним обмеженням, оскільки зазвичай нескладно ідентифікувати зв’язок між вхідними векторами й відповідною реакцією мережі.

Існує ще один вид навчання — з підкріплюванням (reinforcement learning), при якому також передбачається наявність учителя, що не підказує, однак, мережі правильної відповіді. Учитель тільки повідомляє, правильно чи неправильно відпрацювала мережа поданий образ. На основі цього мережа корегує свої параметри, збільшуючи значення ваг зв’язків, що правильно реагують на вхідний сигнал, і зменшуючи значення інших ваг.

Сьогодні існує велика кількість алгоритмів навчання. Приведу найбільш відомі з них.

1) Правило навчання Гебба (корелятивне, співвідносне навчання).

Більшість сучасних алгоритмів навчання виросло із правила Гебба. Наприкінці 40-х років XX ст. років Д. О. Гебб теоретично встановив, що асоціативна пам’ять у біологічних системах викликається процесами, що змінюють зв’язки між нервовими клітинами. Відповідно до установленого їм правила, що називається «правилом Гебба», при одночасній активації (порушенні) двох нейронів синаптична сила (вага їхнього зв’язку) зростає. Таким чином, часто використовувані зв’язки в мережі підсилюються, що пояснює феномен звички й навчання повторенням.

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

Слід лише зазначити, що це правило досить активно використовувалося в мережах, однак за останні роки виникло багато більш ефективних алгоритмів, що забезпечують значно вищу швидкість навчання.

2) Дельта-правило.

Це важливе правило навчання було запропоновано Б. Уідроу й М. Е. Гоффом і найбільше відповідає одношаровим ШНМ прямого поширення. Ідея його полягає в тому, що якщо під час навчання мережі можна встановити розбіжність між її бажаною й наявною реакціями, ця розбіжність може бути усунута або зменшена шляхом зміни певним чином вагових коефіцієнтів зв’язку.

3) Розширене дельта-правило.

Розширене дельта-правило, на відміну від простого, знаходить застосування у багатошарових ШНМ прямого поширення другого порядку.

4) Конкурентне навчання.

У цьому виді навчання всі нейрони одного шару є конкуруючими, а перевага віддається тому нейрону, що найбільш сильно реагує на вхідний (дратівний) сигнал, тобто настроюються ваги тільки одного нейрона — нейрона-переможця (winner-takes-all).

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

5) Стохастичне навчання.

Розглянуті вище методи є детерміністськими, у яких на кожному такті за певним алгоритмом відбувається корекція ваг, заснована на використанні значень вхідних і вихідних бажаних і фактичних сигналів.

Стохастичні методи навчання базуються на псевдовипадкових змінах ваг зі збереженням тих змін, які ведуть до поліпшень. Для корекції ваг використовується деяка імовірнісна функція. Більші первинні і випадкові корекції зі збереженням певних змін ваг поступово зменшують, досягаючи при цьому мети навчання. Це нагадує процес відпалювання металу, коли атоми розплавленого металу, які перебувають у хаотичному русі при його поступовому охолодженні, гублячи енергію, досягають нижчого з можливих енергетичних станів (глобального мінімуму). Тому для опису цього виду навчання часто використовують термін «імітація відпалювання» (simulated annealing).

Таке стохастичне навчання використовується в машинах Больцмана й Коші.

6) Градієнтні методи навчання.

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

Ці методи найчастіше використовуються при контрольованому навчанні, коли відома необхідна реакція нейронів .

Градієнтні методи застосовуються також і для навчання стохастичних нейронів.

7) Навчання з підкріплюванням.

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

На завершення зазначу, що хоча цей вид навчання й досліджено у ряді робіт, він не належить до числа популярних.

3.3 Розробка програми навчання нейронної мережі на основі таблиць маршрутизації в пакеті Microsoft Excel

Навчання нейронної мережі буду проводити за методом «Дельта-правило» запропонованого Б. Уідроу й М. Е. Гоффом.

На рисунку 19 зображений граф мережі.

Рисунок 19 — Граф мережі

Ребра графа неорієнтовані та мають певні вагові коефіцієнти, які я приведу до діапазону [0.1]:

; ;

;; ;

; ;

Шляхи між вузлами я розділю на прямі та зворотні. Прямі вузли (наприклад, від вузла 1 до вузла 2, або від вузла 3 до вузла 5 та ін.) будуть мати вхідний сигнал 1, а зворотні вузли (наприклад, від вузла 2 до вузла 1, або ж від вузла 5 до вузла 3) будуть мати вхідний сигнал -1.

Для прикладу знайдемо оптимальний шлях між віддаленими вузлами мережі, для графу заданого на рисунку 19, найбільш віддаленим є шлях від вузла 1 до вузла 5.

Перейдемо до навчання нейронної мережі (рисунок 20).

Рисунок 20 — Навчання нейронної мережі в Microsoft Excel.

Визначимо всі можливі шляхи між вузлами 1 та 5:

;

;

;

;

;

;

Функція значить, що навчання нейронна пройшло успішно.

Наприклад, якщо наші вагові коефіцієнти відповідають довжині ребер, то порівнюючи можливо визначити найкоротшу відстань.

ВИСНОВКИ При виконанні завдань курсової роботи були розглянуті та виконані наступні розділи:

1) Розробка системи підтримки прийняття рішень (СППР) для проектування комп’ютерної мережі.

Система підтримки прийняття рішень, СППР, система підтримки прийняття рішень, DSS — комп’ютерна автоматизована система, метою якої є допомога людям, що приймають рішення в складних умовах для повного і об'єктивного аналізу предметної діяльності.

2) Розрахунок оптимального маршруту.

В якості розрахунку оптимального маршруту був використаний матричний алгоритм пошуку найменших шляхів.

Матричний метод визначення найкоротших шляхів дозволяє знайти довжини (ранги) найкоротших шляхів між всіма вершинами графа одночасно, ґрунтується на застосуванні алгебраїчних операцій над матрицею довжин L (матрицею рангів R).