40. Метод гілок та границь. Задача комміявожера.

Метод гілок і меж (англ. Branch-and-Bound) — один з поширених методів дискретної оптимізації. Метод працює на дереві рішень та визначає принципи роботи конкретних алгоритмів пошуку розв'язків, тобто, є мета-алгоритмом. Для різних задач комбінаторної оптимізації створюють спеціалізовані алгоритми гілок та меж.Ідею методу було вперше сформульовано A.H. Land та A.G. Doig (1960) в галузі дослідження операцій. R.J. Dakin (1965) розробив простий для впровадження алгоритм.На жаль, цей алгоритм не виправдав покладені на нього надії. Більш того, якщо спочатку алгоритм не був пов'язаний з методом гілок та меж, то згодом було встановлено, що адитивний алгоритм являється частковим випадком методу гілок та меж.Метод гілок і меж - це один з методів організації повного перебору. Він застосовується не завжди, а тільки тоді, коли виконуються специфічні додаткові умови на безліч M і мінімізуєму на ньому функцію.

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

Існує кілька окремих випадків загальної постановки завдання, зокрема геометрична задача комівояжера (також звана планарной або евклідової, коли матриця відстаней відображає відстані між точками на площині), трикутна задача комівояжера (коли на матриці вартостей виконується нерівність трикутника), симетрична і асиметрична задачі комівояжера. Також існує узагальнення задачі, так звана узагальнена задача комівояжера.Загальна постановка задачі, втім як і більшість її часткових випадків, відноситься до класу NP-повних задач. Задача комівояжера відноситься до числа трансобчислювальної: вже при відносно невеликому числі міст (66 і більше) вона не може бути вирішена методом перебору варіантів ніякими теоретично мислимими комп'ютерами за час, менший декількох мільярдів років.