Вказівки до виконання. 1. Визначаються витрати на переміщення між містами за своїм варіантом (“i”-дорівнюється останній, а “j” - передостанній цифрі номеру залікової книжки або

1. Визначаються витрати на переміщення між містами за своїм варіантом (“ i ”-дорівнюється останній, а “ j ” - передостанній цифрі номеру залікової книжки або студентського квитка).

2. Знаходиться мінімальний гамільтоновий контур для графа з n вершинами у наступній послідовності:

2.1. Знаходимо в кожному рядку матриці мінімальний елемент і віднімаємо його від усіх елементів відповідного рядка.

2.2. Якщо в матриці, наведеної по рядках, виявляться стовпці, що не містять нуля, то приводимо її по стовпцях.

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

2.4. Знаходимо ступені нулів для наведеної по рядках і стовпцям матриці.

2.5. Визначаємо дугу, для якої ступінь нульового елемента досягає максимального значення.

2.6. Розбиваємо множину всіх гамільтонових контурів на дві підмножини.

2.7. Порівнюємо нижні границі підмножини гамільтонових контурів.

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

3. Порівнюємо довжину гамільтонова контуру з нижніми границями обірваних гілок. Якщо довжина контуру не перевищує їхніх нижніх границь, то завдання вирішене. У противному випадку розвиваємо гілки підмножин з нижньою границею, меншої отриманого контуру, доти, поки не одержимо маршрут з найменшими витратами або не переконаємося, що такого не існує.

Контрольні питання

1. Які існують методи рішення задачі комівояжера?

2. Яким чином приводиться матриця по строках та стовпцях?

3. Яким чином визначається нижня границя множини всіх припустимих гамільтонових контурів?

4. Як утворюється дерево розгалужень?

5. Що таке оптимальний маршрут?