Maria Petrova
июнь 2015.
1938

Сколько минимум времени займет проехать все станции московского метро (необязательно высаживаться на каждой), и по какому маршруту нужно двигаться?

Ответить
Ответить
Комментировать
0
Подписаться
3
1 ответ
Поделиться

Это задача коммивояжёра, решается в теории графов. Собирайте исходные данные: граф станций, время езды по всем перегонам с учетом остановок (и то и другое есть общедоступная информация) — и обращайтесь к математикам. Я, однако, полагаю, что погрешность, связанная прежде всего с переходами, а также с различным временем остановки на станциях, которое для разных станций не одинаково зависит от времени, будет велика. Тогда имеет смысл добавить в граф связи, соответствующие переходам, и попробовать решить задачу в общем виде, коль скоро ваше время перехода между станциями неизвестно; и шаманить с данными о времени перехода между станциями разных людей относительно минимальных данных о том, как вы ходите.

Ответить