Optimizing a Parking Lot Problem. What algorithms should I use to fit the most amount of cars in the lot?

Question

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

The parking lot varies in shape would be nice but if you want to assume it's some invariant shape that is fine.

Another Edit: Assume that driving distance in the parking lot is not a factor (although it would be totally awesome if it was weighted factor to number of cars in lot).

Another Edit: Assume 2 Dimensional (no cranes or driving over cars).

Another Edit: You cannot move cars around once they are parked (it's not a valet parking lot).

Answer 1

Well, let's simplify/concreteify a bit. Assume that our cars are unit squares, the parking lot is N x N, and we need to enter/exit from the lower left corner. A simple pattern gets the lot almost 2/3 full with cars (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 possibly do is to get the lot 2/3 full. Imagine that you build up the empty spaces by starting with a completely full garage and driving out a (currently reachable) car one at a time. Each time you remove a car, you produce up to 3 newly reachable cars, and remove one once-reachable car (now an empty space). So for every space you make, you create at most 2 more reachable cars. To make 2/3 N^2 reachable cars, you need to make at least 1/3 N^2 spaces, and that's all the squares you have. So you can fill the garage at most 2/3 full.

The simple pattern above is asymptotically optimal, as its density approaches 2/3 as N -> infinity. (Kinda boring, I was hoping some tree-looking pattern would do better.)