🤝 Задача Комівояжера

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

TSP є NP-складною: жоден відомий алгоритм не розв'язує її за поліноміальний час у загальному випадку. Кількість різних маршрутів зростає як (n-1)!/2, тож для 20 міст існує приблизно 1,2 × 10^18 маршрутів. Повний перебір усіх маршрутів швидко стає неможливим, тому й використовують евристики.

Найближчий сусід будує маршрут, завжди переходячи до найближчого невідвіданого міста. 2-opt повторно розвертає сегменти маршруту, щоб усунути перетини й скоротити шлях. Симуляція відпалу випадково міняє міста місцями і іноді приймає гірші маршрути, поступово охолоджуючись, щоб зрештою осісти на хорошому розв'язку.

Для кожного випадкового обміну вона обчислює зміну довжини маршруту, дельту. Якщо дельта від'ємна, крок завжди приймається. Якщо дельта додатна, він приймається з імовірністю exp(-дельта / T), де T — поточна температура. У міру охолодження T кроки "вгору" стають рідшими, тож пошук звужується від дослідження до уточнення.

Start temp задає початкову температуру T0 (значення повзунка, помножене на 500), визначаючи, наскільки охоче пошук приймає гірші маршрути на початку. Cooling задає множник на кожен крок alpha приблизно між 0,9995 і 0,99995; значення ближче до 1 охолоджують повільніше, даючи довший і ретельніший пошук перед тим, як температура впаде майже до нуля.

2-opt — це чистий локальний пошук: він приймає лише покращувальні обміни, тому швидко сходиться, але може застрягти в локальному оптимумі, з якого не може вибратися. Симуляція відпалу іноді приймає гірший крок, дозволяючи вирватися з таких пасток. На одних розташуваннях перемагає детермінізм 2-opt, на інших — випадковість симуляції відпалу знаходить коротший маршрут.

Довжина маршруту — це загальна відстань поточного маршруту; Best found — найкоротший маршрут, знайдений досі, зображений блідо-зеленим. Iterations рахує кроки алгоритму, Temperature показує поточне значення T симуляції відпалу, а Improvements рахує, скільки кроків справді скоротили маршрут.

Speed обирає, скільки кроків алгоритму виконується за кадр анімації — від 1 до 20 000 на найвищому налаштуванні, тож можна спостерігати повільно або швидко зійтися. Кнопка Step просуває рівно на одну ітерацію за раз, що корисно для вивчення того, як один обмін чи розворот змінює маршрут.

Ні. Усі три методи — евристики, що прагнуть до майже оптимальних маршрутів, а не доведено найкоротших. Найближчий сусід може бути на 25 відсотків або більше гіршим за оптимум; 2-opt і симуляція відпалу зазвичай значно кращі, але не дають гарантій. Пошук точного оптимуму для великої кількості міст вимагає набагато важчих технік точного розв'язання.

TSP та її варіанти зустрічаються в маршрутизації посилок і доставок, свердлінні отворів у друкованих платах, плануванні спостережень телескопів, плануванні секвенування ДНК та оптимізації траєкторій інструментів у виробництві. Ті самі ідеї "обміняй і покращ", показані тут, масштабуються, з удосконаленнями, до промислового програмного забезпечення маршрутизації, що обробляє тисячі зупинок.