6

我会使用什么算法（暴力与否）在停车场中放置尽可能多的汽车（假设所有汽车的大小相同），以便至少有一个出口（来自集装箱）并且不能阻止汽车。或者有人可以向我展示以编程方式解决此问题的示例。

停车场的形状不同会很好，但如果你想假设它是一些不变的形状，那很好。

另一个编辑：假设停车场的行驶距离不是一个因素（尽管如果它是加权因素到停车场的汽车数量，那将是非常棒的）。

另一个编辑：假设 2 维（没有起重机或在汽车上行驶）。

另一个编辑：一旦停放汽车，您就不能四处移动（这不是代客泊车场）。

4

4 回答 4

5

好吧，让我们简化/具体化一下。假设我们的车是单位正方形，停车场是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。（有点无聊，我希望一些看起来像树的图案会做得更好。）

于 2010-05-15T05:46:10.623 回答
1

这基本上相当于装箱，增加了一个出口在一个特定的地方，所有的汽车都可以出口的要求——这本身就是一个难题！

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

于 2010-05-13T18:17:53.820 回答
0

您对效率的定义是在给定尺寸和形状的许多停车位中的最大数量（假设每辆汽车都可以在不移动任何其他汽车的情况下开走）？如果是这样，这是一个包装问题，而不是一个背包问题，对我来说这听起来 NP，但任何现实世界的解决方案的范围是如此之小，以至于可以通过实际的详尽搜索来解决。

于 2010-05-13T17:46:18.670 回答
0

我认为它在技术上可能是 NP 完整的。但我认为你可以开发一套智能的解决方案，每个解决方案都建立在最后一个经验的基础上，并从计算的集合中通过算法选择最佳解决方案。您可能无法证明这是最好的解决方案。但是从实际的角度来看，你有一个优化的停车场，那么在无限的时间里，你会在里面多挤 3 辆车真的很重要吗？

于 2010-05-13T17:57:15.670 回答