НГУ

Пусть у нас есть парковка на n машин, на которую машины ставятся параллельно друг другу и мордами к оградке. Пусть все машины имеют одинаковую ширину. Вплотную друг к другу ставить их, как известно, нельзя. Для простоты будем считать, что к каждой машине с боков приписано по 40 см "личного пространства", и если ставить их так, чтобы эти зоны не пересекались, то выйдет как раз нормально.

То есть математическая модель такая: есть отрезок длины n, и на нём нужно размещать отрезки длины 1. Основная задача: размещать их так, чтобы влезло как можно больше.

Рассмотрим сначала очень простой случай:
1) будем считать, что все пользователи парковки могут договориться друг с другом о том, как ставить машины
2) парковка расположена так, что сначала водитель проезжает вдоль неё и оценивает расположение машин, а потом уже заезжает внутрь и выбирает себе местечко (около ИМ есть что-то похожее).

Вопрос: о каком алгоритме действий стоит договориться водителям? Если кто этот простой случай решит, проявив интерес, задачу усложним.

Правильный ответ известен: хозяин парковки делает разметку.

Разметка, конечно, решает все проблемы. Если удастся договориться её соблюдать. Но у нас её как минимум 4 месяца под снежком не видно, поэтому в задаче разметки нет. В RL она тоже, мягко говоря, не везде есть.

Надо ещё оговорить ряд условий. Вариант, когда водители будут бегать по парковке с рулеткой, мы не рассматриваем. Можно с приемлемой точностью считать, что опытный водитель, посмотрев на 2 соседние машины, всегда может определить, какой из 4-х вариантов имеет место:
0) они стоят на расстоянии 0, т.е. рядом друг с другом
1) они стоят на расстоянии 1, т.е. между ними как раз влазит ещё одна
2) они стоят не рядом, но на расстоянии меньше 1, т.е. между ними ничего уже не поставишь
3) они стоят на расстоянии больше 1
На этом его измерительные возможности заканчиваются.

А какова измерительная способность водителя во время парковки? То есть, с какой точностью водитель может подогнать машину к другой машине справа, если известно, что пространства хватает?

Будем считать, что выбрать один из этих четырёх вариантов он точно может. Т.е. он может поставить машину вплотную к соседней, на расстоянии 1, меньше или больше 1 (уже без какой-либо точности). То же самое касается края парковки.

Можно попробовать рассмотреть ещё какие-то варианты, если они вдруг понадобятся.

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

Машину ставлю вплотную к какой-нибудь стоящей. Где проблема?

Оk, простая задача решена. Заметим, что несколько сотен миллионов людей решают её каждый день по нескольку раз, и даже такой скромный результат в чём-то любопытен.

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

Напомним, что обычная парковка - очень динамичный объект, какие-то машины оттуда уезжают, какие-то приезжают. То есть в какой-то момент там могут собраться все k отщепенцев, в какой-то 0. Общее число претендентов на места существенно превышает размер парковки n, который тоже достаточно велик.

Да: решение задачи мне не известно. Если найти несколько стратегий, то их можно было бы сравнить.

У парковки есть края.

Хорошие водители должны стараться создавать как можно больше одиночных мест, то есть свободных кусков длины 1, то есть ставить машины относительно другой на расстоянии 1. Причем, предпочтение необходимо отдавать заниманию меньших кусков. То есть, если есть свободный кусок длины 3 и длины 10, то нужно разместить машину в куске длины 3 посередине
P.S. Это не решение, а лишь пара несвязных идей

Да, чтобы нагадить остальным, можно ставить посередине куска длины 3. В соседние метровые куски заехать можно, но вылезти из машины нельзя, т.к. двери не открываются.

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

Да, если немного подумать, то становится ясен парадоксальный факт: машины лучше всего ставить на расстоянии 1. Хоть плакат над парковками вешай.

Мне при этом кажется, что всегда нужно стараться занимать места с краёв парковки. То есть первый сознательный водитель ставит машину на место 2, второй - на место 4, и т.д. В итоге пространство для нарушителей каждый раз будет сокращаться на 2, а наносимый ими потенциальный ущерб - минимизироваться.

Напомним, что мы считаем всех водителей предварительно просмотревшими всю парковку. Тогда алгоритм такой: просматриваем машины, начиная от края парковки. Если все они стоят как надо (мы можем это увидеть), то паркуемся на расстоянии 1 от крайней. Если такой возможности нет, т.е. после ряда сознательных водителей стоит один нарушитель, то смотрим на другой край. Если и там стоит нарушитель, то вопрос, что делать.

Один из вариантов: теперь начинаем ставить машины в те дырки ширины 1 с краёв парковки, который были заготовлены заранее. Это даст возможность не портить ситуацию в центре: как только нарушитель уедет, вновь приезжающие сознательные водители тут же продолжат "зону порядка" на его место.

Чтобы двери не открывались, нужно оставлять с боков примерно по 0.8, такое условие.

Вообще, задача хоть и сложно звучит, весьма близка к практике. Условия взяты по возможности из жизни. Не менее 99% водителей скажут, что вылезать из машины через багажник им очень не хочется, особенно каждый день по нескольку раз. Кабриолеты в нашем климате непопулярны.

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

Если задача близка к практике, то нужно ещё один параметр: модель работы парковки. То есть это может быть, скажем, парковка офисного типа "утром приехал - вечером уехал", либо парковка гипермаркета, когда за сутки состав автомобилей обновляется несколько раз. В первом случае можно придумывать идеальные схемы, во втором - нарушители будут заполнять дырки как попало и любая стройная схема со временем рандомизируется.
Есть ещё один смежный вопрос: можно ли оценить предельную степень заполнения парковки (или потерю емкости) при наличии нарушителей? В самом плохом случае (все становятся ровно через 1.9(9) места) - это 50%. А если нарушителей разумная доля?