Я пытаюсь смоделировать лифт, как всегда, я начал очень просто, принимая только один заказ за раз, затем добавил память к лифту в виде очередей, так что этажи перемещались в том порядке, в котором они были нажаты, что, очевидно, не лучший подход.
Поэтому в данный момент я использую очень простую и «близорукую» логику, которая заключается в том, что для текущего этажа найдите этаж, ближайший ко мне, и установите его в качестве моего следующего пункта назначения, и выполните цикл, пока в списке не останется больше этажей.
Но это не всегда работает, например, лифт был на 3-м этаже 5-ти этажного здания и получил заказы 4,5,2, самый короткий путь был бы 2-> 4-> 5, который стоит 4 этажа, но используя эту логику 4-> 5-> 2, который стоит 5, имеет одинаковую вероятность быть выбранным, в зависимости от кода.
Как мне найти кратчайший путь и сделать лифт более эффективным?
источник
Ответы:
«Эффективность» - не самая важная особенность, главное, чтобы каждый заказ выполнялся, чтобы не было голода. Если кто-то нажимает 100, а люди продолжают нажимать 1 и 2, может быть целесообразно продолжать проходить между этими этажами, но было бы хорошо, чтобы 100 посещали в какой-то момент.
Я думаю (из личного наблюдения, когда мне было интересно выяснить), что большинство из них делают:
Обратите внимание, что у многих лифтов рядом с дверями есть кнопки «Я хочу подняться» и «Я хочу спуститься» вместо одной кнопки. Алгоритм нуждается только в небольшом изменении: в 2, если единственной кнопкой, нажатой для этого этажа, является одна из кнопок рядом с дверью, останавливайте и открывайте двери, только если мы движемся в этом направлении. Возможно, удерживайте кнопку нажатой, если двери открыты из-за нажатия кнопки внутри лифта, и она движется в неправильном направлении.
Вам никогда не придется выяснять весь путь , просто в каком направлении идти дальше.
источник
Другой ответ правильно дает стандартный алгоритм лифта, который в основном «продолжает двигаться в одном и том же направлении как можно дольше и делает все необходимые остановки на этом пути».
Есть и другие алгоритмы лифта. Например, рассмотрим жилой дом, где квартиры становятся дороже, когда вы поднимаетесь. Владельцы здания могут изменить алгоритм лифта так, чтобы он «двигался в одном и том же направлении как можно дольше, но останавливался только на пути вниз». Таким образом, если в лифте есть люди, которые находятся в вестибюле и идут к 2, 5 и 10, то лифт идет к 10, затем к 5, затем к 2, отбрасывая людей в порядке платы за аренду. Но, конечно, когда люди из 10 выходят из своей квартиры, им чаще приходится ждать дольше, чтобы попасть в вестибюль.
Если вы ищете эффективное решение, тогда придумайте метрику стоимости, внедрите множество различных алгоритмов и запустите симуляции. Не забудьте измерить не только среднюю стоимость, но и такие показатели, как самая длинная продолжительность обработки одного запроса. Оптимизация для низких средних значений может иногда деоптимизировать худший случай, что плохо.
источник
Обратите внимание, что лифты используют те же алгоритмы планирования, что и некоторые контроллеры жестких дисков. Стандартный алгоритм SCAN даже известен как алгоритм лифта . Я думаю, что на практике алгоритм LOOK более распространен, так как он немного более эффективен, чем SCAN.
источник