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

27

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

Поэтому в данный момент я использую очень простую и «близорукую» логику, которая заключается в том, что для текущего этажа найдите этаж, ближайший ко мне, и установите его в качестве моего следующего пункта назначения, и выполните цикл, пока в списке не останется больше этажей.

Но это не всегда работает, например, лифт был на 3-м этаже 5-ти этажного здания и получил заказы 4,5,2, самый короткий путь был бы 2-> 4-> 5, который стоит 4 этажа, но используя эту логику 4-> 5-> 2, который стоит 5, имеет одинаковую вероятность быть выбранным, в зависимости от кода.

Как мне найти кратчайший путь и сделать лифт более эффективным?

Раед Табани
источник
2
Несколько связано: programmers.stackexchange.com/q/96278/149904
Мэнлио
6
Я хотел бы пригласить вас в мой офис и выяснить алгоритм, который там используют лифты. Потому что я абсолютно не могу.
gnasher729
1
@ gnasher729 О, я могу, хотя и не знаю вас, потому что это точно так же, как в моем офисе: никогда не останавливайтесь на полу, на котором я нахожусь, за исключением случаев, когда уже полно людей. Я прав?
Андрес Ф.
2
Не совсем. Есть четыре лифта. Нажимаешь кнопку, ничего не движется очень долго. Если кто-то двигается, он останавливается прямо перед вашим полом и ждет целую вечность, пока его не настигнет другой, который пройдет мимо вашего пола, а затем спустится. На пути к земле он останавливается как минимум три раза, и никто не входит.
gnasher729
2
Соответствующая игра в программирование / вызов: play.elevatorsaga.com
dwikle

Ответы:

30

«Эффективность» - не самая важная особенность, главное, чтобы каждый заказ выполнялся, чтобы не было голода. Если кто-то нажимает 100, а люди продолжают нажимать 1 и 2, может быть целесообразно продолжать проходить между этими этажами, но было бы хорошо, чтобы 100 посещали в какой-то момент.

Я думаю (из личного наблюдения, когда мне было интересно выяснить), что большинство из них делают:

  1. Начните движение в направлении первой нажатой кнопки, следите за тем, в каком направлении мы движемся
  2. Когда этаж достигнут и эта кнопка была нажата, остановитесь и откройте двери, отметьте кнопки для этого этажа как больше не нажимаемые.
    • Если нам нужно посетить еще несколько этажей в одном направлении, продолжайте движение в этом направлении .
    • Если нет и есть еще этажи, которые нам нужно посетить, двигайтесь в этом направлении.
    • Если нет, то мы закончили и начнем с 1, когда кнопка будет нажата снова.

Обратите внимание, что у многих лифтов рядом с дверями есть кнопки «Я хочу подняться» и «Я хочу спуститься» вместо одной кнопки. Алгоритм нуждается только в небольшом изменении: в 2, если единственной кнопкой, нажатой для этого этажа, является одна из кнопок рядом с дверью, останавливайте и открывайте двери, только если мы движемся в этом направлении. Возможно, удерживайте кнопку нажатой, если двери открыты из-за нажатия кнопки внутри лифта, и она движется в неправильном направлении.

Вам никогда не придется выяснять весь путь , просто в каком направлении идти дальше.

RemcoGerlich
источник
это полностью пропустило мой разум, я был так сосредоточен на эффективности и забыл, что другие вещи тоже важны. все еще неэффективно переходить от 2-> 100 и обратно к 1 просто потому, что оно было в том же направлении, но, по крайней мере, оно не обеспечивает голодание. и, совершенно не по теме, возможно, поэтому часто встречаются два лифта с такой логикой? это заставляет меня задаться вопросом, является ли более распространенным явление, когда лифты движутся в противоположном направлении в любой момент времени. В любом случае, мне все еще интересно, как найти кратчайший путь целиком, но это очень аккуратно отвечает на мой вопрос, спасибо
Raed Tabani
7
Обратите внимание, что как только вы доберетесь до здания с 100 этажами, у вас, как правило, будут лифты, обслуживающие только определенный диапазон этажей (например, 0-19, 20-39, ...), а также экспресс-лифты, которые проходят только большие расстояния (например, 0 до 50, от 0 до 100, от 50 до 100, но без этажей между ними), поэтому вам, возможно, придется поменять лифты, чтобы добраться до пункта назначения. Вы можете также иметь несколько лифтов на шахту, которые, очевидно, не могут проходить друг за другом. Абсолютно не по теме: во IIRC возник вопрос об эффективности этих кнопок со стрелками вверх и вниз на сайте пользовательского опыта, которые делали чтение очень увлекательным.
Йорг Миттаг,
спасибо, я этого не знал Подразделение представляется хорошей стратегией, если одна часть ломается, а вся система не разбивается, а также для распределения нагрузки, которая важна для механического износа. Интересно, появились ли эти экспресс-лифты из-за логических недостатков алгоритма лифта Кнута?
Раед Табани
Единственное, что я хотел бы добавить, это то, что часто у них есть «домашний» этаж, к которому они будут возвращаться, когда они не используются, это может быть различным для разных лифтов и, возможно, даже меняться в зависимости от времени суток и ожидаемых моделей использования
jk ,
Я имею тенденцию нажимать кнопку вверх / вниз наполовину случайным образом, независимо от того, в каком направлении я на самом деле путешествую. В моем случае, у меня когда-либо есть только один пункт назначения, поэтому лифт доставит меня в это место независимо от того, выбрал я или вниз. Я подозреваю, что если бы я нажал кнопку «вниз», выбрал этаж над собой, а затем выбрал этаж подо мной, прежде чем лифт начнет двигаться, это привело бы меня к полу подо мной, а не к полу, который я толкнул первым. Я могу ошибаться, я обязательно проверю это в следующий раз, когда окажусь в лифте.
Уценна
13

Другой ответ правильно дает стандартный алгоритм лифта, который в основном «продолжает двигаться в одном и том же направлении как можно дольше и делает все необходимые остановки на этом пути».

Есть и другие алгоритмы лифта. Например, рассмотрим жилой дом, где квартиры становятся дороже, когда вы поднимаетесь. Владельцы здания могут изменить алгоритм лифта так, чтобы он «двигался в одном и том же направлении как можно дольше, но останавливался только на пути вниз». Таким образом, если в лифте есть люди, которые находятся в вестибюле и идут к 2, 5 и 10, то лифт идет к 10, затем к 5, затем к 2, отбрасывая людей в порядке платы за аренду. Но, конечно, когда люди из 10 выходят из своей квартиры, им чаще приходится ждать дольше, чтобы попасть в вестибюль.

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

Эрик Липперт
источник
1
Кажется, это редкость (другие алогирты)
FindOutIslamNow
10

Обратите внимание, что лифты используют те же алгоритмы планирования, что и некоторые контроллеры жестких дисков. Стандартный алгоритм SCAN даже известен как алгоритм лифта . Я думаю, что на практике алгоритм LOOK более распространен, так как он немного более эффективен, чем SCAN.

gardenhead
источник
Когда вы так точно говорите, у вас есть профессиональный опыт внедрения кода для лифтов? Особенно новые лифтовые системы? Мне любопытно, если после 11 сентября в Нью-Йорке приоритет отдается отправке пассажиров, а не их воспитанию.
Джон Заброски