На головну

Алгоритм рішення (алгоритм Дейкстри)

  1. I. РОЗРОБКА АЛГОРИТМІВ. ГРАФІЧНЕ ЗОБРАЖЕННЯ (БЛОК-СХЕМИ) І СЛОВЕСНА ЗАПИС АЛГОРИТМІВ
  2. II. Проблема виродженого базисного рішення
  3. Автомобільного транспорту та шляхи їх вирішення
  4. АЛГОРИТМ 10
  5. алгоритм DES
  6. алгоритм RSA
  7. Алгоритм автоматичного формування парних симетричних ключів шифрування-дешифрування відкритих повідомлень на робочих станціях абонентів корпоративної системи.

Алгоритм Дейкстри застосуємо для невід'ємних елементів матриці с і складається з двох частин: прямого і зворотного ходів. Прямий хід містить початкове заповнення і ітеративну процедуру. В процесі роботи кожного вузла i приписується, а потім змінюється деяке число, зване позначкою, яка може бути двох видів - постійна Li або тимчасова Ii . Змінюватися при цьому можуть тільки тимчасові позначки. Просування вузлів постійні позначки в подальшому змінюватися не можуть.

 Начальноезаполненіе:    Джерела привласнити постійну позначку 0.Остальним вузлів i привласнити тимчасові позначки, чисельно рівні елементам csi матриці узагальненої вартості дуг з джерела в вузол i. Для вузлів, які не є кінцевими для дуг, що йдуть з джерела, тимчасові позначки рівні . Ls = 0; Ii = csi, i N, i s.

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

 ітерація:    Крок 1:    Для всіх вузлів i з тимчасовими позначками Ii обчислити їх нове значення Ii як найменше з старого значення позначки і суми отриманої на попередній ітерації постійної позначки Lj з узагальненої вартістю дуги [ji].Ii '= Min {Ii; Lj + зji}; j: Lj =  {Li} (3)
         
     Крок 2:    Вузлу, тимчасова позначка якого є найменшою з усіх ще існуючих тимчасових позначок, привласнити постійну позначку, чисельно рівну цієї тимчасової.Lj = Ij; j: Ij =  {Ii} (4) Якщо поміченим виявляється стік (j = r), Прямий хід алгоритму Дейкстри закінчений.

Величина постійної позначки стоку дорівнює узагальненої вартості невідомої поки що оптимальною ланцюга. Сама ланцюг визначається у другій частині алгоритму Дейкстри і складається з дуг, для кожної з яких різниця між значеннями постійних позначок її кінцевих вузлів, дорівнює довжині (узагальненої вартості) цієї дуги. Іншими словами, умова, при виконанні якого вузли i и j належать найкоротшою ланцюга [s, ..., i, j, ..., r] Може бути записано таким чином:

Lj - Li - cij = 0. (5)

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

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

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

Ітеративна процедура складається не більше ніж з n-1 Ітерації і триває до тих пір, поки джерело не потрапить в оптимальну ланцюг. Кожна ітерація виконується по одному і тому ж алгоритму і складається з двох кроків.

 ітерація:    Крок 1:    Для всіх вузлів i з постійними позначками Li обчислити величину i = Lj - Li - cij, де Lj - Постійна позначка вузла j, Останнім включеного в оптимальну ланцюг.
         
     Крок 2:    Включити в оптимальну ланцюг вузол, що задовольняє умові (5): i '= 0. Якщо це джерело (i'= s), Зворотний хід алгоритму Дейкстри закінчений.

Абсолютно аналогічним методом може бути вирішена задача про ланцюги максимальної довжини, проте при цьому в прямому ході алгоритму Дейкстри в виразах (3) і (4) необхідно min {...} замінити на max {...} (від тих же виразів) і в початковому заповненні прямого ходу алгоритму Дейкстри замість  необхідно ввести - .

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



Попередня   1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   Наступна

Вступ | Перелік використовуваних надалі позначень | визначення | Орієнтовані і неорієнтовані мережі | Теорема про максимальний потік і мінімальному розрізі | Ізоморфізм і гомеоморфизм графів. | Дерева і деревовидних | Матричні уявлення мереж | Приклади економічних задач, що зводяться до задачі про найкоротшою ланцюга | Алгоритм рішення (алгоритм Літтла) |

© um.co.ua - учбові матеріали та реферати