n align="justify"> 4. Будується допоміжна матриця nхn. Елементами цієї матриці є числа 0 і 1. При цьому, якщо T ik ki , то на перетині рядка i та стовпця k заноситься 1, а на перетині рядка k і шпальти i - 0. У разі T ik = T ki в обидві клітини заноситься 1.
. На основі допоміжної матриці будуються всі повні допустимі послідовності об'єктів. p align="justify"> Послідовність об'єктів i 1 , i 2 , i 3 , ..., i n називається допустимої, якщо для будь-якої пари суміжних об'єктів e, k елемент допоміжної матриці в клітці (k, e) дорівнює 1. Таким чином, перехід з об'єкту k на об'єкт e дозволяється, якщо T Kе еk .
Послідовність об'єктів є повною, якщо вона містить усі n об'єктів без повторень.
Повні допустимі послідовності об'єктів будуються шляхом послідовного В«зчитуванняВ» допоміжної матриці.
. Серед всіх повних допустимих послідовностей об'єктів вибирається та послідовність, яка відповідає мінімальної загальної тривалості будівництва. p align="justify"> Допоміжна матриця має наступний вигляд:
Таблиця 12
123456789101 11111111121 01111111301 11111114101 01111150001 11111600001 11117100001 01181000001 11910000001 110100000001
На основі допоміжної матриці виділяємо 2 допустимі послідовності:
) 7 2 10 5 < span align = "justify"> 3 9 4 8 1 6
2) 2 10 4 1 7 9 6 3 5 8
Розрахуємо для 2 цих послідовностей тривалість будівництва
) +5? 6? 4? 3? 9? 7? 1? 10? 8? 2. br/>
За допомогою ув'язки визначаємо, що тривалість будівництва в даному випадку с...
