Один билет — целый Нью-Йорк: самый длинный маршрут в метро без повторов
Энтузиасты нашли самый длинный непрерывный маршрут в метро Нью-Йорка, не посещая одну станцию дважды.
Помните, как в детстве мы пытались проехать на автобусе до конечной, чтобы посмотреть, что там? Разработчик по имени Джон решил пойти дальше и составил оптимальный маршрут, который проходит через максимальное количество станций нью-йоркского метро, ни разу не заезжая на одну и ту же дважды.
Что получилось?
- Маршрут охватывает более 200 станций.
- В пути придётся провести около 14 часов.
- Используется все 24 линии метро.
Проект SingleRide — это не просто забавный челлендж, но и отличная демонстрация возможностей графовых алгоритмов. По сути, это задача поиска гамильтонова пути в транспортной сети — классическая NP-полная задача, которую автор решил эвристически.
Для IT-специалиста такой проект — напоминание о том, как алгоритмы могут оптимизировать маршруты не только для метро, но и для доставки, логистики или даже для планирования тестовых покрытий в вашем коде.
Комментарий студии METABYTE: Если вы думали, что графы нужны только для собеседований, то вот вам живой пример их практической пользы. Хотите оптимизировать свои бизнес-процессы с помощью алгоритмов — мы знаем, как это сделать.