Знайдіть найкоротший маршрут через усі міста і поверніться додому. Задача Комівояжера (TSP) є NP-важкою: для 20 міст є понад 60 квадрильйонів маршрутів для перевірки.
TSP є NP-важкою: кількість маршрутів зростає як (n−1)!/2. Жоден відомий алгоритм не розв'язує її оптимально для великих n за поліноміальний час. Використовуються евристики: жадібний, 2-opt, симуляція відпалу, мурашині алгоритми.
Виберіть кількість міст і алгоритм. Спостерігайте за покращенням маршруту. Порівняйте якість жадібного алгоритму, 2-opt та симуляції відпалу. Клацайте, щоб додати нові міста.
Оптимальне рішення TSP для 85 900 міст (рекорд 2006 р.) зайняло 136 CPU-років обчислень. TSP застосовується у логістиці, прокладці друкованих плат і навіть у ДНК-секвенуванні.