Обложка статьи «Как работает лифт в небоскребах? Алгоритмы + задачи с собеседований»

Как работает лифт в небоскребах? Алгоритмы + задачи с собеседований

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

История

Первые лифты приводились в движение паровой машиной, их работой управлял оператор. В 1924 году компания Otis представила первый автоматический лифт, управляемый логическими реле. Это позволило увеличить скорость передвижения кабины. Через 13 лет, Otis показала систему помогающую планировать работу лифта в периоды высокой нагрузки. Так выглядели первые автоматические лифты:

В 1948 году Otis начал производить автоматические лифты, которые уже умели изменять скорость, адаптировать своё расписание к периодам нагрузки, не останавливаться при полной загрузке кабины. В них появилась функция автоматического закрытия двери после определенного времени простоя.

Управление с помощью реле использовалось до 1980 годов, когда их начали вытеснять микропроцессоры. Микропроцессоры потребляли меньше энергии и занимали гораздо меньше места.

управляющие реле автоматического лифта Otis

Так выглядела управляющая система реле лифта Otis. Картинка с сайта

Алгоритмы работы лифтов

Простой алгоритм

Большинство обычных лифтов работают по простому алгоритму:

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

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

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

Группировка по месту назначения

Этот алгоритм принципиально отличается от простого: на каждом этаже, вместо кнопки вызова лифта, находятся кнопки для указания, на какой этаж нужно пассажиру. Благодаря этой информации, лифт может собрать в одной кабине всех, кому нужно на конкретный этаж. Это позволяет не тратить время на лишние остановки. Однако время ожидания в среднем немного увеличится.

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

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

Задачи с собеседований

Алгоритм работы лифта — нетривиальная задача, вопросы о нём задают даже на собеседовании в Google. Вот пример задания:

Как должен работать лифт в 40-этажном офисном здании, на каждом из этажей которого работает около 100 человек, чтобы обеспечить наиболее эффективное заполнение и опустошение здания во время стандартного 9 часового рабочего дня, с двумя выходными, учитывая возможные пробки?

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

Такую задачу предлагает компания Synergy Team:

Требуется разработать программу — эмулятор лифта. При старте программа должна запрашивать этажность дома. Программа должна выводить пользователю текущее состояние лифта (номер этажа, направление движения (вверх, вниз, остановка). Скорость движения лифта: 1 этаж в секунду. Пользователь должен иметь возможность в любой момент, включая периоды движения лифта, «нажать» кнопку вызова на любом этаже. Во время движения может быть нажато произвольное количество кнопок «вызов» на разных этажах. Пользователь должен иметь возможность «нажать» кнопку любого этажа на вызывной панели внутри кабины лифта. При написании программы надо руководствоваться собственными здравым смыслом и знаниями о работе лифтов. Остальные ограничения по работе программы должны устанавливаться программистом по его собственному усмотрению. Дополнительные уточнения по заданию не выдаются.

Другие логические задачи с собеседований можно посмотреть здесь.

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