algorithm - 优化 parking 场问题。我应该使用什么算法来匹配 parking 场中最多的汽车？

Question

我将使用什么算法(是否使用蛮力)将尽可能多的汽车(假设所有汽车大小相同)放入 parking 场，以便至少有一个导出(来自容器)并且汽车不能被封锁。或者有人可以向我展示一个以编程方式解决此问题的示例。

parking 场的形状变化会很好，但如果您想假设它是某种不变的形状，那很好。

另一个编辑:假设 parking 场的行驶距离不是一个因素(尽管如果它是 parking 场中汽车数量的加权因素，那就太棒了)。

另一个编辑:假设 2 维(没有起重机或驾驶汽车)。

另一个编辑:汽车一旦停好就不能四处移动(这不是代客泊车场)。

Answer 1

好吧，让我们稍微简化/具体化一下。假设我们的车是单位正方形， parking 场是N×N，需要从左下角进/出。一个简单的模式让 parking 场几乎占满了汽车的 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 的地 block 装满。想象一下，您通过从一个完全满的车库开始并一次开出一辆(当前可到达的)汽车来建立空地。每次你移除一辆车，你会产生最多 3 辆新可达的汽车，并移除一辆曾经可达的汽车(现在是一个空的空间)。因此，对于您创建的每个空间，您最多可以创建 2 辆可到达的汽车。要制作 2/3 N^2 辆可到达的汽车，您至少需要制作 1/3 N^2 的空间，这就是您拥有的所有正方形。因此，您最多可以将车库装满 2/3。

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