Ця симуляція досліджує задачу комівояжера (TSP): знайти найкоротший замкнений маршрут, який відвідує кожне місто рівно один раз і повертається до початкової точки. Міста — це точки на полотні, а вартість маршруту — сума евклідових відстаней між послідовними зупинками. Ви можете порівняти три класичні евристики на одному й тому ж наборі міст: жадібний алгоритм найближчого сусіда, локальний пошук 2-opt та імітація відпалу.
Повзунок «Міста» (від 4 до 80) та кнопка «Нові міста» генерують випадкові розташування, клацання додає місто, перетягування переміщує його, а правий клік видаляє. Оберіть алгоритм, встановіть швидкість (кроків на кадр) і натисніть «Запуск»; для імітації відпалу повзунки початкової температури та охолодження налаштовують пошук. TSP лежить в основі логістики, маршрутизації транспорту, свердління друкованих плат і ДНК-секвенування.
Що таке задача комівояжера?
Вона шукає найкоротший маршрут, який відвідує заданий набір міст рівно один раз і повертається до початкової точки. Тут міста — точки на екрані, а відстань — пряма (евклідова), тому мета — мінімізувати загальну довжину маршруту. Це одна з найбільш вивчених задач комбінаторної оптимізації.
Чому TSP вважається складною задачею?
TSP є NP-важкою: жоден відомий алгоритм не розв'язує її за поліноміальний час у загальному випадку. Кількість різних маршрутів зростає як (n-1)!/2, тому вже для 20 міст існує близько 1,2 × 10^18 маршрутів. Повний перебір швидко стає неможливим, тому й використовуються евристики.
Що роблять три алгоритми?
Жадібний алгоритм будує маршрут, щоразу переходячи до найближчого невідвіданого міста. Метод 2-opt послідовно розвертає фрагменти маршруту, усуваючи перетини і скорочуючи загальну відстань. Імітація відпалу виконує випадкові перестановки міст і іноді приймає гірші рішення, поступово «охолоджуючись» до хорошого розв'язку.
Для кожної випадкової перестановки обчислюється зміна довжини маршруту — дельта. Якщо дельта від'ємна, крок завжди приймається. Якщо дельта додатна, крок приймається з імовірністю exp(-дельта / T), де T — поточна температура. По мірі охолодження T кроки «вгору по схилу» стають рідшими, і пошук переходить від дослідження до уточнення.
Початкова температура встановлює T0 (значення повзунка, помножене на 500), визначаючи готовність алгоритму приймати гірші рішення на початку. Охолодження задає множник alpha на кожному кроці в діапазоні приблизно від 0,9995 до 0,99995; значення, ближчі до 1, охолоджують повільніше, забезпечуючи тривалий ретельний пошук до того, як температура впаде до нуля.
Метод 2-opt — це чистий локальний пошук: він приймає лише покращення, тому швидко сходиться, але може застрягти у локальному оптимумі. Імітація відпалу іноді приймає гірший крок, що дозволяє вирватися з таких пасток. На деяких розташуваннях детермінованість 2-opt дає перевагу; на інших випадковість відпалу знаходить коротший маршрут.
«Довжина маршруту» — загальна відстань поточного маршруту; «Найкраще» — найкоротший маршрут, знайдений досі (відображається зеленим). «Ітерації» рахують кроки алгоритму, «Температура» показує поточне значення T при відпалі, а «Покращення» — скільки кроків реально скоротили маршрут.
Швидкість визначає кількість кроків алгоритму за один кадр анімації — від 1 до 20 000 на максимальному рівні, тож можна спостерігати повільно або швидко сходитися до результату. Кнопка «Крок» виконує рівно одну ітерацію, що зручно для вивчення того, як окрема перестановка або розворот змінює маршрут.
Ні. Усі три методи є евристиками, що прагнуть до близьких до оптимальних маршрутів, але не до гарантовано найкоротших. Жадібний алгоритм може давати результат на 25% і більше гірше за оптимум; 2-opt та імітація відпалу зазвичай значно кращі, але також без гарантій. Знаходження точного оптимуму для великих наборів міст потребує значно важчих точних методів.
TSP та її варіанти зустрічаються у доставці посилок і маршрутизації транспорту, свердлінні отворів на друкованих платах, плануванні спостережень телескопа, ДНК-секвенуванні та оптимізації траєкторії інструменту у виробництві. Ті самі ідеї перестановок та покращень, показані тут, у розширеному вигляді використовуються у промисловому програмному забезпеченні маршрутизації для тисяч зупинок.
Знайдіть найкоротший маршрут через усі міста і поверніться додому. Задача Комівояжера (TSP) є NP-важкою: для 20 міст є понад 60 квадрильйонів маршрутів для перевірки.
TSP є NP-важкою: кількість маршрутів зростає як (n−1)!/2. Жоден відомий алгоритм не розв'язує її оптимально для великих n за поліноміальний час. Використовуються евристики: жадібний, 2-opt, симуляція відпалу, мурашині алгоритми.
Виберіть кількість міст і алгоритм. Спостерігайте за покращенням маршруту. Порівняйте якість жадібного алгоритму, 2-opt та симуляції відпалу. Клацайте, щоб додати нові міста.
Оптимальне рішення TSP для 85 900 міст (рекорд 2006 р.) зайняло 136 CPU-років обчислень. TSP застосовується у логістиці, прокладці друкованих плат і навіть у ДНК-секвенуванні.