Как стать автором
Обновить

Алгоритм Метромарафона. Как аналитик Яндекса просчитал, что все станции можно посетить за один день

Время на прочтение9 мин
Количество просмотров63K
Всего голосов 126: ↑122 и ↓4+118
Комментарии96

Комментарии 96

«Эхх, кабы раньше знать» что собираетсь — можно было бы заодно уровень шума померить, хотя бы просто при проходе одного поезда — там точность не нужна, плюс-минус лапоть…
Просто есть такая станция — Пражская. её чехи делали, ещё даже советские. Показали, так сказать, мастер-класс, да у нас мало кто понял: она — тихая. Реально тихая. Там можно не повышая голоса разговаривать посреди перрона когда оба поезда идут в разгон. Вроде ничего особенного внешне, и даже присмотревшись — никаких особенных чудес — просто грамотно по уму выполнена куча рекомендаций…
Очень хочется знать — столь ли она одна на всю москву такая тихая…

Открыли БКЛ (Большую Кольцевую Линию). Может, повторите?=) Хотя бы теоретически интересно было бы проверить, как БКЛ повлиял на исходную задачу.
Заодно и @impetus может удовлетворить свои потребности по шуму.
Понимаю, прошло 7 лет, ну а вдруг.

Ха! На Мякинино тоже очень тихо, правда не думаю, что имеет смысл их как-то сравнивать, там в основном ходят новые поезда, которые сами по себе тише.
На Пражской тоже только новые электропоезда ходят.
Возможно, что даже новее тех, что проходят мимо Мякинино
Она всегда была тихая — я самое раннее на ней бывал в 92-м где-то. и ещё тогда она меня удивила. И отдельно — удивило то, что никто не обращает на это внимания, и даже если кого знакомых обратишь, что вот идём разговаривем а ведь два поезда тормозят разом — реакция типа «а, что, да? хм, никогда не задумывался...»
А что мешает замерить, если автор выложил свой оптимальный маршрут? :)
А почему бы не упростить задачу — линию последовательных станций, без ответвлений, можно упростить до ребра графа просто с соответствующим большим весом? Когда движешься вдоль этой линии все равно вариантов нет — посещаешь каждую станцию.
Тогда будет не 200 узлов, а примерно 35.
Точнее так — линия последовательных станций заменяется на «длинную» линию с 1 промежуточной станцией + линию быстрого возврата (поездка обратном направлении, без выхода на станциях).
Я пробовал и такой вариант.
Он, действительно, сильно дешевле в плане расчётов.
Но есть два момента:
  • В таком формате нет возможности честно обсчитывать варианты «с хордами» — там граф действительно близок к полносвязному.
  • Если присмотреться, например, к последней схеме в посте, можно увидеть, что маршрут разомкнул серую ветку между Пражской и Янгеля. При подходе со «склеенными» участками такой возможности не будет.
А что если сделать следующим образом:
  1. Все тупиковые ветки (Парк культуры — Саларьево, и подобные) заменить на один узел с двумя ребрами (быстрым и медленным), как предлагал mtitov.
  2. Все отрезки между пересадками (Севастопольская — Бульвар Донского и подобные), где более одной станции, заменить на одну станцию.

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

Остается только вопрос с обсчетом наземных хорд, но если рассматривать только подземку, то вычислений должны быть сильно меньше.
Вероятно, можно.
Может, руки как-нибудь дойдут проверить и сравнить результаты.
Маньяки в хорошем смысле. :)

Не понял этого вот момента, можно пояснить?
> А итоговая оценка длительности самого лучшего маршрута получилась равной 19 часам 51 минуте.
> Наше итоговое время составило 16 часов 22 минуты

Откуда такое расхождение? В итоге ведь от всех внешних «хаков» маршрута отказались, то есть теоретическое время настолько отличаться от практики не должно.
Оказалось, что периодически вполне можно выйти из поезда, выбрать объект для съемки, сфотографировать его и вернуться в тот же поезд. Особенно в первый час работы метро, когда поезда идут с большими интервалами, а народу почти нет.

Интересно также и то, что час, сэкономленный утром-днём, вечером превратился в три часа, потому что вечером последние поезда идут с интервалами до 20 минут — и если бы мы не успели закончить до 11, мы бы с довольно высокой вероятностью ехали уже до закрытия.
Видимо, фотографий на последующих станциях делалось все меньше и меньше)
Пожалуй, что и нет. Напротив — под конец нам попалось несколько очень красивых станций.
Например, на Достоевской мы пропустили поезда 3-4, кажется. Потому что уж очень впечатляющая станция ;)
Кому как. Серые стены, чёрные силуэты. Плюс из произведений Достоевского выбрали для иллюстраций, кажется, все сцены смерти и убийства, какие там были.
Я не утверждаю, что она прекрасна или позитивна.
Я говорю, что нас впечатлила сильная атмосферность, без оценки.
Но это, действительно, весьма субъективный момент.
А расскажете, как Яндекс.Метро прогнозирует время? Особенно интересно, какие переходы учитываются, и как вы собирали данные.
Это не ко мне вопрос, но я попросил коллег ответить.
тратя на это лишнее время.
Лёша, и это пишет человек, у которого не только на ноутбуке наклейка my other computer is Hadoop cluster, но и сам кластер есть. Можно было бы просто промолотить все варианты, кажется :)

А генетические алгоритмы — красивая штука. Мне выходцы из Human genome project показывали продукт, который заточен на массовое тестирование продуктовых features с миллионами комбинаций. За счёт пары элегантных решений тест упихивается в формат несложного опроса считанных сотен людей и уделывает более привычные menu-based conjoint тесты на порядок.
Ну ты ж понимаешь ;) Интереснее же генетикой ;)
Можно было бы просто промолотить все варианты, кажется :)

Нет, нельзя. На то она и трансвычислительная задача, что для ее решения «в лоб» требуется компьютер размером с Землю, работающий 4 миллиарда лет.
НЛО прилетело и опубликовало эту надпись здесь
В таких задачках сложность прямого перебора оч. быстро растет (например экспоненциально от числа узлов) и если например потребуется 1e100 вариантов, то привычные нам ограничения по вычислительным мощностям особенно не имеют значения. Ну будет в миллиард раз быстрее, то будет вместо 1e90 секунд, считать 1e81 — никакой разницы. Ещё в триллион раз быстрее? пожалуйста 1e69 сек. (а наша вселенная всего прожила 4.36e+17 секунд).
Ого! Очень здорово!
Хотелось бы увидеть время, проведенное на каждой станции.
Как с пересадками? Фотографировать же надо каждую из двух-трех станций.
Увы — подробного фактического тайминга мы не вели — были сильно заняты.

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

Надо было заранее написать программу для смартфона или какого-нибудь PDA, чтобы она автоматически вела протоколирование маршрута!
В следующий раз будем умнее :)
Если вы фотографировали не на пленочную мыльницу, то время посещения каждой станции есть в метаинформации цифровых фотографий.
Действительно!
У нас, правда, было 6+ девайсов, на которые 3 человека фотографировали процесс.
И на данный момент у меня лично есть от силы 50% фотографий.
Но если когда-нибудь получится собрать всё это воедино — выложу.
А вот это отдельный важный момент, который надо помнить-учитывать и на который многие попадаются попусту —
ВСЕ ФОТИКИ ДОЛЖНЫ БЫТЬ ТОЧНО СИНХРОНИЗОВАНЫ ДО мероприятия —
тогда можно, автопереименовав потом по маске типа «YYYY-MM-DD_HH:SS-ник_фотографа» — сливать их в один каталог —
и будет очень удобная линейка для просмотра.
Не важно, что за мероприятие — встреча одноклассников, юбилей, просто посиделки в ресторане или дальный выход в горы — это реально удобно потом обрабатывать, что вручную. что скриптами.
А вот когда у каждого время на глазок, а то и плюс-минус час (зимнее-летнее), да ещё с минутами — наоборот, просто морока сделать единую ленту, а на самом деле это офигительно потом просматривать — когда какое-то событие оказывается буквально как в матрице — с разных ракурсов. И не важно что один щёлкал без остановки, а остальные изредка — каждый кадр автоматом находит своё место в каталоге даже просто средсвами ОСи и любого файлового менеджера без каких-либо сторонних программ.

Кстати, так потом и хранить их удобно все фотки — годами — даже не разбивая особо — и так гарантированно все события вместе скучкуются, не важно когда с какого фотика фотка до вас доберётся. Почему такое наименование не принято по-умолчанию в самих сфотиах и скачиваюх на комп программах — для меня загадка.
Это можно сделать и потом, главное чтоб было пересечение фоток по месту/времени. Скорректировать время всей серии фоток на константную величину не сложно.
Потому что этим занимается фотоальбом. А программы скачивающие фотки на комп — зло по определению. Кстати, минусы и двоеточие в маске времени — лишние.
а, кстати не подскажете пару таких софтинок, где это удобно делать — похоже я сильно отстал от жизни и мне поправить время-дату у пачки фоток, особо с переходом через 0 (с 0:20.35 1янв16 на 23:40.50 31дек15 например) — реально проблема (так и лежат на винте неправильные)
Недавно на старом компьютере под виндой фотки обрабатывал перед заливкой в облако — остановился на www.muralpix.com/jpgtime

Софтом под другие ОС, к сожалению, не интересовался.
Позанудствую, но двоеточие недопустимо в имени файла… Дефисом заменить нужно будет.
Можно я тоже понудю?
Да все можно сделать, даже на потолке спать! Здесь вопросы с совместимостью и с матами операционной системы на такие извращения. Есть стандарты/соглашения, их лучше все же поддерживать.
При расчёте времени проезда между станциями я лично пользуюсь простой формулой — 3 минуты на станцию. При этом результаты, показываемые Яндекс.Метро не сильно отличаются от этого расчёта.
16 часов и 22 минуты на 200 посещённых станций дают в итоге чуть меньше 2 минут нахождения на каждой станции, которые легко компенсируют возвраты с конечных радиальных станций метро без выхода на них.
Ну в целом, такое «правило Буравчика» выглядит, и правда, довольно реалистичным.
Сильные отклонения от него возникают, как водится, на граничных случаях: хвосты радиальных веток, где перегоны, бывает, существенно длиннее, а также раннее утро и поздний вечер, когда интервалы существенно меняются.
НЛО прилетело и опубликовало эту надпись здесь
Предупреждение: если вы умеете решать задачу коммивояжёра на 200 узлах

Конечно же вы имели в виду на 20 000 узлах?
НЛО прилетело и опубликовало эту надпись здесь
При случае попробую, спасибо.
Предлагаю усложнить задачу. Выходить на каждой станции на улицу и фотографировать окрестности наряду с самой станцией. Получился бы этакий контраст подземного и наземного миров. Некоторые станции располагаются в лесу, некоторые в горах или на реке, другие в гуще жилых массивов, площадях, вокзалах, аэропортах и портах.

Так сказать, таким образом передать атмосферу жизни огромного города. Думаю, что по времени это уложится в лимит в 20 часов.
Я не представляю, как это можно успеть за 20 часов. Но если кто сдюжит — сниму шляпу.
И к тому же совсем не бюджетно выйдет — 199 платных входов на станции после фотографирования на улице.
А у безлимитного билета блокировка на 7 минут, выходит 23 часа и 13 минут минимум — то есть не уложиться в 20.
Можно 2 безлимитных билета, и чередовать их.
Забавно.
Экономический аспект мы не прорабатывали всерьез, но с учётом блокировки, действительно, это блокер.
С другой стороны, можно взять по два-три безлимитных билета на лицо и использовать их «пунктиром», это позволит исключить лишнее время «загорания» у турникетов.

Не уложится. Даже если предположить, что все 200 станций соединены в одну длинную ветку, поезда ждать не надо, а все перегоны занимают 3 минуты – только на перегоны придется потратить 9 часов 57 минут, то есть половину от всего отведенного времени.
Следовательно, даже в этом случае на каждой из станций останется всего 3 минуты 0.9 секунд на то, чтобы:


  • выйти из вагона
  • дойти до эскалатора (причем, не получится просто всегда ездить, скажем, в первом вагоне: на некоторых станциях выход будет только из последнего)
  • подняться на эскалаторе (причем, вероятнее всего, не пешком: я лично не представляю, какая нужна физическая подготовка, чтобы за день бодрым шагом подняться по всем эскалаторам)
  • выйти
  • сфотографировать
  • зайти
  • спуститься по эскалатору
  • сесть в поезд

За три минуты это можно успеть сделать разве что на станциях мелкого заложения (а их всего 107, то есть чуть больше половины), и то, придется побегать.
Подобное можно было бы попробовать провернуть за два или три дня, но это уже не так красиво звучит.

Эскалаторы. Я сомневаюсь что даже в Питере это можно за сутки провернуть. Но можно читерить на пересадочных станциях — выходить с одной, а заходить в другую. И на некоторых соседних, особенно если подключить прокат Велогорода.
У бОльшей части станций — выходы это просто выход из перехода «в кучу ларьков» возле улицы или подобное — на автобусную остановку, в кусты или т.п — т.е надо или заранее выбирать один выход из монгих, или выходить всем каждому в свой (а бывают и ооочень дальние — напр парк победы)
Кроме того — для человека состояние «туда и сразу обратно» — психологически неприятное как бы не играться с мотивациями — и к сотой станции это накопится в очень большое как минимм раздражение.
Подскажу дополнительное улучшение, раз уж вы работали командой.
Решать задачу «объезда» лучше в воскресенье и нужно два-три «друга» на машинах. Которые будут объезжать конечные станции метро по кольцу.
Схема похожа на вариант с такси, но вы сможе замкнуть все конечные станции в петли.
Когда Вы подъезжаете на конечную, вас «подхватывает» друг и везет до следующей конечной. Полное кольцо по МКАД на машине — это час. Почти все линии метро выходят близко к МКАД. Единственный «пропуск» — смыкание веток на Алма-Атинской.
Это интересный вариант.
Но есть, как водится, нюансы:
  • Дружественные товарищи из метро шепнули нам, что в выходные интервалы между поездами в 1.5-2 раза выше чем в будни. Т.е. народу, конечно, меньше, но можно сильно проиграть по ожиданию поездов.
  • Тайминг наземного транспорта существенно менее надёжен, чем тайминг метро. В метро практически нет риска встрять в «пробку» на час.
  • Интересно также то, что метро постепенно доросло до состояния, когда «хорды» соединяют уже чуть ли не половину веток (особенно в южной части Москвы) — таким образом выигрыш от наземных хорд сильно скрадывается, если добавить, условно, по 5 минут на каждый вход и выход из метрополитена.
  • В целом, мы решили, что есть некоторый особый шарм сделать маршрут без единого выхода.
В 1975-ом году в Нью-Йорке это занимало двое суток. У них метро сильно больше Московского?

image

(с) Йодан Э. «Структурное проектирование и конструирование программ»
Не обязательно больше. В 1975-ом могли поезда сильно реже ходить (если что, текущий рекорд по NY, согласно википедии, составляет чуть меньше 22 часов). Ну или просто более долгие перегоны или переходы, например.
Да, сильно больше (по крайней мере, сейчас) — 200 станций и 12 линий в Москве против 422-469 станций и 24-34 линий. Ну и ходит метро в Москве почаще — от буквально одной минуты до максимум 10 (ни разу не заставал, но википедия пишет, что бывает), а в Нью-Йорке интервал в 10-15 минут — обычное дело.
Да там ещё и маршруты и их расписаине надо учитывать, т.е задачка значительно сложнее.
В статье про программиста, ставшего мясником, пишут: «Метро в Нью-Йорке довольно медленное, поезда ходят редко».
То есть можно просто прийти в Московский метрополитен, сказать что хочешь проехать по всем станциям. Ответить «сам не знаю зачем» и тебе даже выделят специального сопровождающего?
Если вам нужен сопровождающий по метро, вы можете оставить заявку вот тут и вам его бесплатно выделят. Ровно такой сопровождающий с нами и ездил.
Я думал это специальный сервис для маломобильных лиц.
Основания для заявки могут быть различными.
В частности, насколько я помню из разговора с сопровождающим, они же занимаются организацией экскурсий по метро (в основном детских, но не только). В нашем случае основанием было существенно длительное пребывание под землёй — гипотетически могли возникнуть какие-то проблемы со здоровьем.
Так весь день с вами и катался? Круто же! Причем с обеих сторон круто — ему тоже не часто такая экспедиция выпадает.
Кстати — поскольку он сотрудник — он мог изредка попросить машиниста «чуток подождать» (ну там секунды, если это не в часы пик — что бы вы успели на тот же состав)
Да, Максим честно отъездил с нами весь маршрут.
С машинистами он, вроде, не коммуницировал ;)
Интересно, с какой целью его вам выделили? Он какую-то особую функцию выполнял?
Я бы тоже выделил — что бы иметь доступ к результатам например и вообще самим знать, что такое возможно. (и теперь у них есть возможность посылать людей в такие командировки — промерить например что-то по всем станциям) Хотя, от бюрократической госструктуры это действительно удивительно.
Я думаю, просто за порядком присматривать.
Было бы очень неудачно получить какой-то инцидент накануне дня рождения метро
> Тут я вспомнил пару довольно древних программ с народными замерами времени – pMetro и mMetro – это, если кто не знает, такие десктопные калькуляторы метромаршрутов. Первая почти перестала официально обновляться в 2011 году, вторая – ещё раньше, но всё лучше, чем ничего.

> Среди файлов в папке pMetro обнаружился Moscow.pmz, на деле оказавшийся обычным zip-архивом с кучей файликов в архаичном .ini-формате. Там нашлась почти вся нужная информация (на схеме не хватало нескольких самых свежих станций). Я наваял одноразовый парсер всего этого в tsv и довбил руками отсутствующие станции и перегоны, «прозвонив» тайминги для них на Яндекс.Метро. Координаты новых станций я взял из статей Википедии.

Программа PMetro сама по себе хоть и старая, но схемы для неё обновляются весьма оперативно. Их нужно скачивать отдельно с pmetro.su/Maps.html

Обновлённая схема с Саларьево, к примеру, вышла на следующий день после открытия этой станции.
Да, спасибо, теперь буду знать.
Исходников никуда не выкладывали?
Поиграться с данными хочется.
Пока нет, руки не дошли.
Может, как-нибудь соберусь, тогда дам тут ссылку.
Будет очень хорошо, хочется повторить для питера.
Ну для Питера сначала всё равно надо собрать граф и статистику, у меня их нет.
Ну для Питера все шансы успеть. 5 линий проехать, должно быть просто.
отличный пост!
Спасибо!
Тут должно быть видео финальной погони из Шоу Бенни Хилла под Якети Сакс, но мне лень искать…
Сколько жетонов потрачено? Или в М-ве на конечных можно перейти на другую сторону?
В Москве карточки. Конечные станции ничем не отличаются от любой другой. Заплатить нужно только один раз и кататься весь день.
По одной поездке на человека потратили.
НЛО прилетело и опубликовало эту надпись здесь
Почти вся филевская линия с островными платформами и там спокойно можно перейти с платформы на платформу. Из таких станиций, где нельзя — только Выхино и вспоминаетя.
Партизанская ещё, насколько я помню.

Нет. На партизанской есть штатный переход между лестницами у основания памятника.

Да, действительно, значит, я его просто не заметил — это была уже 196 станция на маршруте ;)

А для двухплатформенных островных станций вы посещали любую из платформ? (Парк победы, Кунцевская, Каширская, Варшавская, Партизанская, Выхино, Полежаевская).

Нет. Там, где по маршруту не было обратного проезда через другую платформу, мы ногами ходили на соседнюю и обратно.
Но вот на Партизанской, вроде как, не ходили.
Интересно, какое расстояние в итоге проехали?
Если вы на каждой станции были, например, полторы минуты, это получается 5 часов стоянки на станциях. Тогда в дороге 11 часов 22 минуты. Если взять среднюю скорость поезда 60 км/ч, то получится 682 км.
Из вики: длина метро 333,5 км. Средняя скорость 41,24 км/ч.
Ну если учитывать, что мы ездили почти 17 часов, то наша средняя скорость получилась примерно 19 км/ч.
А если брать во внимание, что мы (на глаз) примерно треть-половину участков проезжали дважды, то ближе 25-30 км/ч.
Я писал про среднюю скорость поезда, а не среднюю скорость вашего перемещения.
У вас же есть все расстояния между станциями и есть маршрут. Можете посчитать общую длину маршрута?
Это правда.
Я к тому, что проехали мы около 400-450 км в итоге.
Расстояния у меня только географические есть, длина перегонов может отличаться (там есть изгибы и перепады высот).
Но при случае можно будет посчитать, да.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий