Задача Комівояжера
Тип публікації :
Бакалаврська робота
Дата випуску :
2023
Автор(и) :
Йосипчук Анастасія Ігорівна
Мова основного тексту :
ua
eKNUTSHIR URL :
Цитування :
[APA 7] Йосипчук, А. І. (2023). Задача Комівояжера [Бакалаврська робота, Київський національний університет імені Тараса Шевченка]. eKNUTSHIR. https://ir.library.knu.ua/handle/123456789/5801
[ДСТУ] Йосипчук А. І. Задача Комівояжера : кваліфікаційна робота бакалавра : 11 Математика та статистика. Київ, 2023. 37 с. URL: https://ir.library.knu.ua/handle/123456789/5801 (дата звернення: 25.07.2026).
Метою дипломної роботи є дослідження і розв'язання задачі Комівояжера з метою знайти оптимальний маршрут та реалізувати для цього ефективний алгоритм з мінімальними обчислювальними витратами, використовуючи стандартний технічний пристрій.
В роботі було розглянуто історію виникнення задачі Комівояжера, її теоретичну постановку, задачі, що зводяться до неї (Гамільтона, Переналадка станків) а також точні та наближені алгоритми розв’язання (алгоритм повного перебору, гілок та меж, алгоритм найближчого сусіда, алгоритм випадкових чисел, генетичний алгоритм, мурашиний алгоритм, k-opt алгоритм) та оцінку якості їх виконання.
Було реалізовано вибірково 4 з них: алгоритм повного перебору, алгоритм найближчого сусіда, генетичний алгоритм, k-opt, та візуалізовані результати за допомогою бібліотеки Python folium. В результаті було побудувано наближений до оптимального маршрут та проаналізовано роботу алгоритмів на прикладі використаної задачі.
В роботі було розглянуто історію виникнення задачі Комівояжера, її теоретичну постановку, задачі, що зводяться до неї (Гамільтона, Переналадка станків) а також точні та наближені алгоритми розв’язання (алгоритм повного перебору, гілок та меж, алгоритм найближчого сусіда, алгоритм випадкових чисел, генетичний алгоритм, мурашиний алгоритм, k-opt алгоритм) та оцінку якості їх виконання.
Було реалізовано вибірково 4 з них: алгоритм повного перебору, алгоритм найближчого сусіда, генетичний алгоритм, k-opt, та візуалізовані результати за допомогою бібліотеки Python folium. В результаті було побудувано наближений до оптимального маршрут та проаналізовано роботу алгоритмів на прикладі використаної задачі.
Галузі знань та спеціальності :
11 Математика та статистика
113 Прикладна математика
Файл(и) :![Ескіз]()
Вантажиться...
Формат :
Adobe PDF
Розмір :
2.43 MB
Контрольна сума :
(MD5):775b897e5533a72d2ad0ca18afe25d24
Якщо не вказано інше, ця робота розповсюджується на умовах ліцензії Creative Commons Attribution-NonCommercial 4.0 International