company_banner

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

    12 мая мы с товарищами зашли в московское метро с его открытием утром и, не выбираясь наверх, посетили все 199 доступных в данный момент станций до закрытия метрополитена. Зачем мы всё это сделали – совершенно не ясно, но я попробую рассказать, как так получилось.


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



    По мере изучения вопроса я обнаружил, что идея сама по себе не то чтобы очень нова – в нью-йоркской подземке аналогичные соревнования проходят с 1966 года. Что же касается московского метро, то ЖЖ-пользователь estrella-de-sur полгода назад проехал его за 12 часов 36 минут (расчётное время – 11 часов 50 минут) по правилу «один шаг на каждую станцию». Но у нас была другая задача – мы хотели выйти на каждой станции и по возможности красиво её сфотографировать. Это означало, что нам в большинстве случаев придётся ждать на ней следующего поезда. Исходя из этого я и строил расчёт.


    Предупреждение: если вы умеете решать задачу коммивояжёра на 200 узлах (с помощью генетических алгоритмов или без них) – вас, скорее всего, ждут в другом месте. Можете просто пролистать пост и посмотреть картинки.


    Где взять данные


    Первым делом для такой задачи нужно было оцифровать граф метро (узлы – станции, рёбра – переезды и переходы) и дополнить его элементы разной полезной информацией: для станций – географические координаты, время открытия-закрытия и интервалы следования поездов в разное время суток; для рёбер – время перегона или перехода между станциями.


    Станций в Москве много (Саларьево на тот момент ещё не открыли, но всё равно хватало), и руками всё это делать не хотелось совершенно. Тогда я обратился к сайту Яндекс.Метро. Для старта это было в самый раз, но этот сервис использует усредненные оценки времени, а для серьезного расчёта нужно было иметь более точные сведения. Тут я вспомнил пару довольно древних программ с народными замерами времени – pMetro и mMetro – это, если кто не знает, такие десктопные калькуляторы метромаршрутов. Первая почти перестала официально обновляться в 2011 году, вторая – ещё раньше, но всё лучше, чем ничего.


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


    Схема в итоге получилась вот такой (проекция, конечно, не Меркатора, но суть передаёт):



    (тут я нарисовал ещё и линию монорельса, но, в дальнейшем, было решено от неё отказаться)


    Теперь предстояло попробовать со всем этим взлететь.


    Геном коммивояжёра


    Итак, нужно было решить классическую задачу коммивояжёра в постановке на неполном графе над 200 вершинами. Опыт предков учит нас, что задача эта NP-полна и даже, вероятно, трансвычислительна. В переводе на русский первое означает, приблизительно, что нам не известно способа нахождения её наилучшего решения, кроме перебора всех возможных ответов, а второе – что перебирать нам придётся довольно долго (не менее, чем миллиарды лет). На практике, однако, можно попробовать организовать перебор таким хитрым способом, чтобы постепенно находить всё более хорошие решения и остановиться «по готовности».


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


    Но продолжим. Как я уже сказал, можно организовать перебор таким способом, чтобы постепенно находить всё более хорошие решения, и, если нам не нужно гарантий того, что найденное решение самое лучшее, мы можем остановиться в любой момент, когда сочтём, что текущий лучший результат «достаточно хорош» для нас. Один из древних классических подходов в такой ситуации – использование генетических алгоритмов.


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


    Но дьявол, как водится, в деталях. Во-первых, надо хорошо выбрать представление информации в геноме. Можно, например, сделать геномом вектор с номерами всех станций в порядке их следования в маршруте. Чем это плохо? Геномы разных маршрутов будут разной длины – им будет неудобно скрещиваться. А ещё среди случайных значений генома будет много невалидных маршрутов – таких, которые не позволяют посетить все станции. Другими словами, в пространстве значений генома концентрация действительно возможных кандидатур будет невысокой – а значит, нам отдельно придётся проверять каждого кандидата на валидность, тратя на это лишнее время.



    Гораздо удобнее объявить геномом перестановку длины 200 – т.е. такой вектор длины 200, в котором каждая станция встречается лишь 1 раз. Правда, при таком подходе соседними в маршруте могут оказаться станции, между которыми нет прямого соединения. Не беда – мы можем перейти к полному графу, рассчитав кратчайший маршрут по графу между каждой парой вершин (в лоб это несложно сделать за О(|V|^3) операций, что в нашем случае – не так много). Важно отметить, что этот кратчайший маршрут также может быть различным в разное время суток, с учётом динамики расписания. Поэтому, имеет смысл рассчитать такие таблицы для каждого среза расписания интервалов.


    Во-вторых, нужно пошаманить с разными видами мутаций и скрещиваний. Науки тут особо нет, сплошная эмпирика, направленная главным образом на то, чтобы, с одной стороны обеспечить быструю сходимость, а с другой – возможность выбраться из эволюционного тупика локального оптимума. В итоге, я остановился на наборе из следующих преобразований:


    • случайная перетасовка случайного интервала генома – это быстрая мутация, но не очень аккуратная, на финальных этапах эволюции она с очень низкой вероятностью может улучшить уже неплохое решение.
    • зеркальное отражение случайного интервала генома – может быть полезно для сильных изменений (выхода из локального оптимума), с шансами сохранить некоторый порядок (высокое качество) маршрута в контексте нашей задачи
    • перестановка X пар случайных значений в геноме местами – хорошая мутация, но медленная, из тупика на ней не выберешься.
    • скрещивание (“crossover”) двух геномов – сначала выбираем точку скрещивания на геноме, отрезаем по ней хвосты наших геномов и меняем их местами. После этого мы можем получить некорректный маршрут – поэтому уникализируем результат и добавляем все потерянные узлы, например, в случайные места генома.


    Итого, на каждой итерации мы некоторое подмножество лучших особей подвергаем их различным мутациям и формируем из их потомков новое поколение, досыпая к ним несколько полностью случайных маршрутов, чтобы не пасть жертвами инбридинга. Расчёт такой эволюции длиной в 50000 поколений наколеночным скриптом на питоне занимает на моём домашнем десктопе в среднем 20 минут. А чтобы было не так скучно ждать, можно подглядывать за ним в динамике, отрисовывая лучшую особь каждого, скажем, сотого поколения. Вот небольшая гифка, показывающая фаворитов нескольких первых тысяч поколений в цикле:



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


    Важный момент – если мы видим, что независимые прогоны оптимизации дают нам существенно разные ответы, пусть и похожие по качеству, значит, велика вероятность того, что мы так и не нашли глобальный оптимум. Но нас устроит и достаточно хорошее его приближение, которое можно попробовать получить «мультистартами» – запустить алгоритм много раз (в т.ч. с разными настройками, например, задавая начало и конец маршрута равными различным фиксированным веткам) и выбирать лучший из наблюдаемых результатов.


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



    А итоговая оценка длительности самого лучшего маршрута получилась равной 19 часам 51 минуте. Напомню, интервал работы московского метро – примерно 20 часов, а все исходные данные об интервалах следования поездов я взял из любительских замеров. Если бы у меня получился маршрут в 10 или 40 часов – всё было бы, так или иначе, ясно. Но тут запас составлял всего 9 минут при неизвестной (но явно не маленькой) погрешности.


    Назад, в реальный мир


    Примерно в этот момент идея проверить этот маршрут на практике окрепла. К тому времени несколько моих друзей уже были в курсе моих странных изысканий. Пара из них оказались достаточно безумными, и вот – мы собрали команду для проверки боем. Но, так как риски «не попасть» в отведённое время были довольно высокими, я решил сначала проверить ряд альтернативных вариантов.


    Вариант «Вернуть монорельс». Любопытный факт: проезд от Тимирязевской до ВДНХ на метро с пересадкой через кольцо занимает меньше времени, чем с переходом на монорельс и обратно (по данным pMetro, без необходимости выходить на каждой станции). Вариант отвергнут.


    Вариант «Добавить наземный транспорт». Идея в том, что можно попробовать перемещаться между конечными разных линий на общественном транспорте по земле. За данными по пересадкам на наземный траспорт я пошёл к Диме Крюкову из Яндекс.Расписаний. Оказалось, что точной информации о пересадках между метро и наземном транспортом у нас сейчас нет, зато есть подробная информация о всех наземных остановках и маршрутах автобусов/троллейбусов/трамваев.


    Делать нечего, пришлось делать матчинг остановок со станциями по названиям. Там обнаружилось довольно много подводных граблей, о которых рассказывать не очень интересно. Скажу только, что в Москве нашлось ровно 999 наземных остановок, названных «в честь» той или иной станции метро (не считая нескольких «метромостов», «метродепо», «метрогородков» и прочего). А ещё, некоторые остановки до сих пор названы в честь уже переименованных станций метро. Но это мелочи.


    Вот вам, кстати, схема с найденными наземными «хордами»:



    Но, так или иначе, когда я добавил оценки по времени выхода + ожидания наземного транспорта + проезда + возвращения в метро, оказалось, что эти «хорды» не очень помогают – концепция «метро-трипа» теряет исходную чистоту, а расчётный выигрыш составляет всего 15-20 минут. Вариант отвергнут.


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


    После оптимиазации получился вот такой интересный маршрут с четырьмя «хордами»:



    Такой маршрут по расчётам оказался примерно на 30 минут короче, чем мой оптимальный. Вариант отвергнут, как «не спортивный».


    Итоги


    После бурных дебатов мы решили ехать оптимальный маршрут без «хорд» и с выходом на каждой станции. В конце концов, если б мы хотели просто номинально объехать все станции, можно было бы вообще не выходить из вагона и получить время порядка 12 часов. Но московское метро по праву считается одним из красивейших метрополитенов мира, так что лучше насладиться частью станций, чем посетить все, но не увидеть ничего.


    Настрой был серьезным, поэтому на данном этапе мы обратились в Московский метрополитен, и провалидировали с их помощью наш маршрут. Нам выделили специального сопровождающего из Центра обеспечения мобильности пассажиров, разрешили вести фото и видеосъемку и даже позволили изредка пользоваться служебными туалетами, которые, как выяснилось, есть на каждой станции.


    Итак, 12 мая мы с товарищами зашли в московское метро ранним утром и, не выбираясь наверх, посетили все 199 доступных в данный момент станций до закрытия метрополитена. Зачем мы всё это сделали – совершенно не ясно, но суть не в этом, главное – нам это удалось.


    У нас не было задачи проехать всё метро «на время», скорее мы хотели действительно посмотреть все станции за один день. Мы выходили на каждой станции, делали фотографии (пару сотен фото можно найти в наших различных лентах в соцсетях) и ехали дальше – иногда в том же поезде, а иногда пропуская по несколько поездов к ряду, если станция была настолько интересной, что нам хотелось провести на ней побольше времени.


    Наше итоговое время составило 16 часов 22 минуты, и мы с удовольствием публикуем наш маршрут, с тем, чтобы любой желающий мог попробовать улучшить это время.



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

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

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

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

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

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

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

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

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

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

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

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

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

                                      Конечно же вы имели в виду на 20 000 узлах?
                                      • +1
                                        Подразумевалось «на 200 или более», конечно же.
                                        Про TSP была ещё вот такая красивая история.
                                        • 0
                                          В свое время для прогулочных кластеров использовал Concorde. Шустро считает даже для тысячи точек, обещают отклонение от оптимального решения на какие-то мизерные проценты.
                                          • 0
                                            При случае попробую, спасибо.
                                      • 0
                                        Предлагаю усложнить задачу. Выходить на каждой станции на улицу и фотографировать окрестности наряду с самой станцией. Получился бы этакий контраст подземного и наземного миров. Некоторые станции располагаются в лесу, некоторые в горах или на реке, другие в гуще жилых массивов, площадях, вокзалах, аэропортах и портах.

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

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


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

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

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

                                                    image

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

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

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

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

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

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

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

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

                                                                                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                                                Самое читаемое