Особливості методу гілок і границь для розв’язування задачі про комівояжера

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

Для кожної задачі, з урахуванням її специфіки, розробляються наступні підходи:

1) Правило розгалуження.

2) Спосіб обчислення оцінок (функція цілі).

3) Способи знаходження розв’язків.

Отже, основною особливістю методу гілок і границь є те, що він дозволяє організувати повну процедуру перебору відповідних планів задачі.

Розглянемо зазначений підхід детально.

Нехай на деякій множині W необхідно мінімізувати функцію j. Тоді цю процедуру реалізують у такий спосіб: W розбивають на ряд непересічних підмножин і потім вибирається та підмножина, наприклад W₁, на якій функція j досягає свого найменшого значення. Далі розбивають W₁ на ряд підмножин і вибирають ту з них, наприклад W₂, на якій функція j досягає свого мінімального значення. Далі W₂ розбивають на кілька непересічних частин. Такий процес розгалуження реалізують до одноелементної множини. Така одноелементна множина називається рекордом.

Практичну реалізацію методу гілок і границь для задачі про комівояжера зручніше за все проводити на тлі конкретному прикладі.

Приклад. Спекла бабка колобок і поставила його остигати на віконце. І вирішив колобок, що поки він стигне, він може оббігти ліс, подивитися на лісових жителів і знову повернутися. Сказано-зроблено. Зстрибнув він з віконця й покотився в ліс. Допоможіть колобку знайти найкоротший шлях його руху в лісі, якщо відстань між норами й будинком діда й баби дані в наступній таблиці:

	Дід і баба	Заєць	Вовк	Ведмідь	Лисиця
Дід і баба
Заєць				3, 5	4, 5
Вовк				5, 5
Ведмідь		3, 5	5, 5
Лисиця		4, 5

 

Математична модель задачі: для рішення задачі привласнимо кожному пункту задачі певний номер: дід і баба = 1, заєць =2, вовк = 3, ведмідь = 4, лисиця = 5.

Отже, загальне число пунктів n = 5. Тоді, на першому етапі можна записати функцію цілі задачі

Задача вирішується в рамках наступних обмежень:

дозволяється перехід з 1 пункту в 2 або 3 або 4 або5

Розв’язування задачі комівояжера методом гілок і границь

1. Аналіз вихідної множини ((омега)

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

Далі знаходимо значення функції цілі

.

Аналогічно визначається матриця мінімальних відстаней по стовпцях

.

Тоді .

У такому випадку оцінка функції якості Н буде визначатися на основі співвідношення

– вибираємо максимальне число.

Далі оцінимо верхнє значення функції якості. Для цієї мети виберемо початковий план

.

У такому випадку верхнє значення функції якості .

Очевидно, що вихідна множина планів (буде містити в собі наступні підмножини:

.

Тут W _ij означає перехід з i-того пункту (у цьому випадку 1) в j-ий.

2. Аналіз підмножини W₁₂

.

У такому випадку на першому етапі матрицю вихідних маршрутів можна представити у вигляді

Для визначення нижньої границі функції якості на підмножині W₁₂ знову визначають мінімальне значення функції якості по рядках і стовпцях

3. Аналіз підмножини W₁₃

Верхня оцінка функції якості на цій підмножині

4. Аналіз підмножини W₁₄

Далі визначаємо верхню границю функції якості на цій підмножині

.

5. Аналіз підмножини W₁₅

Визначимо нижнє значення функції якості на множині W₁₅

. – можливий варіант відвідування

.

6. Відсівання безперспективних підмножин

.

Підмножини V ₁₂ й V ₁₄ мають найкращу верхню оцінку функції якості, однак перспективним є підмножина W₁₄, в силу того, що нижня границя функції якості є ближче до оптимальної.

Отже, надалі необхідно розглядати підмножину W₁₄.

Розглядається підмножина W₁₄, що містить у собі наступні підмножини .

7. Аналіз підмножини W₁₄₂

.

Далі обчислюють верхню границю функції якості

.

Визначення нижньої границі функції якості

. – можливі шляхи пересування комівояжера

.

8. Аналіз підмножини W₁₄₃

Визначення верхньої границі функції якості

Визначення нижньої границі функції якості

.

9. Аналіз підмножини W₁₄₅

Визначення верхньої границі функції якості

Визначення нижньої границі функції якості

.

10. Відсівання безперспективних підмножин

.

Підмножина V ₁₄₃ є безперспективною.В силу того, що верхня границя функції якості на підмножинах V ₁₄₂ й V ₁₄₅ збігаються між собою, то далі порівнюють між собою нижні границі функції якості і тому що Н ₁₄₂ > Н ₁₄₅, то рекордом є підмножина W₁₄₅. При цьому W₁₄₅ буде містити в собі 2 непересічні підмножини .

11. Аналіз підмножини W₁₄₅₂

Визначення верхньої границі функції якості

Визначення нижньої границі функції якості

.

12. Аналіз підмножини W₁₄₅₃

Визначення верхньої границі функції якості

Визначення нижньої границі функції якості

.

13. Відсівання безперспективних підмножин

.

14. У такому випадку

.

Оптимальна матриця переміщень буде представлена в такий спосіб

Таким чином, оптимальний маршрут колобка буде представлений наступними відвідуваннями: дід і баба ® ведмідь ® лисиця ® заєць ® вовк ® дід і баба. При цьому .

 

Дерево розв’язків

 

0 крок		W
	W12	W13	W14	W15
1 крок
2 крок		W142	W143	W145
3 крок			W1452	W1453
		W14523