загрузка...
загрузка...
На головну

приклад рішення

  1. Ethernet - приклад стандартної технології з комутацією пакетів
  2. Fill in the missing numerals in the following sentences as in the example given for the first sentence. (Вставте пропущене ім'я числівник як в прикладі.)
  3. I. Приклади деяких розподілів дискретних випадкових величин
  4. II. Проблема виродженого базисного рішення
  5. III. «Наприклад» в аналізі
  6. PEST-аналіз і приклад його використання
  7. SWOT - аналіз на прикладі фабрики з виробництва взуття.

 Розглянемо роботу алгоритму Дейкстри на прикладі мережі, зображеної на рис. 8. Вузол s= 1здесь є джерелом, r= 4 - стоком, а числа cij, Приписані дуг, відповідають їх довжині або узагальненої вартості. Матриця узагальненої вартості цієї мережі має вигляд:

C = ;

Робота алгоритму (див. Рис. 9) починається з того, що істочнікупріпісивается постійна позначка I1 = 0, а вузлам j = 2,3,4 присвоюються тимчасові позначки Ij =  . Таким чином проводиться початкове заповнення. Надалі проводиться ітеративна процедура. Перша ітерація: на першому кроці обчислюються нові тимчасові позначки всіх вузлів (2, 3, 4), що не мають постійних позначок:

I2'= Min {I2, L1 + c12} = Min {  , 0 + 3} = 3,

I3'= Min {I3, L1 + c13} = Min {  , 0 +2} = 2,

I4'= Min {I4, L1 + c14} = Min {  , 0 +  } = .

На другому кроці вузлу 3, тимчасова позначка якого найменша з отриманих, присвоюється постійна позначка L3 = I3'= 2.

Друга ітерація: на першому кроці обчислюються нові тимчасові позначки вузлів 2, 4, що не мають постійних позначок:

I2'= Min {I2, L3 + c32} = Min {3,2 +  } = 3,

I4'= Min {I4, L3 + c34} = Min {  , 2 + 7} = 9.

На другому кроці вузлу 2, тимчасова позначка якого найменша з отриманих, присвоюється постійна позначка L2 =I2'= 3.

Третя ітерація: на першому кроці обчислюється нова тимчасова позначка вузла 4, що не має постійної позначки:

I4'= Min {I4, L2 + с24} = Min {9,3 + 4} = 7.

На другому кроці вузлу 4, тимчасова позначка якого найменша (і єдина) з отриманих, присвоюється постійна позначка L4 = I4'= 7. Так як поміченим виявився стік 4 = r, Прямий хід алгоритму Дейкстри закінчений.

 Графічна демонстрація цього рішення наведена на рис. 9; табличное рішення - в табл. 1.

Таблиця 1: Прямий хід алгоритму Дейкстри

 вузол i: s= 1 r= 4
 ітерація:  значення позначок
 
   
     

У зворотному ході алгоритму Дейкстри (див. Рис. 10) беруть участь всі 4 вузли. Після початкового заповнення оптимальна ланцюг має вигляд [?, 4]. Перша ітерація: на першому кроці обчислюються величини:

1 = L4 - L1 - c14 = 7 - 0 -  = - ,

2 = L4 - L2 - c24 = 7 - 3 - 4 = 0,

3 = L4 - L3 - c34 = 7 - 2 - 7 = - 2.

На другому кроці вузол 2, для якого 2 = 0, включається в оптимальну ланцюг [?, 2, 4].

Друга ітерація: на першому кроці обчислюються величини:

1 = L2 - L1 - c12 = 3 - 0 - 3 = 0, 3 = L2 - L3 - c32 = 3 - 2 -  = - .

На другому кроці вузол 2, для якого 1 = 0 включається в оптимальну ланцюг [1, 2, 4]. Так як це джерело (1 = s), Зворотний хід алгоритму Дейкстри закінчений.

Графічна демонстрація цього рішення наведена на рис. 10; табличное рішення - в табл. 2.

Таблиця 2: Зворотний хід алгоритму Дейкстри

 вузол i: s= 1  оптимальна ланцюг
 ітерація:  значення i
       [?, 4]
-  -2  [?, 2,4]
  -  [1, 2, 4]

Таким чином, з використанням алгоритму Дейкстри вирішена задача пошуку найкоротшої ланцюга (ланцюга найменшої узагальненої вартості) для мережі G (Див. Рис. 8). Оптимальна ланцюг: [1, 2, 4], її довжина 7. Оптимальний потік Fmin в мережі G: Fmin = {f12 = 1; f13 = 0; f23 = 0; f24 = 1; f34 = 0}.



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

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

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