С ростом этажности наших городов всё больше людей ежедневно пользуется лифтами. Но мало кто из нас задумывается о том, как всё это лифтовое поголовье умудряется более-менее эффективно развозить в течение дня уйму людей, особенно в часы пик. Существует ряд алгоритмов движения лифтов, которые исходят из разных условий — например минимизации времени ожидания лифта. Но давайте подумаем, как можно разработать лифтовый алгоритм.
При всей кажущейся простоте задачи довольно сложно создать лифтовый алгоритм для реального применения в зданиях. К тому же такие вещи считаются коммерческими тайнами и патентуются. Поэтому попробуем сделать упрощённую модель:
В здании на каждом этаже живёт одинаковое количество людей. Есть несколько лифтов, лестниц нет. Для простоты будем считать, что на каждом этаже одинаковое количество пассажиров ждёт лифт. Также мы знаем, что в течение дня есть несколько часов пик. Нужно придумать такой алгоритм, чтобы минимизировать время ожидания всех людей в здании.
фильм про устройство лифта
Здесь можно выделить несколько затрудняющих решение задачи условий:
- Произвольное количество этажей.
- Произвольное количество лифтов.
- Есть периоды часов пик.
- Распределение лифтов должно описываться на основе функции от нагрузки и времени ожидания.
Также будем учитывать ещё несколько переменных и констант:
- Количество людей на каждом этаже — 100 человек.
- Время, за которое лифт проходит один этаж без остановки, — 5 секунд.
- Время стояния лифта на этаже — 20 секунд.
Конечно, в реальной жизни скорость прохождения этажа лифтом может быть нелинейной, ведь он разгоняется и тормозит. Но для упрощения расчётов мы это отбросим. Если вам это покажется излишним упрощением задачи, то можете потом самостоятельно ввести эти условия в алгоритм.
Заметим, что пока ничего не сказано о грузоподъёмности лифтов. Здесь мы тоже радикально упростим себе жизнь — будем считать, что лифт вмещает сколько угодно людей. Нереалистично, согласен. Но зато, когда у нас появится первая версия алгоритма, будет проще ввести такие условия:
- Если лифт полон, то он опускается на этаж ниже.
- После высадки всех пассажиров лифт возвращается на предыдущий этаж.
Алгоритм распределения лифтов
Как понятно из рисунка, каждому лифту присваивается определённая зона ответственности. Это сделано для того, чтобы усреднить время ожидания на каждом этаже, а также нагрузку на каждый из лифтов. Каждый лифт может проходить цикл «этаж 1 -> 2 -> 3 -> 0». Давайте посчитаем, сколько времени занимает полное прохождение цикла:
- Время прохождения одного этажа умножаем на количество этажей в цикле и умножаем на два (потому что лифт идёт вверх, а потом вниз). В нашей модели получается:
5 секунд * * 2. - Количество остановок c первого по последний этажи умножаем на продолжительность остановки. В нашей модели:
20 секунд * .
Галилео | Лифт Elevator
Теперь посчитаем усреднённое количество людей, которых мы перевезём в течение одного цикла:
- — это время завершения одного часа пик.
- — количество этажей, на которых останавливается лифт.
Теперь создадим два массива:
- Массив здания. Количество ячеек равно количеству этажей. Содержимое ячейки обозначает количество ожидающих на этаже людей.
- Массив лифтов. Количество ячеек равно количеству лифтов. Содержимое ячейки обозначает «верхний» этаж, до которого ездит данный лифт. Например, в массиве [2, 3, 4] описаны три лифта: первый ездит не выше второго этажа, второй — не выше третьего, третий — не выше четвёртого.
Начнём с того, что первый массив пуст, а затем при каждом добавлении этажа в массив мы станем приписывать к нему лифт. Характер добавления будет меняться, как мы увидим ниже, но в целом он описывается довольно просто. Этажи добавляются в циклы до тех пор, пока грузоподъёмность не станет ограничением. Введём маленькую функцию:
время прохождения цикла + ((время прохождения цикла / 100) * усреднённая загрузка лифта)
— это целое число, пока оно не достигнет 100 секунд (достаточно долго для пребывания в лифте), а затем в уравнении начинают учитываться . Поскольку наша задача была описана довольно расплывчато, то и в решении есть некоторая неясность. Таким образом, функция добавления этажа в зону ответственности лифта довольно условна, хотя и эффективна при управлении нагрузкой. Вероятно, есть и более хорошее решение.
Реализация функции добавления этажа (Python):
# (Индекс * 5 секунд) + (20 секунд * (Индекс – Предыдущий индекс)) # Если сумма предыдущих циклов/остановок больше, чем # (время прохождения этажа * 2) + время ожидания, тогда увеличиваем этажность # предыдущего цикла, то есть лифт[2]+=1 # e обозначает массив лифтов (зоны ответственности) def addFloor(e): best = 99999 for i in range(1, len(e)): cirTime, avgCarry = eleLoop(e, i) if cirTime + ((cirTime / 100) * avgCarry) < best: elevatorNumber = i best = cirTime + ((cirTime / 100) * avgCarry) for i in range(elevatorNumber, len(e)): e[i] += 1 return e
Обратите внимание: каждый раз, когда elevatorNumber выбирает лифт выше текущего значения elevatorNumber , увеличивается размер массива лифтов:
for i in range(elevatorNumber, len(e)): e[i] += 1
В каждом цикле мы на единицу увеличиваем максимальный этаж после выбранного лифта. Поэтому в цикл выбранного лифта мы добавляем ещё один лифт. Функция eleLoop(e, i) просто определяет время и среднее количество перевозимых в цикле пассажиров.
Теперь напишем функцию прохождения по этажам и создания самих этажей. Обратите внимание: в нашем случае количество людей на этажах считается одинаковым. Если решить эту задачу, то потом будет достаточно легко учитывать и разное количество людей на этажах.
# Распределение лифтов. # Elevator[] обозначает начальную группу остановок. def elevatorAllocation(building, elevatorCount): elevator = [] for i in range(elevatorCount + 1): elevator.append(0) for i in range(1, floorCount): elevator = addFloor(elevator) printeleLoop(elevator)
Этого вполне достаточно. Решение относительно прямолинейное, так что здесь многое можно улучшить.
Реализация на Python
Теперь соберём разные части алгоритма вместе, добавим несколько функций для вывода данных и создадим маленький симулятор.
- 10 этажей.
- 3 лифта.
- 1 час пик.
- 5 секунд на прохождение этажа.
- 20 секунд стояния лифта на этаже.
- 100 человек на этаж.
# Настраиваем здание, заполняем этажи людьми def fillBuilding(): building = [] for i in range(floorCount — 1): building.append(peoplePerFloor) return building # Определяем продолжительность цикла (cirTime), # а также усреднённое количество людей, перевозимых за цикл. # Здесь e — массив лифтов, он содержит номера верхних # обслуживаемых этажей. А i — текущий индекс e. def eleLoop(e, i): floorsServiced = e[i] — e[i-1] + 1 cirTime = timePerFloor * e[i] * 2 cirTime += timePerWait * floorsServiced avgCarry = cirTime * peoplePerFloor / rushHour * floorsServiced return cirTime, avgCarry # (Индекс * 5 секунд) + (20 секунд * (Индекс – Предыдущий индекс)) # Если сумма предыдущих циклов/остановок больше, чем # (время прохождения этажа * 2) + время ожидания, тогда увеличиваем этажность # предыдущего цикла, то есть лифт[2]+=1 # e обозначает массив лифтов (зоны ответственности) def addFloor(e): best = 9999 for i in range(1, len(e)): cirTime, avgCarry = eleLoop(e, i) if cirTime + ((cirTime / 100) * avgCarry) < best: elevatorNumber = i best = cirTime + ((cirTime / 100) * avgCarry) for i in range(elevatorNumber, len(e)): e[i] += 1 return e # Выводит в виде массива количество людей на этаже. def printApprox(building): str = ‘[ ‘ for i in range(len(building)): str += ‘%06.3f ‘ % building[i] str += ‘]’ print str # Выводит цикл(-ы) для каждого лифта def printeleLoop(e): print » print e print » for i in range(1, len(e)): floorsServiced = e[i] — e[i-1] + 1 curr = timePerFloor * e[i] * 2 curr += timePerWait * floorsServiced avgCarry = curr * peoplePerFloor / rushHour * floorsServiced str = ‘Лифт #%d, продолжительность цикла %d секунд, ‘ % (i, curr) str += ‘в среднем перевозится ‘ str += ‘%3.2f людей’ % avgCarry print str print » # Распределение лифтов. # Elevator[] обозначает начальную группу остановок. def elevatorAllocation(building, elevatorCount): elevator = [] for i in range(elevatorCount + 1): elevator.append(0) for i in range(1, floorCount): elevator = addFloor(elevator) printeleLoop(elevator) return elevator # Эмулирует час пик, когда все покидают здание def simulate(e, building): str = ‘[ ‘ for floor in range(len(building)): str += ‘floor%2d ‘ % (floor + 1) str += ‘]’ print str eCircuit = [] for i in range(len(e)): curr, avgCarry = eleLoop(e, i) eCircuit.append(float(curr)) emptyFloors = 0 iteration = 0 finalFloor = 0 while emptyFloors < len(building): emptyFloors = 0 iteration += 1 for i in range(1, len(e)): for j in range(e[i-1], e[i]): if building[j] >0.0: persons = eCircuit[i] * peoplePerFloor / rushHour building[j] = building[j] — persons if 0 >= building[j]: building[j] = 0.0 emptyFloors += 1 finalFloor = j printApprox(building) print » # Находит последний лифт в цикле, выводит время for i in range(len(e)): if e[i] > finalFloor: iteration = eCircuit[i] * iteration / 60 print ‘Общее время: %d минутn’ % (итерация) # ___ MAIN ____ building = fillBuilding() elevator = elevatorAllocation(building, elevatorCount) simulate(elevator, building)
Выходные данные:
Лифт № 1, продолжительность цикла — 140 секунд, в среднем перевозится 19,44 человека
Лифт № 2, продолжительность цикла — 150 секунд, в среднем перевозится 16,67 человека
Лифт № 3, продолжительность цикла — 150 секунд, в среднем перевозится 12,5 человека
Общее время: 65 минут
Среднее количество людей на этаже по мере прохода лифтов:
Как видите, алгоритм работает неплохо, но не идеально (для наших условий). Вы можете улучшить его самостоятельно.
Время прогона
Время прогона алгоритма зависит от трёх факторов:
- k: самый длинный цикл, количество людей
- n: начальное количество людей на обслуживаемом этаже самого длинного цикла
- m: общее количество этажей
Время прогона: O(m * (n/k))
n/k определяет максимальное количество итераций, совершаемых лифтам в пределах цикла(-ов). m используется потому, что нам нужно пройти по каждому этажу в ходе итерации. В этом случае мы пренебрегаем «настройкой», представляющей собой заполнение «массива здания», описывающего количество людей на каждом этаже, потому что это не является основным условием для прогона (m*(n/k) + m).
Объём памяти для прогона алгоритма зависит:
- e: от количества лифтов
- f: от количества этажей
Объём памяти: O(e + f)
Заключительное слово
Конечно, алгоритм получился не идеальный, но вполне рабочий. Предложите свои улучшения. Движение лифтов — это интересная прикладная задача, которая аналогична распределению ресурсов компьютера.
- Блог компании VK
- Python
- Программирование
- Алгоритмы
Источник: habr.com
Как работает лифт в небоскребах? Алгоритмы + задачи с собеседований
В небоскрёбах и других высотных зданиях лифт — это единственный способ добраться на нужный этаж за приемлемое время. Алгоритм, по которому работает лифт, должен учитывать множество факторов: скорость передвижения, безопасность, удобство пассажиров, время ожидания и другие. Современные умные лифты используют для этого компьютерное моделирование и машинное обучение, — пишет tproger.ru.
История
Первые лифты приводились в движение паровой машиной, их работой управлял оператор. В 1924 году компания Otis представила первый автоматический лифт, управляемый логическими реле. Это позволило увеличить скорость передвижения кабины. Через 13 лет, Otis показала систему помогающую планировать работу лифта в периоды высокой нагрузки. Так выглядели первые автоматические лифты:
Алгоритмы работы лифтов
Простой алгоритм
Большинство обычных лифтов работают по простому алгоритму:
- пока внутри лифта или на этажах (по ходу движения) есть пассажиры, которым нужно ехать в ту же сторону, лифт движется в эту сторону;
- если вызовов по ходу движения больше нет, но есть в обратную сторону, то лифт меняет направление.
В этом случае лифту важно знать только желаемое направление, поэтому для вызова обычно используют две кнопки со стрелками. Подобный алгоритм использовался в жёстких дисках.
Такое поведение оптимально при небольшом количестве этажей и наличии только одного лифта. При увеличении количества этажей время ожидания возрастает. В случае если лифтов больше одного, при такой стратегии все лифты будут приезжать на один этаж. Чтобы справиться с этим инженеры начали синхронизировать лифты между собой. Так, если вызвать лифт, то приедет тот, который ближе всего в данном направлении.
Группировка по месту назначения
Этот алгоритм принципиально отличается от простого: на каждом этаже, вместо кнопки вызова лифта, находятся кнопки для указания, на какой этаж нужно пассажиру. Благодаря этой информации, лифт может собрать в одной кабине всех, кому нужно на конкретный этаж. Это позволяет не тратить время на лишние остановки. Однако время ожидания в среднем немного увеличится.
Для большинства людей ожидание кажется настолько невыносимым, что некоторые лифты настраивают так чтобы минимизировать время ожидания, даже если это увеличит время поездки.
В зависимости от времени, суток лифт может работать в разных режимах. Например утром лифты будут стоять с открытыми дверьми на первом этаже, готовые к часу пик. Это называется стратегией парковки, когда лифты возвращаются на этажи, где пользуются наибольшим спросом. Кроме того, лифт можно привязать к определённой группе этажей. Чтобы использовать оптимальную в данный момент стратегию компьютер, управляющий лифтами, анализирует ситуацию с помощью машинного обучения.
Задачи с собеседований
Алгоритм работы лифта — нетривиальная задача, вопросы о нём задают даже на собеседовании в Google. Вот пример задания:
Как должен работать лифт в 40-этажном офисном здании, на каждом из этажей которого работает около 100 человек, чтобы обеспечить наиболее эффективное заполнение и опустошение здания во время стандартного 9 часового рабочего дня, с двумя выходными, учитывая возможные пробки?
Дайте максимально подробный ответ, включая: предполагаемое количество пассажиров в кабине лифта, время на остановку, среднее количество остановок за поездку в разные часы и т. д.
Такую задачу предлагает компания Synergy Team:
Требуется разработать программу — эмулятор лифта. При старте программа должна запрашивать этажность дома. Программа должна выводить пользователю текущее состояние лифта (номер этажа, направление движения (вверх, вниз, остановка). Скорость движения лифта: 1 этаж в секунду.
Пользователь должен иметь возможность в любой момент, включая периоды движения лифта, «нажать» кнопку вызова на любом этаже. Во время движения может быть нажато произвольное количество кнопок «вызов» на разных этажах.
Пользователь должен иметь возможность «нажать» кнопку любого этажа на вызывной панели внутри кабины лифта.
При написании программы надо руководствоваться собственными здравым смыслом и знаниями о работе лифтов. Остальные ограничения по работе программы должны устанавливаться программистом по его собственному усмотрению. Дополнительные уточнения по заданию не выдаются.
В интернете даже есть игра, в которой вам нужно запрограммировать лифт, чтобы развезти людей за определённое время.
Источник: techrocks.ru
Как работает лифт в небоскребах? Алгоритмы + задачи с собеседований
В небоскрёбах и других высотных зданиях лифт — это единственный способ добраться на нужный этаж за приемлемое время. Алгоритм по которому работает лифт должен учитывать множество факторов: скорость передвижения, безопасность, удобство пассажиров, время ожидания и другие. Современные умные лифты используют для этого компьютерное моделирование и машинное обучение.
История
Первые лифты приводились в движение паровой машиной, их работой управлял оператор. В 1924 году компания Otis представила первый автоматический лифт, управляемый логическими реле. Это позволило увеличить скорость передвижения кабины. Через 13 лет, Otis показала систему помогающую планировать работу лифта в периоды высокой нагрузки. Так выглядели первые автоматические лифты:
В 1948 году Otis начал производить автоматические лифты, которые уже умели изменять скорость, адаптировать своё расписание к периодам нагрузки, не останавливаться при полной загрузке кабины. В них появилась функция автоматического закрытия двери после определенного времени простоя.
Управление с помощью реле использовалось до 1980 годов, когда их начали вытеснять микропроцессоры. Микропроцессоры потребляли меньше энергии и занимали гораздо меньше места.
Так выглядела управляющая система реле лифта Otis. Картинка с сайта
Алгоритмы работы лифтов
Простой алгоритм
Большинство обычных лифтов работают по простому алгоритму:
- пока внутри лифта или на этажах (по ходу движения) есть пассажиры, которым нужно ехать в ту же сторону, лифт движется в эту сторону;
- если вызовов по ходу движения больше нет, но есть в обратную сторону, то лифт меняет направление.
В этом случае лифту важно знать только желаемое направление, поэтому для вызова обычно используют две кнопки со стрелками. Подобный алгоритм использовался в жёстких дисках.
Такое поведение оптимально при небольшом количестве этажей и наличии только одного лифта. При увеличении количества этажей время ожидания возрастает. В случае если лифтов больше одного, при такой стратегии все лифты будут приезжать на один этаж. Чтобы справиться с этим инженеры начали синхронизировать лифты между собой. Так, если вызвать лифт, то приедет тот, который ближе всего в данном направлении.
Группировка по месту назначения
Этот алгоритм принципиально отличается от простого: на каждом этаже, вместо кнопки вызова лифта, находятся кнопки для указания, на какой этаж нужно пассажиру. Благодаря этой информации, лифт может собрать в одной кабине всех, кому нужно на конкретный этаж. Это позволяет не тратить время на лишние остановки. Однако время ожидания в среднем немного увеличится.
Для большинства людей ожидание кажется настолько невыносимым, что некоторые лифты настраивают так чтобы минимизировать время ожидания, даже если это увеличит время поездки.
В зависимости от времени суток, лифт может работать в разных режимах. Например утром лифты будут стоять с открытыми дверьми на первом этаже, готовые к часу пик. Это называется стратегией парковки, когда лифты возвращаются на этажи, где пользуются наибольшим спросом. Кроме того, лифт можно привязать к определённой группе этажей. Чтобы использовать оптимальную в данный момент стратегию компьютер, управляющий лифтами, анализирует ситуацию с помощью машинного обучения.
Задачи с собеседований
Алгоритм работы лифта — нетривиальная задача, вопросы о нём задают даже на собеседовании в Google. Вот пример задания:
Как должен работать лифт в 40-этажном офисном здании, на каждом из этажей которого работает около 100 человек, чтобы обеспечить наиболее эффективное заполнение и опустошение здания во время стандартного 9 часового рабочего дня, с двумя выходными, учитывая возможные пробки?
Дайте максимально подробный ответ, включая: предполагаемое количество пассажиров в кабине лифта, время на остановку, среднее количество остановок за поездку в разные часы и т. д.
Источник: tproger.ru