# data[].attributes.headline
Задача комівояжера

# data[].attributes.subject
Задача комівояжера

# data[].attributes.body
Задача полягає в знаходженні самого вигідного маршрута, що проходить через зазначені міста хоча б по одному разу з наступним поверненням в початкове місто.

Метод гілок і меж

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

Для вирішення завдання комівояжера методом гілок і меж необхідно виконати наступну послідовність дій:

1. Побудова матриці з вихідними даними.

2. Знаходження мінімуму по рядках.

3. Редукція рядків.

4. Знаходження мінімуму за стовпцями.

5. Редукція стовпців.

6. Обчислення оцінок нульових клітин.

7. Редукція матриці.

8. Якщо повний шлях ще не знайдений, переходимо до пункту 2, якщо знайдений до пункту 9.

9. Обчислення підсумкової довжини шляху і побудова маршруту.

eolymp #3474, #3473

# data[].attributes.headline
Задача комівояжера

# data[].attributes.subject
Задача комівояжера

# data[].attributes.body
Алексюк, Гребенюк, Дзус, Колачко

# data[].attributes.attachment_link.title
Задача комівояжера

# data[].attributes.headline
Задача комівояжера

# data[].attributes.subject
Задача комівояжера

# data[].attributes.attachment_link.title
Презентация 16