Найден оптимальный алгоритм парковки
Одна из самых повседневных задача, наконец, решена
Нам только кажется, что наши повседневные решения просты. Они подчас дьявольски сложные и требуют для решения крутейшей математики.
И мы ошибаемся думая, что большинство повседневных задач уже решены. Дудки! Вот даже для решения, казалось бы, банальной задачи парковки приличное решение придумали только что.
Вы приехали в торговый центр или отель, или еще куда-то с большой публичной парковкой. Свободные места есть. Но как выбрать оптимальное место?
Можно тупо встать на свободном конце парковочного ряда. Но отсюда далеко идти ко входу в здание.
Можно попытаться найти дырку поближе ко входу в ряду уже припаркованных машин. Но надо тратить время на поиск. И потом, — парковаться в 1ю попавшуюся дырку или искать еще ближе ко входу, а там и еще ближе? А когда ближе не окажется, разворачиваться и возвращаться. Но время — деньги.
Получается, что так плохо (пилить с дальнего конца стоянки ко входу), что эдак погано (заморачиваться и тратить время на выбор самой близкой ко входу дырки).
И как же быть?
Дано следующее:
- автомобиль едет справа налево (см. рис);
- ваша цель — вход в здание — расположен на дальнем левом конце от ряда авто.
Чтобы количественно сравнить разные стратегии, нужно ввести «стоимость наших затрат». Естественным определением «стоимости» может быть расстояние от места парковки до входа в здание плюс время, потраченное на поиски места для парковки.
Чтобы минимизировать число параметров предположим, что скорость автомобиля на стоянке такая же, как и скорость ходьбы. Таким образом, подходящей мерой «стоимости» будет расстояние, пройденное автомобилем на стоянке плюс расстояние, которое водитель проходит от места парковки до цели.
В «Кроткой стратегии» каждый новый автомобиль паркуется на крайнем правом месте в максимальном удалении от входа.
В «Оптимистической стратегии» водитель надеется, что есть место для парковки рядом с входом в здание. Таким образом, водитель проходит весь путь до входа, игнорирует все открытые места и, наконец, паркуется на первом свободном месте, которое встретится при отступлении назад.
В «Разумной стратегии» водитель, в отличие от «оптимиста» не уверен, но надеется, что свободные места внутри ряда имеются. Обнаружив 1ю дырку он паркуется на 1ое же свободное место слева от дырки. Если же слева от неё свободных мест нет, то «разумный водитель» превращается в «оптимиста» — проходит весь путь до входа, и развернувшись, паркуется на первом свободном месте, которое встретится при отступлении назад.
- Как следует из названия, «Разумная стратегия» оказалась лучшей, — она стоит водителям наименьших затрат времени.
- На 2ом месте «Оптимистическая стратегия».
- «Кроткая стратегия» предельно неэффективна (если ею воспользуются все, а не только вы).
Чтобы доказать это математически, пришлось написать дифуравнение и еще 3 страницы не самых простых формул.
А это пояснение вышесказанного на видео.
Какая из всего этого мораль.
1) «Разумную стратегию» каждый из нас каким-то образом знает без какой-либо оптимизационной математики. Но откуда это знание, и как (кто) его в нас вложил — неизвестно. Эволюция, однако?
2) Проверенная в исследовании стратегия оптимальна лишь в упрощенном идеальном примере (один бесконечный ряд авто, нет конкуренции за место и пр.) Для реальной стратегии (не идеальной) математическое решение пока неизвестно. Разработавший ее, наверное, будет претендовать на «нобеля в математике».
3) Есть большое подозрение, что и эта — не сформулированная пока наукой оптимальная реальная стратегия — нам все же каким-то образом известна (зашита в нас). Ведь решаем же мы эту задачу. И нельзя сказать, что не оптимально.
________________________________
Если понравился пост:
- нажмите на “палец вверх”;
- подпишитесь на обновления канала на платформе Medium;
- оставьте комментарий.
Еще больше материалов на моем Телеграм канале «Малоизвестное интересное». Подпишитесь
