Вы стоите на пятнадцатом этаже, нажимаете кнопку вызова и ждете. Лифт проезжает мимо вас вверх, хотя вам нужно вниз. Кажется, что машина сломалась или издевается, но на самом деле в этот момент работает один из самых изящных и эффективных алгоритмов, когда-либо созданных человеком. Парадокс заключается в том, что классический лифт действительно не знает, куда именно вам нужно ехать, пока вы не зайдете внутрь. И именно это неведение делает его работу идеальной.
Давайте представим, что лифт работал бы по принципу строгой очереди: кто первый нажал кнопку, к тому кабина и отправляется. В многоэтажном здании в час пик это привело бы к настоящему транспортному коллапсу. Кабине пришлось бы метаться с первого этажа на тридцатый, затем спускаться на второй, потом снова подниматься на двадцать пятый. Время ожидания растянулось бы на часы, а износ механизмов и расход электроэнергии достигли бы колоссальных значений. Чтобы избежать этого хаоса, инженеры придумали систему коллективного управления, которая в программировании так и называется — «алгоритм лифта».
Суть этого гениального решения предельно проста: кабина движется в одном направлении до тех пор, пока есть вызовы по пути. Если лифт едет вверх, он будет собирать всех пассажиров, которым нужно подняться, игнорируя тех, кто хочет спуститься. Как только самый высокий запрос выполнен, система меняет направление и начинает собирать людей на пути вниз. В момент нажатия кнопки в коридоре система фиксирует только ваше текущее положение и желаемое направление, но не конечную точку маршрута. Лифт не строит сложный индивидуальный план для каждого человека, он просто сканирует здание, подобно дворнику, сметающему снег из одного конца двора в другой.
Этот алгоритм оказался настолько удачным, что вышел далеко за пределы архитектуры. Точно по такому же принципу работают считывающие головки в жестких дисках компьютеров. Чтобы не прыгать хаотично по всему магнитному диску в поисках нужных файлов, головка плавно движется от края к центру и обратно, считывая данные по пути. Это многократно увеличивает срок службы техники и скорость обработки информации.
Конечно, технологии не стоят на месте. В современных бизнес-центрах все чаще можно встретить систему распределения пассажиропотока, когда вы вводите нужный этаж еще в холле, до посадки в кабину. Умный компьютер анализирует все запросы и группирует людей так, чтобы в одном лифте оказались те, кому нужно на соседние этажи. Это позволяет сократить время поездки еще на тридцать процентов.
Однако в большинстве жилых домов по всей стране продолжает трудиться тот самый классический алгоритм. Он не знает ваших конечных целей, не учитывает ваш статус или то, как сильно вы спешите. Он просто делает свою работу максимально эффективно для всех пассажиров сразу, находя идеальный баланс между справедливостью и здравым смыслом.
А как часто вы сталкиваетесь с долгим ожиданием лифта в вашем доме, и раздражает ли вас, когда кабина уезжает в противоположном направлении?