Самойленко Ігор ВалерійовичЙосипчук Анастасія Ігорівна2023-12-202024-05-142023-12-202023Йосипчук А, І. Задача Комівояжера : випускна кваліфікаційна робота бакалавра : 113 Прикладна математика / Йосипчук Анастасія Ігорівна. – Київ, 2023. – 37 с.https://ir.library.knu.ua/handle/123456789/5801Метою дипломної роботи є дослідження і розв'язання задачі Комівояжера з метою знайти оптимальний маршрут та реалізувати для цього ефективний алгоритм з мінімальними обчислювальними витратами, використовуючи стандартний технічний пристрій. В роботі було розглянуто історію виникнення задачі Комівояжера, її теоретичну постановку, задачі, що зводяться до неї (Гамільтона, Переналадка станків) а також точні та наближені алгоритми розв’язання (алгоритм повного перебору, гілок та меж, алгоритм найближчого сусіда, алгоритм випадкових чисел, генетичний алгоритм, мурашиний алгоритм, k-opt алгоритм) та оцінку якості їх виконання. Було реалізовано вибірково 4 з них: алгоритм повного перебору, алгоритм найближчого сусіда, генетичний алгоритм, k-opt, та візуалізовані результати за допомогою бібліотеки Python folium. В результаті було побудувано наближений до оптимального маршрут та проаналізовано роботу алгоритмів на прикладі використаної задачі.uaБакалаврська робота