Задача знаходження найкоротших шляхів

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

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

Загальна задача знаходження найкоротшого шляху полягає у знаходженні для кожної упорядкованої пари вершин будь-якого шляху від вершини до вершини , довжина якого мінімальна серед всіх можливих шляхів від до . Алгоритм розв’язку сформованої задачі носить назву алгоритму Флойда (R. W. Floyd). Для визначеності допустимо, що всі вершини графа послідовно пронумеровані ві 1 до . Алгоритм Флойда використовує матрицю розміром , в яку заносяться довжини найкоротших шляхів. На початку роботи алгоритму для всіх . Якщо вершини та не з’єднані між собою, то . Кожний діагональний елемент матриці дорівнює нулю, тобто .

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

На -ій ітерації для обчислення значень елементів матриці використовується наступна формула:

, (3.1)

де нижній індекс позначає значення елемента матриці після -ої ітерації. Графічна інтерпретація формули (3.1) показана на рис. 3.3.

Рисунок 3.3 – Включення вершини у шлях від до

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

 

FloydPath

n – розмір матриці А

1 for i=1 to n

2 for j=1 to n

3 A(i,j)=C(i,j)

4 end for

5 end for

6 for i=1 to n

7 A(i,j)=0

8 end for

9 for k=1 to n

10 for i=1 to n

11 for j=1 to n

12 if A(i,k)+ A(k,j)< A(i,j)

13 then A(i,j)= A(i,k)+ A(k,j)

14 end if

15 end for

16 end for

17 end for

 

Час виконання алгоритму FloydPath має порядок , оскільки вона вміщує вкладені один в одного три цикли.

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

Модифікована версія алгоритму Флойда, яка дає змогу визначати найкоротший шлях наведена нижче.

 

ModifiedFloydPath

n – розмір матриці А

1 for i=1 to n

2 for j=1 to n

3 A(i,j)=C(i,j)

4 P(i,j)=0

5 end for

6 end for

7 for i=1 to n

8 A(i,j)=0

9 end for

10 for k=1 to n

11 for i=1 to n

12 for j=1 to n

13 if A(i,k)+ A(k,j)< A(i,j)

14 then A(i,j)= A(i,k)+ A(k,j)

15 P(i,j)=k

16 end if

17 end for

18 end for

19 end for

 

Для індикації послідовності вершин, які визначають найкоротший шлях від вершини до вершини , викликається процедура Path(i,j), псевдокод якої має наступний вигляд

 

Path(i,j)

1 k=P(i,j)

2 if k=0

3 return

4 path(i,k)

5 writeln(k)

6 path(i,k)

7 end if

 

Множення матриць

Матриця - математичний об’єкт, який задається таблицею чисел , , . Числа і визначають розмір матриці , тобто матриця має рядків і стовпців; на перетині -го рядка та -го стовпця знаходиться елемент матриці . Отже, матриця розміром задається таблицею чисел

.

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

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

, , . (3.2)

У результаті виконання операції (3.2) отримаємо матрицю розміром .

У загальному випадку , тобто операція множення матриць не комутативна.

Стандартний алгоритм множення двох матриць і розмірами і має наступний вигляд:

 

MatrixMultiply

1 Визначити розміри матриць А і В – m,r,n

2 for i=1 to m

3 for j=1 to n

4 C(i,j)=0

5 for k=1 to r

6 C(i,j)=C(i,j)+A(i,k)*B(k,j)

7 end for

8 end for

9 end for

 

Алгоритм MatrixMultiply множення матриць і розмірами і виконує операцій множення і операцій додавання. Загальна кількість операцій, що виконує алгоритм MatrixMultiply при перемноженні двох матриць, дорівнюватиме .

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

 

Таблиця 3.1 – Порівняння ефективності трьох

Алгоритмів

Алгоритм	Операції
множення	додавання
Стандартний
Винограда
Штрассена

 

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

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

, (3.3)

де матриця має розмір , .

Ланцюжок матриць (3.3) можна перемножувати природнім способом – зліва направо. При множенні матриці на розмірами і отримаємо матрицю розміром . Потім до матриць та застосовуємо операцію множення, що дає змогу отримати матрицю розміром і т. д.

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

,

,

,

,

.

Час обчислення добутку матриць визначається кількістю скалярних добутків, які обчислюються у рядку 6 процедури MatrixMultiply. Ця кількість дорівнює . Якщо -ту лінійку матриці та -тий стовпець матриці розглядати як вектори з компонентами і , то під скалярним добутком будемо розуміти операцію знаходження елемента матриці як скалярний добуток двох векторів .

Щоб проілюструвати як спосіб розстановки дужок при перемноженні декількох матриць впливає на кількість операцій, що виконуються, розглянемо приклад, у якому перемножуються три матриці . Допустимо, що розміри цих матриць – , та . Перемножуючи ланцюжок матриць у природному порядку – зліва направо; спочатку отримаємо матрицю , а потім матрицю . Розміри матриць і відповідно дорівнюють і відповідно, де , і . Матриця буде мати розмір . Для обчислення всіх елементів матриці необхідно обчислити скалярних добутків. Знаходження елементів матриці , яка матиме розмір , потребує . Разом будемо мати 5000+2500=7500 скалярних множень. Якщо обчислити результат, який задається виразом , то неважко підрахувати, що отримаємо 75000 скалярних множень. Таким чином, для обчислення першим способом добутку ланцюжка матриць затрати часу будуть у 10 раз менші, ніж у другому випадку.

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

Звернемо увагу на те, що операція перемноження матриць у задачу не входить. Мета розв’язку поставленої задачі – визначити оптимальний порядок перемноження матриць.

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

(3.4)

Розв’язком рекурентної співвідношення (3.4) є так звана послідовність чисел Каталана, яка зростає як . Таким чином, кількість варіантів розстановки дужок має експоненціальне збільшення зі зростанням , і метод прямого перебору не є ефективним для визначення оптимальної стратегії розстановки дужок.

Для розв’язку поставленої задачі застосуємо алгоритмічну стратегію динамічного програмування.

Позначимо результат перемноження матриць через , де . Якщо задача нетривіальна, то будь-який спосіб розстановки дужок розбиває добуток між матрицями і , де - ціле число, що задовольняє умові . Таким чином, при деякому спочатку обчислюються матриці і , а потім вони перемножуються між собою і у результаті отримуємо добуток . Вартість, яка визначається вибраним способом розстановки дужок дорівнює сумі вартості обчислення матриці , вартості обчислення матриці та вартості обчислення добутку матриць і .

Нехай мінімальна кількість скалярних добутків необхідних для обчислення матриці . Тоді повна вартість мінімальної кількості скалярних добутків для обчислення буде - .

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

. (3.5)

У рекурсивному співвідношенні невідомою є величина . Для знаходження значення є можливостей, а саме - , тобто

(3.6)

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

 

MatrixChainOrder

1 n=length(p)

2 for i=1 to n

3 m(i,i)=0

4 end for

5 for l=2 to n

6 for i=1 to n-l+1

7 j=i+l-1

8 m(i,j)=

9 for k=i to j-1

10 q=m(i,k)+m(k+1,j)+p_i-1p_kp_j

11 if q< m(i,j)

12 then m(i,j)=q

13 s(i,j)=k

14 end if

15 end for

16 end for

17 end for

 

Спочатку в процедурі MatrixChainOrder (рядки 2 – 4) величинам присвоюється нульове значення, що відповідає послідовності нульової довжини. У першій ітерації циклу (рядки 5 – 16) за допомогою рекурентного співвідношення (3.6) обчислюються величини при - мінімальні вартості для послідовностей довжини . При другому проході цього ж циклу обчислюються величини при - мінімальні вартості для послідовностей довжини . і т. д. На кожному етапі уже вичислені у рядках 9 – 17 величина залежать тільки від попередньо обчислених і занесених у таблицю значень і .

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

Приклад 3.3 Для матриць, розміри яких наведені у табл. 3.2 визначити оптимальну розстановку дужок з використанням процедури MatrixChainOrder.

Оскільки використовується тільки частина таблиці у якій елементи визначені тільки при , то використовується тільки та її частина, що розміщена над верхньою діагоналлю (рис. 3.4). На рис. 3.4 таблиця повернута таким чином, щоб її головна діагональ розмістилась горизонтально. Із даної таблиці легко знайти мінімальну вартість часткового добутку матриць .Вона знаходиться на пересіченні ліній, що йдуть від матриці вправо і вгору, і від матриці - вліво і вгору. У кожному горизонтальному рядку матриці знаходяться вартості перемноження часткових послідовностей, які складаються з однакової кількості матриць. У процедурі рядки обчислюються знизу вверх, а елементи у кожному рядку - зліва направо. із таблиці видно, що мінімальна вартість скалярних добутків, яка необхідна для перемноження шести матриць із табл. 3.2, дорівнює 15125. Таблиця дає змогу визначити порядок розстановки дужок у добутку матриць . У верхній клітинці таблиці знаходиться значення , яке розбиває добуток матриць на два співмножники і . Оскільки , то оптимальна розстановка дужок у добутку матриць буде такою: .

 

 

Таблиця 3.2 – Матриці та їх розміри

Матриця	Розмір

 

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

 

 

Рисунок 3.4 – Таблиці та , що обчислюються процедурою MatrixChainOrder для

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

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

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

Таблиця 3.3 – Скалярні добутки матриць при природному їх

Множенні

Часткові добутки матриць	Розмір матриці	Скалярні добутки
Загальна кількість скалярних добутків

 

 

Швидке перетворення Фур’є

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

Перетворення Фур’є дійсної функції , яка визначена на нескінченому інтервалі, обчислюється за формулою

,

де - частота;

- уявна одиниця.

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

.

Допустимо, що величина спостерігається у дискретні моменти часу , де , ; - крок дискретності. Тоді інтеграл в останньому співвідношенні можна замінити сумою

.

Для обчислення вибирають, як правило, дискретні значення частот

, .

Тоді

.

Підставляючи в останню формулу замість його значення, отримуємо

.

Якщо ввести позначення , то

, (3.6)

Величина носить назву множника повороту.

Вектор називається дискретним перетворенням Фур’є (Discrete Fourier Transform, DFT) вектора і позначається таким чином: .

В алгоритмі дискретного перетворення Фур’є використовуються властивості комплексних коренів із одиниці.

Комплексним коренем степені із одиниці називають таке комплексне число , що

. (3.7)

Рівняння (3.7) має рівно комплексних коренів

, (3.8)

де ; - уявна одиниця.

Комплексні корені із одиниці рівномірно розподілені на колі одиничного радіуса з центром у нулі (рис. 3.5). Значення

(3.9)

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

Рисунок 3.5 – Значення на комплексній площині ()

Наведемо основні властивості коренів із одиниці.

Властивість 1. для будь-яких цілих , і

. (3.10)

У відповідності з (3.8)

. (3.11)

Властивість 2. Для будь-якого парного

. (3.12)

Використовуючи співвідношення (3.8), можемо записати . Згідно формули Ейлера . Із рівності (3.9) випливає, що , тобто має місце формула (3.11).

Властивість 3 (ділення наполовину). Якщо парне, то, піднісши до квадрату всі комплексних коренів степені із одиниці, отримаємо всі комплексні корені степені із одиниці.

Оскільки , то з врахуванням (3.12), маємо . Із останньої рівності випливає, що . Розглянемо величину . Із властивості 1, коли випливає, що . Так як , то

.

Властивість 4 (додавання). Для будь-якого і невід’ємного числа , яке не є кратним до , має місце рівність

. (3.13)

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

.

Знаменник не перетворюється у нуль, так як не кратне .

У формулі (3.6) введемо позначення: . Тоді формула (3.6) набуде такого вигляду:

. (3.14)

Таким чином, FFT-задача трансформувалась у задачу обчислення значень многочлена (3.14) степені у коренях степені із одиниці, тобто у точках , , , …, .

Для розв’язку FFT-задачі використаємо метод «розділяй і володарюй». Допускаємо, що степінь полінома (3.14) є степеню числа 2, тобто , де - ціле додатне число. Якщо це не так, то поліном (3.14) доповнюється до полінома степені , з нульовими коефіцієнтами при відповідних степенях. Утворимо два поліноми і

,

,

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

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

У тому випадку, коли степінь числа 2, то швидке перетворення Фур’є має степінь складності .