优化停车场问题。我应该使用什么算法来适应停车场中数量最多的汽车？

Question

我会使用什么算法(暴力或非暴力)在停车场投入尽可能多的汽车(假设所有汽车的大小都相同)，以便至少有一个出口(从集装箱)，并且一辆汽车不会被阻挡。或者有人可以给我展示一个以编程方式解决这个问题的例子。

停车场的形状不同会很好，但如果你想假设它是某种不变的形状，那也没问题。

另一个编辑:假设在停车场的驾驶距离不是一个因素(尽管如果它是停车场中汽车数量的加权因素，那将是非常棒的)。

另一个编辑:假设是二维的(没有起重机或在汽车上行驶)。

另一个编辑:一旦停车，你就不能移动汽车(这不是代客停车场)。

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的车库。

上面的简单模式是渐近最优的，因为当N ->无穷大时，它的密度接近2/3。(有点无聊，我希望一些看起来像树的模式会更好。)

Answer 2

这基本上等同于bin-packing，但增加了一个要求，即出口必须位于特定位置，并且所有汽车都可以退出--这本身就是一个很难解决的问题！

所以你的问题至少是NP难的。

Answer 3

你对效率的定义是不是指给定大小和形状的大量停车位的最大数量(假设每辆车都可以在不移动任何其他车的情况下被开走)？如果是这样的话，这是一个装箱问题，而不是背包问题，对我来说，这听起来像NP，但现实世界中任何批次的解决方案范围都很小，可以通过实际的穷尽搜索来解决。