Optimization of parking problems. What algorithms should be used for the maximum number of cars in a batch?

Question

What algorithms (brute force or not) I would use to place so many cars (suppose all cars are the same size) in the parking lot, so there is at least one exit (from the container) and the car cannot be blocked. Or can someone show me an example of this problem being solved programmatically.

Parking depending on the form will be pleasant, but if you want to take some kind of invariant form, this is normal.

Other Editing: Suppose parking mileage is not a factor (although it would be perfectly cool if it were a weighted factor in the number of cars in a lot).

Other Editing: Assume 2 sizes (no cranes or car rides).

Other Editing: You cannot move cars when they are parked (this is not parking for cars).

Answer 1

Well, let it simplify / explain a bit. Suppose our cars are unit squares, N x N parking, and we need to enter / exit the lower left corner. A simple template gets almost 2/3 of the full machine (shown for 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| | -----------+ 

I can prove that the best you can do is get a 2/3 batch. Imagine that you are building empty spaces, starting with a completely full garage and driving out of the (if possible achievable) car one at a time. Each time you rent a car, you produce up to 3 new available cars and delete one available car (now an empty space). Therefore, for each place you make, you create no more than two available cars. To make 2/3 N ^ 2 reachable cars, you need to make at least 1/3 N ^ 2 spaces and all the squares that you have. Thus, you can fill the garage by a maximum of 2/3.

The simple pattern above is asymptotically optimal, since its density approaches 2/3 as N → infinity. (I miss you, I was hoping that some kind of tree drawing would be better.)

Answer 2

This is basically equivalent to bin-packing , with the additional requirement that the exit be in a specific location and all machines can exit - which in itself is a difficult problem!

So your problem is at least NP-hard.

Answer 3

Is your definition of efficiency the largest number of parking spaces in a large number of a given size and shape (provided that each car can be driven away without moving any other car)? If so, this is a packaging problem, not a backpack problem, and that sounds NP to me, but the range of solutions for any real world was so small that it could be solved with a practical comprehensive search.

Answer 4

I think it can be technically NP completed. But I think that you could develop an intelligent set of solutions, each of which is based on experience with the latter and algorithmically selects the best solution from the calculated set. You may not be able to prove that this is the best solution. But from a practical point of view, you have an optimized parking lot, so is it really important that, given the infinite amount of time, would you press 3 more cars?