​​Найден оптимальный алгоритм парковки.
Одна из самых повседневных задача, наконец, решена.
Нам только кажется, что наши повседневные решения просты. Они подчас дьявольски сложные и требуют для решения крутейшей математики.
И мы ошибаемся думая, что большинство повседневных задач уже решены. Дудки! Вот даже для решения, казалось бы, банальной задачи парковки приличное решение придумали только что.

Вы приехали в торговый центр или отель, или еще куда-то с большой публичной парковкой. Свободные места есть. Но как выбрать оптимальное место?
Можно тупо встать на свободном конце парковочного ряда. Но отсбда далеко идти ко входу в здание.
Можно попытаться найти дырку поближе ко входу в ряду уже припаркованных машин. Но надо тратить время на поиск. И потом, - парковаться в 1ю попавшуюся дырку или искать еще ближе ко входу, а там и еще ближе? А когда ближе не окажется, разворачиваться и возвращаться. Но время – деньги.
Получается, что так плохо (пилить с дальнего конца стоянки ко входу), что эдак погано (заморачиваться и тратить время на выбор самой близкой ко входу дырки).
И как же быть?

Дано следующее:
- автомобиль едет справа налево (см. рис);
- ваша цель - вход в здание - расположен на дальнем левом конце от ряда авто.
Чтобы количественно сравнить разные стратегии, нужно ввести «стоимость наших затрат». Естественным определением «стоимости» может быть расстояние от места парковки до входа в здание плюс время, потраченное на поиски места для парковки.
Чтобы минимизировать число параметров предположим, что скорость автомобиля на стоянке такая же, как и скорость ходьбы. Таким образом, подходящей мерой «стоимости» будет расстояние, пройденное автомобилем на стоянке плюс расстояние, которое водитель проходит от места парковки до цели.

Проанализировали 3 стратегии.
В «Кроткой стратегии» каждый новый автомобиль паркуется на крайнем правом месте в максимальном удалении от входа.
В «Оптимистической стратегии» водитель надеется, что есть место для парковки рядом с входом в здание. Таким образом, водитель проходит весь путь до входа, игнорирует все открытые места и, наконец, паркуется на первом свободном месте, которое встретится при отступлении назад.
В «Разумной стратегии» водитель, в отличие от «оптимиста» не уверен, но надеется, что свободные места внутри ряда имеются. Обнаружив 1ю дырку он паркуется на 1ое же свободное место слева от дырки. Если же слева от неё свободных мест нет, то «разумный водитель» превращается в «оптимиста» - проходит весь путь до входа, и развернувшись, паркуется на первом свободном месте, которое встретится при отступлении назад.

Как следует из названия, «Разумная стратегия» оказалась лучшей, - она стоит водителям наименьших затрат времени.
На 2ом месте «Оптимистическая стратегия».
«Кроткая стратегия» предельно неэффективна.

Чтобы доказать это математически, пришлось написать дифуравнение и еще 3 страницы не самых простых формул.

Какая из всего этого мораль.
1) «Разумную стратегию» каждый из нас каким-то образом знает без какой-либо оптимизационной математики. Но откуда это знание, и как (кто) его в нас вложил – неизвестно. Эволюция, однако?
2) Проверенныая в исследовании стратегия оптимальна лишь в упрощенном идеальном примере (один бесконечный ряд авто, нет конкуренции за место и пр.) Для реальной стратегии (не идеальной) математическое решение пока неизвестно. Разработавший ее, наверное, будет претендовать на «нобеля в математике».
3) Есть большое подозрение, что и эта – не сформулированная пока наукой оптимальная реальная стратегия - нам все же каким-то образом известна (зашита в нас). Ведь решаем же мы эту задачу. И нельзя сказать, что не оптимально.
https://iopscience.iop.org/article/10.1088/1742-5468/ab3a2a
#СтатистическаяМеханника

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

Полтора года назад я писал, что одна из самых повседневных задач (парковка), наконец, решена, - найден оптимальный алгоритм парковки. С такой задачей мы сталкиваемся каждый день: нужно парковаться на большой парковке, и свободные места есть. Но как выбрать оптимальное по затратам времени на парковку и выезд?

Т.н. «Разумная стратегия», найденная полтора года назад Крапивским и Реднером и описанная ими в “Журнале статистической механики”, была признана авторами и рецензентами оптимальной. Можете прочесть мой тогдашний пост и даже посмотреть видео.

Однако авторы не унялись в своем стремлении к математическому перфекционизму. Потратив еще год, они таки нашли еще более оптимальный алгоритм (назвав его «Правило 1/2»), имеющий к тому же 2 дополнительных преимущества:
1. Алгоритм прост, как редис.
2. И он не улучшаем (математически доказана его оптимальность).

Оптимальная стратегия такова - игнорировать все открытые места, пройдя до середины ряда, после чего занять первое свободное место.

Ложка дёгтя в эту бочку мёда, к сожалению, присутствует. «Правило 1/2», как и «Разумная стратегия», работают лишь в упрощенном идеальном примере (один бесконечный ряд авто и нет конкуренции за место) Для реальной стратегии (не идеальной) математическое решение пока неизвестно. Разработавший ее имеет все шансы на «нобеля в математике».

Так что рекомендую читателям подумать над реальной стратегией. Задачка страшно перспективная. И решив её, гарантированно войдете в историю математики.

#СтатистическаяМеханника

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

Представить, насколько сложна супер-высшая математика «лифтовой жизни», нам довольно трудно. Но если пролистать многие страницы многоэтажных формул интегралов в новой работе профессора неравновесной статистической физики Сидни Реднера «Когда приедет лифт?», сложность этого нагромождения формул здорово прочищает мозги.
Оказывается, что мы просто не представляем уровень сложности математики повседневной жизни.
Полет на Марс или расчет кинетики ядерного реактора – для нас это да! Мы понимаем, насколько это сложно. Но оказывается, что «лифтовая жизнь» (сколько лифтов, какого размера и с какими алгоритмами работы нужно, например, для 100-этажного офисного здания определенной планировки для обеспечения максимального времени ожидания < Х) еще сложнее.

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

Новая работа – первая попытка понять, почему это происходит, и как этого можно избежать (например, проектируя сужающиеся кверху здания).
Исследование показало сложную нелинейную динамику работы системы лифтов, когда при увеличении пассажиропотока лифты начинают синхронизироваться, создавая пробки. Устранить такое возможно лишь когда несколько лифтов одновременно вернутся на первый этаж. И это всего лишь одна из проблем, число которых лавинообразно растет с усложнением схемы поэтажного распределения числа работающих в здании и его посетителей.
Решений тут много: хитрые соотношения числа лифтов и офисных площадей; группы лифтов, обслуживающие группы этажей и т.д.
Короче, фронт работ – огромный. А с учетом темпов урбанизации мира, задачка оказывается поактуальней расчетов межпланетных перелетов.

Подробней:
• 3х минутное видео с объяснением задачи
• Популярный рассказ в EurekAlert!
• Научная статья с тонной формул: за пейволом и без него

И в заключение снова о главном:
✔️ супер-высшая математика повседневной жизни крайне сложна;
✔️ а наши повседневные представления о сложности устройства мира – далеки от реальности.

P.S. Еще одна прорывная работа проф. Реднера – «Улучшен и доказан оптимальный алгоритм парковки. Он минимизирует общие затраты времени при парковке и выезде». Усовершенствование этого алгоритма может претендовать на «нобеля в математике»
#СтатистическаяМеханника