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

Question

Какие алгоритмы (грубая сила или нет) я бы использовал, чтобы поместить как можно больше машин (предположим, что все автомобили одинакового размера) на парковке, чтобы был хотя бы один выход (из контейнера), и машина не может быть заблокирован. Или может кто-нибудь показать мне пример этой проблемы, решаемой программным путем.

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

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

Другое Править: Предположим, 2-мерный (без кранов или вождения по автомобилям).

Другое Править: Вы не можете перемещать автомобили, когда они припаркованы (это не парковка для автомобилей служащим гостиницы).

Answer 1

Хорошо, давайте немного упростим / конкретизируем. Предположим, что наши машины представляют собой единичные квадраты, автостоянка N x N, и нам нужно войти / выйти из нижнего левого угла. По простому шаблону партия почти на 2/3 заполнена автомобилями (показано для N = 12):

+------------+
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
             |
  -----------+

Я могу доказать, что лучшее, что вы можете сделать, - это заполнить лот 2/3. Представьте себе, что вы создаете пустые пространства, начиная с полностью заполненного гаража и вывозя (в настоящее время доступный) автомобиль по одному. Каждый раз, когда вы удаляете автомобиль, вы производите до 3 новых автомобилей, которые можно было бы достать, и удаляете один автомобиль, который был когда-то доступен (теперь пустое место). Таким образом, для каждого пространства вы создаете не более 2 доступных автомобилей. Чтобы сделать 2/3 N ^ 2 достижимых автомобилей, вам нужно сделать не менее 1/3 N ^ 2 пробелов, и это все, что у вас есть. Таким образом, вы можете заполнить гараж максимум на 2/3.

Простой шаблон выше асимптотически оптимален, так как его плотность приближается к 2/3 при N -> бесконечности. (В некотором роде скучно, я надеялся, что какой-нибудь узор в виде дерева будет лучше.)

Answer 2

Это в основном эквивалентно мусорное ведро , с дополнительным требованием, чтобы выход находился в определенном месте, и все машины могли выехать - что само по себе является сложной проблемой!

Так что ваша проблема, по крайней мере, NP-сложная.

Answer 3

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

Answer 4

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