Приведення вихідної матриці в по стовпцях
Пункти початку руху |
Пункти кінця руху |
||||
1 |
2 |
3 |
4 |
5 |
|
1 |
∞ |
|
|
|
|
2 |
|
∞ |
|
|
|
3 |
|
|
∞ |
|
|
4 |
|
|
|
∞ |
|
5 |
|
|
|
|
∞ |
|
7 |
1 |
0 |
0 |
0 |
Для приведення матриці по стовпцях у кожному стовпці табл. 2.2 знаходиться мінімальний елемент (константи приведення по стовпцях). Ці мінімальні елементи записуються під матрицею. Вони віднімаються з елементів відповідних стовпців (табл. 2.3 – приведення матриці по стовпцях).
Матриця, яка приведена по рядках і стовпцях, показана в табл. 2.4.
Таблиця 2.4
Матриця В, приведена по рядках і стовпцях
Пункти початку руху |
Пункти кінця руху |
||||
1 |
2 |
3 |
4 |
5 |
|
1 |
∞ |
2 |
0 |
3 |
2 |
2 |
2 |
∞ |
0 |
0 |
2 |
3 |
0 |
0 |
∞ |
0 |
2 |
4 |
4 |
1 |
1 |
∞ |
0 |
5 |
3 |
3 |
3 |
0 |
∞ |
Сума констант приведення складе:
.
Отримана величина одночасно є нижньою границею витрат часу (або відстані чи іншого показника, за яким розраховується маршрут) на рух по маршруту. Витрати часу по кожному найбільш сприятливому варіанту не можуть бути менше 29 од.
Етап 2. Організація процесу розгалуження.
Для виконання даного етапу для кожного
нульового елемента
матриці В (табл. 2.4) розраховується
показник
,
який записується в правому верхньому
куті елемента
.
визначається як сума мінімального
елемента
-го
рядка й мінімального елемента
-го
стовпця, виключаючи 0, що знаходиться в
-му
рядку в
-му
стовпці:
,
,
,
,
,
,
,
.
Приведена матриця В із зазначеними для елементів представлена в табл. 2.5.
Таблиця 2.5
Приведена матриця В із зазначеними
Пункти початку руху |
Пункти кінця руху |
||||
1 |
2 |
3 |
4 |
5 |
|
1 |
∞ |
2 |
0 2 |
3 |
2 |
2 |
2 |
∞ |
0 0 |
0 0 |
2 |
3 |
0 2 |
0 1 |
∞ |
0 0 |
2 |
4 |
4 |
1 |
1 |
∞ |
0 3 |
5 |
3 |
3 |
3 |
0 3 |
∞ |
Розгалуження повинне здійснюватися по
дугах
,
що мають найбільше значення
в приведеній матриці В (табл. 2.5).
Найбільші значення мають
і
.
Для розгалуження можна використати як
дугу (4,5), так і дугу (5,4). Скористаємося
дугою (4,5). Позначимо всі варіанти, що
включають у маршрут дугу 4,5 через (4,5), а
варіанти, що не включають дугу 4,5 через
.
Перший етап розгалуження показаний на
рис. 2.1.
Рис. 2.1. Перший етап розгалуження
На рис. 2.1 початковій вершині (вона
позначена «Усі цикли») відповідає оцінка
«29», яка отримана як сума констант
приведення –
,
що визначає нижню границю, тобто
мінімальне значення можливих витрат
по циклу.
Виберемо цикли, що включають гілку (4,5). Нижня границя варіанта, що виключає використання дуги (4,5) (ліва гілка дерева) визначається як сума нижньої границі всіх циклів плюс : 29+3=32. Рядок 4 і стовпець 5 матриці (табл. 2.5) викреслюються (табл. 2.6). Не викреслені рядки і стовпці утворять нову матрицю, у якій у клітці (5,4) варто поставити «∞», тому що включення дуги (4,5) у маршрут виключає використання в маршруті дуги (5,4). Нова матриця показана в табл. 2.7. Відзначимо, що при викреслюванні рядків і стовпців нумерація рядків і стовпців, що залишилися, зберігається колишньою.
Таблиця 2.6
Процес виключення рядків
Пункти початку руху |
Пункти кінця руху |
||||
1 |
2 |
3 |
4 |
5 |
|
1 |
∞ |
2 |
0 |
3 |
2 |
2 |
2 |
∞ |
0 |
0 |
2 |
3 |
0 |
0 |
∞ |
0 |
2 |
4 |
4 |
1 |
1 |
∞ |
0 |
5 |
3 |
3 |
3 |
0 |
∞ |
Після одержання розгалуження й відповідного перетворення матриці В знову виконуються етап 1 - одержання нової приведеної матриці В, і етап 2 - організація процесу розгалуження.
Етапи 1 й 2 повторюються до одержання рішення завдання - побудови оптимального кільцевого маршруту.
Для приведення нової матриці визначаються константи приведення по рядках (цифри з правої сторони матриці, табл. 2.7).
Таблиця 2.7
Приведена матриця з константами
-
Пункти початку руху
Пункти кінця руху
1
2
3
4
1
∞
2
0
3
0
2
2
∞
0
0
0
3
0
0
∞
0
0
5
3
3
3
∞
3
Матриця, після її приведення по рядках, показана в табл. 2.8.
Таблиця 2.8
Матриця, після її приведення по рядках
Пункти початку руху |
Пункти кінця руху |
|||
1 |
2 |
3 |
4 |
|
1 |
∞ |
2 |
0 |
3 |
2 |
2 |
∞ |
0 |
0 |
3 |
0 |
0 |
∞ |
0 |
5 |
0 |
0 |
0 |
∞ |
Кожен стовпець матриці містить не менш
одного нуля. Це виключає необхідність
приведення матриці по стовпцях. Сума
констант приведення
.
Нижня границя варіанта, що включає дугу
(4,5) (права гілка дерева), визначається
як сума нижньої границі всіх циклів
плюс
(див. рис. 2.1). Для наступного розгалуження
дерева по правій гілці визначається
для нової приведеної матриці (табл.
2.8):
,
,
,
,
,
,
,
,
.
Максимальне значення має
.
Рядок 1 і стовпець 3 в матриці викреслюються
(табл. 2.9).
Таблиця 2.9
Нова приведена матриця
Пункти початку руху |
Пункти кінця руху |
|||
1 |
2 |
3 |
4 |
|
1 |
∞ |
2 |
0 |
3 |
2 |
2 |
∞ |
0 |
0 |
3 |
0 |
0 |
∞ |
0 |
5 |
0 |
0 |
0 |
∞ |
Дуга (1,3) включається в маршрут, що
виключає використання дуги (3,1). У клітку
(3,1) записується
(табл. 2.10).
Таблиця 2.10
Нова приведена матриця
Пункти початку руху |
Пункти кінця руху |
||
1 |
2 |
4 |
|
2 |
2 |
∞ |
0 |
3 |
∞ |
0 |
0 |
5 |
0 |
0 |
∞ |
Наступне розгалуження правої частини дерева з використанням дуги (1,3) показане на рис. 2.2.
Помітимо, що при оцінці циклів, що
включають дугу (1,3) треба до попередньої
оцінки (32) додати суму констант приведення
(
).
При оцінці циклів, що не включають дугу
(
),
до попередньої оцінки (32) додається
(2).
Рис. 2.2. Останнє розгалуження правої частини дерева
Як видно з табл. 2.10, сума констант
приведення дорівнює 0 (
).
Нижня границя варіантів з використанням
дуги (1,3) дорівнює 32+0=32, а нижня границя
варіантів, що виключають дугу (1,3),
дорівнює 34.
Отже, подальше розгалуження варто проводити по правій частині дерева.
Отримана матриця (табл. 2.10) не має потреби в приведенні, тому що в кожному рядку й кожному стовпці є не менш одного нуля.
Сума констант приведення дорівнює нулю.
Значення нової матриці показані в табл. 2.11.
Наступне розгалуження приводить до варіантів, що включають дугу (3,1) (мал. 2.3). Включення дуги (3,1) виключає використання дуги (1,3). У новій матриці (табл. 2.11) у клітці (1,3) проставляється «∞».
Таблиця 2.11
Матриця, після виключення дуги (1,3)
Пункти початку руху |
Пункти кінця руху |
||
2 |
3 |
5 |
|
1 |
2 |
∞ |
0 |
2 |
∞ |
0 |
0 |
4 |
0 |
0 |
∞ |
Максимальне значення мають
,
тобто розгалуження можна здійснювати
по дузі (2,4) або по дузі (5,1). Виберемо дугу
(2,4).
Нове розгалуження по дугам (2,4) і (
)
з оцінкою циклів представлене на рис.
2.3.
Рис. 2.3. Наступне розгалуження правої частини дерева
Викреслимо рядок 2 і стовпець 4 з матриці В. Одержуємо табл. 2.12.
Таблиця 2.12
Матриця, після виключення гілки (2,4)
Пункти початку руху |
Пункти кінця руху |
|
1 |
2 |
|
3 |
∞ |
0 ∞ |
5 |
0 ∞ |
0 0 |
Сума константи приведення для цієї матриці дорівнює 0.
Розраховані значення показані в правому верхньому куті матриці.
Як бачимо, розгалуження повинне здійснюватися або по дузі (3,2), або по дузі (5,1). Цей крок є останнім, тому здійснюється вибір одночасно двох дуг – (3,2) і (5,1). Виконаємо оцінку отриманого результату (рис. 2.4).
Рис. 2.4. Останнє розгалуження
Як бачимо, відповідно до рішення (рис. 2.4) у цикл увійшли наступні дуги: (1,3), (2,4), (3,2), (5,1). Оцінка циклу – 32 од.
Побудуємо отриманий цикл (рис. 2.5) і з використанням вихідної матриці В (табл. 2.1) одержимо сумарне значення часу Т (відстані L) переміщення по дугах циклу:
Т (L) = 12+2+4+4+10 = 32.
Рис. 2.5. Оптимальний маршрут (цикл)
Таким чином, отримане значення Т (L) = 32 од. відповідає оптимальному рішенню (32 од.), отриманому методом «гілок і границь».
Відзначимо, що у випадку, коли на якомусь із кроків розгалуження оцінка циклу виявляється вище, ніж та, котра відповідала напрямку розгалуження, виключеному як безперспективне на попередніх кроках, здійснюється повернення до цього напрямку. Наприклад, нехай на рис. 2.4 на розгалуженні по дузі (2,4) отримана оцінка не 32 од., а 33 од. Тоді цей напрямок пошуку не продовжується, а здійснюється повернення на крок, де здійснюється розгалуження по напрямку з оцінкою 32 од. (оскільки ця оцінка менше, ніж 33 од.).
Якщо на якомусь наступному кроці розвитку розгалуження виявиться, що оцінка більше 33 од., то знову здійснюється повернення на розгалуження (2,4). Таким чином, у методі виключається можливість дослідження неоптимальних циклів.
Висновки: розглянутий метод «гілок і границь» є точним і забезпечує можливість одержання оптимального маршруту (циклу). Крім того, трудомісткість процесу пошуку оптимального маршруту на кожному наступному кроці зменшується за рахунок виключення рядків та стовпців матриці В.