Алгоритм Карпа: Лифты и алгоритмы | Игра в науку

Наш пулевый лифт, созданный на прошлой неделе, не должен, ради блага его пассажиров, ускоряться со скоростью 10 м/с² до середины своего пути, и, следовательно, реакция второго посетителя очень разумна, потому что, как отмечает Марина Пуэнте:

«Замедление не может превышать гравитацию (9,8 м/с²), поскольку пассажиры потеряют контакт с полом лифта. Поэтому максимальная скорость должна достигаться до 100-дюймового этажа.

Для Гамовский лифтНа первый взгляд кажется, что, хотя лифтов несколько, вероятность того, что первый лифт, остановившийся на 2-м этаже, опустится, все равно равна 5/6, поскольку это вероятность для каждого отдельного лифта и дает то же самое использование одного, чем другое. Собственно, сам Гамов поначалу растерялся. Но Дональд Э. Кнут Он понял, что, вопреки тому, что подсказывает интуиция, если есть несколько лифтов, все меняется, и он подробно проанализировал ситуацию в своей статье 1979 года «Проблема лифта Гамова-Штерна». Ситуация меняется настолько сильно, что, когда количество лифтов стремится к бесконечности, вероятность стремится к 1/2, как пришли к выводу некоторые читатели (см. комментарии за прошлую неделю).

Что касается проблемы пятиэтажного здания с единственным лифтом, рассчитанным на двух человек, Франциско Монтесинос и Сальва Фустер соглашаются найти минимальный маршрут из 18 единиц, который гласит:

«Я согласен с аргументом, который показывает, что путешествие менее 14 единиц невозможно. Как и Франциско, я также совершил путешествие в 18 единиц и считаю, что 18 — это минимально достижимый уровень. Чтобы это увидеть, думаю, удобно каждое совершаемое движение разделить на направленные единичные сегменты (схему оставляю в прикрепленном изображении). Каждую пару отрезков между двумя соседними этажами можно сделать за одно перемещение на 1 единицу (2 единицы, если считать в обе стороны), но с учетом (не)парности отрезков, на части маршрутов мы сможем только сблизить одного. человек до места назначения (конкретно это произойдет 8 раз)».

Алгоритм Карпа

Престижный ученый-компьютерщик Ричард М. Карп, получивший в 1985 году Премию Тьюринга за вклад в теорию алгоритмов и решение задач комбинаторной оптимизации, разработал простую процедуру для решения обобщения предыдущей проблемы:

1. Если во время подъема лифта кто-то (либо в лифте, либо на этаже, где он только что остановился) хочет подняться, лифт загружается людьми с самым высоким пунктом назначения, а все остальные остаются на этом этаже, и затем лифт поднимается на один этаж. Если никто не хочет подниматься, лифт опускается.
2. Когда лифт опускается, он загружается людьми, находящимися ниже всего (независимо от того, находятся ли они уже в лифте или на этаже, на котором он только что остановился), и лифт опускается на один этаж вниз. Если никто не хочет спускаться, лифт поднимается.

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

Вы можете следить МАТЕРИЯ в Фейсбук, Икс е Инстаграмнажмите здесь, чтобы получить наш еженедельный информационный бюллетень.