Один билет — целый Нью-Йорк: самый длинный маршрут в метро без повторов

Помните, как в детстве мы пытались проехать на автобусе до конечной, чтобы посмотреть, что там? Разработчик по имени Джон решил пойти дальше и составил оптимальный маршрут, который проходит через максимальное количество станций нью-йоркского метро, ни разу не заезжая на одну и ту же дважды.

Что получилось?

• Маршрут охватывает более 200 станций.
• В пути придётся провести около 14 часов.
• Используется все 24 линии метро.

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

Для IT-специалиста такой проект — напоминание о том, как алгоритмы могут оптимизировать маршруты не только для метро, но и для доставки, логистики или даже для планирования тестовых покрытий в вашем коде.

Комментарий студии METABYTE: Если вы думали, что графы нужны только для собеседований, то вот вам живой пример их практической пользы. Хотите оптимизировать свои бизнес-процессы с помощью алгоритмов — мы знаем, как это сделать.