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

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

История

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

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

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

Так выглядела управляющая система реле лифта Otis. Картинка с сайта https://elevation.fandom.com/wiki/Elevator_control_system

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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