Задача
коммивояжёра
Классика комбинаторной оптимизации: бродячий торговец обходит города по кратчайшему маршруту. Сравни жадный алгоритм с точным решением Хелда-Карпа — в реальном времени на графе.
В чём суть
Торговец должен посетить несколько городов ровно по одному разу и вернуться домой. Цель — сделать это по кратчайшему пути.
NP-hard: почему нельзя просто перебрать
С добавлением одного города количество маршрутов растёт факториально. Для 20 городов полный перебор на обычном компьютере займёт годы.
15 городов: 43 000 000 000+ путей
Где встречается
Логистика, проектирование печатных плат, секвенирование ДНК, маршрутизация дронов. Любая задача, где нужно оптимально обойти набор точек.
Жадный алгоритм
Метод «ближайшего соседа»: из текущего города идём в тот, который ближе всего прямо сейчас. Работает мгновенно, но часто даёт не лучший маршрут.
Хелд-Карп (динамика)
Динамическое программирование по подмножествам. Гарантирует оптимальный результат, но работает только для малого числа городов.
Тренажёр
Сгенерируй города, запусти оба алгоритма и сравни длину маршрутов. Синий путь — жадный, зелёный — оптимальный.
Оптимизация маршрута
Связанные темы
Углублённый уровень
Все темы за пределами школьной программы: графы, инверсия, комбинаторика.
Инверсия относительно окружности
Мощный инструмент олимпиадной геометрии. Превращает сложные задачи в очевидные.
Все задания ЕГЭ
Полная карта 19 заданий: от первой части до параметров и чисел.
Олимпиадная математика — это не «для гениев»
Это набор конкретных идей и алгоритмов. На первом уроке разберём задачу из твоей олимпиады — покажу, как подходить к нестандартным задачам системно.
Записаться на урок