Оптимизация проблемы Парковки. Какие алгоритмы я должен использовать для установки большей части суммы автомобилей в партии?
Что алгоритмы (грубая сила или не) были бы я использовать, чтобы вставить как много автомобилей (предположите, что все автомобили являются тем же размером) на парковке так, чтобы был по крайней мере один выход (от контейнера), и автомобиль не может быть заблокирован. Или может кто-то показывать мне пример этой проблемы, решенной программно.
Парковка варьируется по форме, было бы хорошо, но если Вы хотите предположить, что это - некоторая инвариантная форма, которая прекрасна.
Другое Редактирование: Предположите, что проезжать расстояние на парковке не является фактором (хотя это было бы полностью потрясающим, если бы это было взвешено фактор к количеству автомобилей в партии).
Другое Редактирование: Примите 2 Размерных (никакие подъемные краны или приезжающие автомобили).
Другое Редактирование: Вы не можете переместить автомобили, после того как они паркуются (это не парковка камердинера).
4 ответа
Ну, давайте немного упростим/конкретизируем. Предположим, что наши машины - единичные квадраты, парковка имеет размеры 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 -> бесконечность. (Скучновато, я надеялся, что какой-нибудь похожий на дерево узор будет лучше)
.Вы определяете эффективность как наибольшее количество парковочных мест на участке заданного размера и формы (при условии, что каждую машину можно уехать, не двигая другую машину)? Если так, то это проблема упаковки, а не проблема рюкзака, и это звучит NP для меня, но диапазон решений для любой реальной партии настолько мал, что может быть решен путем практического исчерпывающего поиска.
Я думаю, что технически это может быть NP-полная. Но я думаю, что вы могли бы разработать интеллектуальный набор решений, каждое из которых будет основываться на опыте с последним, и алгоритмически выбрать лучшее решение из рассчитанного набора. Возможно, вы не сможете доказать, что это лучшее из возможных решений. Но с практической точки зрения у вас есть оптимизированная парковка, так что действительно ли имеет значение, что, учитывая бесконечное количество времени, вы втиснули бы туда еще 3 машины?
Это в основном эквивалентно упаковке в контейнеры с добавленным требованием, чтобы выход был в определенном месте, и все машины могли выехать, что само по себе является сложной проблемой!
Итак, ваша проблема как минимум NP-сложная.