- PVSM.RU - https://www.pvsm.ru -
© Клип "Gangnam Style"
С ростом этажности наших городов всё больше людей ежедневно пользуется лифтами. Но мало кто из нас задумывается о том, как всё это лифтовое поголовье умудряется более-менее эффективно развозить в течение дня уйму людей, особенно в часы пик. Существует ряд алгоритмов движения лифтов, которые исходят из разных условий — например минимизации времени ожидания лифта [1]. Но давайте подумаем, как можно разработать лифтовый алгоритм.
При всей кажущейся простоте задачи довольно сложно создать лифтовый алгоритм для реального применения в зданиях. К тому же такие вещи считаются коммерческими тайнами и патентуются. Поэтому попробуем сделать упрощённую модель:
В здании на каждом этаже живёт одинаковое количество людей. Есть несколько лифтов, лестниц нет. Для простоты будем считать, что на каждом этаже одинаковое количество пассажиров ждёт лифт. Также мы знаем, что в течение дня есть несколько часов пик. Нужно придумать такой алгоритм, чтобы минимизировать время ожидания всех людей в здании.
Здесь можно выделить несколько затрудняющих решение задачи условий:
Также будем учитывать ещё несколько переменных и констант:
Конечно, в реальной жизни скорость прохождения этажа лифтом может быть нелинейной, ведь он разгоняется и тормозит. Но для упрощения расчётов мы это отбросим. Если вам это покажется излишним упрощением задачи, то можете потом самостоятельно ввести эти условия в алгоритм.
Заметим, что пока ничего не сказано о грузоподъёмности лифтов. Здесь мы тоже радикально упростим себе жизнь — будем считать, что лифт вмещает сколько угодно людей. Нереалистично, согласен. Но зато, когда у нас появится первая версия алгоритма, будет проще ввести такие условия:
Как понятно из рисунка, каждому лифту присваивается определённая зона ответственности. Это сделано для того, чтобы усреднить время ожидания на каждом этаже, а также нагрузку на каждый из лифтов. Каждый лифт может проходить цикл «этаж 1 -> 2 -> 3 -> 0». Давайте посчитаем, сколько времени занимает полное прохождение цикла:
5 секунд * <максимальное количество этажей> * 2.
20 секунд * <количество обслуженных этажей>.
Объединим:
время прохождения цикла = (5 * <максимальное количество этажей> * 2) + (20 * <количество обслуженных этажей>)
Теперь посчитаем усреднённое количество людей, которых мы перевезём в течение одного цикла:
усреднённая загрузка лифта = <Время прохождения цикла> * <количество обслуженных этажей> * <количество людей на этаже> / <час пик>
Здесь:
Теперь создадим два массива:
Начнём с того, что первый массив пуст, а затем при каждом добавлении этажа в массив мы станем приписывать к нему лифт. Характер добавления будет меняться, как мы увидим ниже, но в целом он описывается довольно просто. Этажи добавляются в циклы до тех пор, пока грузоподъёмность не станет ограничением. Введём маленькую функцию:
время прохождения цикла + ((время прохождения цикла / 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)
Этого вполне достаточно. Решение относительно прямолинейное, так что здесь многое можно улучшить.
Теперь соберём разные части алгоритма вместе, добавим несколько функций для вывода данных и создадим маленький симулятор [2].
Переменные:
# Настраиваем здание, заполняем этажи людьми
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)
Выходные данные:
[0, 4, 7, 9]
Лифт № 1, продолжительность цикла — 140 секунд, в среднем перевозится 19,44 человека
Лифт № 2, продолжительность цикла — 150 секунд, в среднем перевозится 16,67 человека
Лифт № 3, продолжительность цикла — 150 секунд, в среднем перевозится 12,5 человека
Общее время: 65 минут
Среднее количество людей на этаже по мере прохода лифтов:
Как видите, алгоритм работает неплохо, но не идеально (для наших условий). Вы можете улучшить его самостоятельно.
Время прогона алгоритма зависит от трёх факторов:
Время прогона: O(m * (n/k))
n/k
определяет максимальное количество итераций, совершаемых лифтам в пределах цикла(-ов). m
используется потому, что нам нужно пройти по каждому этажу в ходе итерации. В этом случае мы пренебрегаем «настройкой», представляющей собой заполнение «массива здания», описывающего количество людей на каждом этаже, потому что это не является основным условием для прогона (m*(n/k) + m).
Объём памяти для прогона алгоритма зависит:
Объём памяти: O(e + f)
Конечно, алгоритм получился не идеальный, но вполне рабочий. Предложите свои улучшения. Движение лифтов — это интересная прикладная задача, которая аналогична распределению ресурсов компьютера.
Автор: pushtaev
Источник [3]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/python/276468
Ссылки в тексте:
[1] минимизации времени ожидания лифта: https://www.google.com/patents/US5304752
[2] маленький симулятор: https://github.com/lettergram/ElevatorAllocation
[3] Источник: https://habrahabr.ru/post/352310/?utm_campaign=352310
Нажмите здесь для печати.