На головну

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

  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 - аналіз на прикладі фабрики з виробництва взуття.

 Розглянемо роботу алгоритму Літтла на прикладі мережі, зображеної на рис. 11. Числа cij, Приписані дуг, відповідають їх довжині або узагальненої вартості. Матриця узагальненої вартості цієї мережі має вигляд:

C=

 Робота алгоритму починається з редукування ациклічності і однонаправленнихучастков мережі. Результат наведено на рис. 12. З матриці Cпри цьому викреслюються рядки і стовпці з однаковими номерами, в яких не на головній діагоналі є трохи більше одного кінцевого елементу, тобто в нашому випадку №№ 5, 6. Матриця скороченої циклічного подграфа G1 має вигляд:

C1 =

Для обчислення верхньої межі використаємо ланцюг [1, 2, 3, 4, 1]:

Hmax = H [1, 2, 3, 4, 1] = 17 + 7 + 11 + 3 = 38.

Процедура ітерацій:


Ітерація № 1.

 Ісходнаяматріца  minв стор.  Редуцірованнаяпо рядках  Редуцірованнаяпо стовпцями
           
 
 
 
 
           S = 22  S = 0  

Нижня межа вартості всіх маршрутів, яка виходить на цій ітерації, є сума всіх величин, на які редукувалася матриця (вони виписані праворуч від вихідної і знизу від скороченої по рядках матриць): H1 = 22 + 0 = 22.

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

i, j  1,4  2,3  3,2  4,1
Фij

Так як максимальний Ф14, То всі маршрути діляться на дві групи: що містять дугу [1, 4], і її не містять (в дереві маршрутів мітка [1, 4], Мал. 13). Нижня межа вартості всіх маршрутів, що не містять дугу [1, 4], обчислюється як сума H1 и Ф14: Н14 = 22 + 10 = 32. Елемент с41 потрібно було рівним  . Повірок на повернення і підцикли на ітерації №1 не проводиться, нижня межа другої вершини рис. 13 обчислюється на наступній ітерації №2, в якій розглядається матриця без першого рядка і четвертого стовпця.


Ітерація № 2.

 Ісходнаяматріца  minв стор.  Редуцірованнаяпо рядках  Редуцірованнаяпо стовпцями
                 
                                   
       
       
       
           S = 5    S = 3    

 Нижня межа вузла [1, 4], яка виходить на цій ітерації, є сума всіх величин, на які редукувалася матриця, і попередньої нижньої межі H1: H14 = 22 + 5 + 3 = 30.

Для кожного нуля обчислюємо штрафи:

i, j  2,3  3,1  3,2  4,2
Фij

Так як максимальний Ф23, То маршрути, які містять дугу [1, 4], діляться на дві групи: що містять дугу [2, 3] і її не містять (в дереві маршрутів мітка [2, 3], Мал. 14). Причому нижня межа вартості всіх маршрутів, що не містять дугу [2, 3], обчислюється як сума H14 и Ф23: Н23 = 30 + 10 = 40. Елемент с32 потрібно було рівним  . Перевірка на повернення і підцикли на ітерації № 2 результату не дає, так як H14 Hmax, H14} І з дуг [1, 4] і [2, 3] не можна утворити підцикл додаванням будь-якої третьої, нижня межа другої вершини (рис. 14) обчислюється на наступній ітерації № 3, в якій розглядається матриця без другого рядка і третього стовпця.


Ітерація № 3.

 Ісходнаяматріца  minв стор.  Редуцірованнаяпо рядках  Редуцірованнаяпо стовпцями
                       
                                   
                                   
             
             
           S = 0      S = 0      

Нижня межа вузла [2, 3]: H23 = H14+ 0 + 0 = 30.

 Для кожного нуля обчислюємо штрафи:

i, j  3,1  4,2
Фij

 Нескінченні штрафи означають, що ми зобов'язані вибрати обидві дуги, яким відповідають кінцеві елементи матриці, прийом при виборі їх виходить повний маршрут. У такій ситуації нижні межі H31 и Н42 рівні між собою і дорівнюють H23 (Нижній межі даної ітерації). Так як H23 Hmax, H14, H23}, То вороття немає; так як замкнутий повний маршрут, то підцикл неосвічений. Взагалі кажучи, наявність на будь-якої ітерації матриці 2 х 2, аналогічної отриманої тут, свідчить про правильність проведених обчислень і про закінчення ітерацій і без обчислення штрафів. Результуюче дерево маршрутів наведено на рис. 16.

В результаті ітеративного процесу отриманий мінімальний остовно контур [1, 4, 2, 3, 1] графа G1 (Рис. 12) з узагальненою вартістю 30. Для отримання мінімального остовного контуру вихідної мережі G (Рис. 11) необхідно в нього додати контури від скорочених на першому етапі алгоритму ділянок: [1, 4, 6, 4, 2, 3, 1, 5, 1], А до вартості додати с15 + с51 + с46 + с64, Що дасть остаточну величину узагальненої вартості знайденого мінімального остовного контуру:

С [1, 4, 6, 4, 2, 3, 1, 5, 1] = 30 + 2 + 4 + 5 + 5 = 46.

 Рішення завдання отримано. Необхідно, однак, відзначити, що в даному випадку не зустрілася ситуація повернення і ситуація усунення можливого подцикла, і сіли остання зустрінеться нижче в прикладі виконання домашнього завдання, то ситуацію повернення ілюструє дерево маршрутів (рис. 17) для завдання з наведеної нижче матрицею узагальненої вартості, причому через наявність лише нульових штрафів на першій ітерації (ситуація великої кількості близьких за вартістю маршрутів) при виборі на першій ітерації дуги [1, 5] вже на третій виникає повернення, так як на цій ітерації H34 виявляється більше H15 (Див. Рис. 17).

C = .

Більш того, при проведенні процедури повернення до першої ітерації (при цьому c15 =  ) На ітерації 2 'знову виникає повернення (див. Рис. 17) за рахунок зазначеної вище особливості матриці прикладу.



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

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

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