♾️ Иногда даже триллиона вычислений в секунду недостаточно
♾️ Иногда даже триллиона вычислений в секунду недостаточно Задача коммивояжёра выглядит довольно просто: нужно найти самый короткий маршрут между городами, побывав в каждом и вернувшись в исходную точку. Но стоит увеличить их количество, и начинается комбинаторный взрыв. Для 100 городов существует около 4,7 × 10¹⁵⁵ возможных маршрутов. Даже если компьютер будет проверять триллион вариантов каждую секунду, полный перебор займет порядка 10¹³⁶ лет. Для сравнения: возраст Вселенной около 13,8 млрд лет. Поэтому в алгоритмическом программировании важно не просто написать работающий код, а найти способ решить задачу эффективно. На примере задачи коммивояжёра показываем в карточках, почему иногда даже невероятно быстрый компьютер не спасает плохой подход. ⚡А искать эффективные решения в условиях соревнования участникам предстоит уже 18 октября на Финале Международного чемпионата по алгоритмическому программированию «РуКод». Финал пройдет в командном формате — в команде может быть от 1 до 3 участников. 🔥 Зарегистрироваться: https://rucode.net/0jrx