优化停车场问题.我应该使用哪些算法来适应该批次中最多的汽车？

Question

我会使用什么算法(强力或非强力)将多少辆汽车(假设所有汽车的尺寸都相同)放入停车场,这样至少有一个出口(从集装箱出来)并且汽车无法阻挡.或者有人能告诉我一个以编程方式解决这个问题的例子.

停车场的形状各不相同,但如果你想假设它是一些不变的形状,那很好.

另一个编辑:假设停车场的行车距离不是一个因素(尽管如果它是加权因素对车辆的数量是非常好的).

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

另一个编辑:一旦停车,你就无法移动汽车(这不是代客停车场).

Answer 1

好吧,让我们简化/具体化一点.假设我们的汽车是单位正方形,停车场是N×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 - >无穷大.(有点无聊,我希望看起来像树状图案会更好.)