♾️ Иногда даже триллиона вычислений в секунду недостаточно

Задача коммивояжёра выглядит довольно просто: нужно найти самый короткий маршрут между городами, побывав в каждом и вернувшись в исходную точку. Но стоит увеличить их количество, и начинается комбинаторный взрыв.

Для 100 городов существует около 4,7 × 10¹⁵⁵ возможных маршрутов. Даже если компьютер будет проверять триллион вариантов каждую секунду, полный перебор займет порядка 10¹³⁶ лет. Для сравнения: возраст Вселенной около 13,8 млрд лет.

Поэтому в алгоритмическом программировании важно не просто написать работающий код, а найти способ решить задачу эффективно. На примере задачи коммивояжёра показываем в карточках, почему иногда даже невероятно быстрый компьютер не спасает плохой подход.

⚡А искать эффективные решения в условиях соревнования участникам предстоит уже 18 октября на Финале Международного чемпионата по алгоритмическому программированию «РуКод».

Финал пройдет в командном формате — в команде может быть от 1 до 3 участников.

🔥 Зарегистрироваться: https://rucode.net/0jrx