代码之家 › 专栏 › 技术社区 › Adam Gent

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

np-complete machine-learning algorithm

Adam Gent · 技术社区 · 14 年前

我会用什么算法(蛮力或不蛮力)把尽可能多的车(假设所有的车都是相同的大小)放在停车场,这样至少有一个出口(从集装箱)和一辆车不会被阻塞。或者有人能给我一个用程序解决这个问题的例子吗?

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

另一个编辑: 假设停车场的行驶距离不是一个因素(尽管如果把它加权到停车场的车数,那将是非常棒的)。

另一个编辑: 假设为二维(无起重机或在车上行驶)。

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

4 回复 | 直到 6 年前

Keith Randall 14 年前

好吧,让我们简化/具体化一点。假设我们的车是单元广场,停车场是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/3n^2可到达的汽车,你需要制造至少1/3n^2的空间,这就是你所有的正方形。所以你最多可以把车库装满2/3。

当密度接近n->无穷大时,上面的简单模式是渐近最优的。(有点无聊,我希望一些看起来像树的图案会更好。)

Shaggy Frog 14 年前

这基本上等同于 bin-packing 另外还有一个要求,即一个出口在一个特定的地方,所有的汽车都可以出口——这本身就是一个难题!

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

Michael Lorton 14 年前

你对效率的定义是在给定大小和形状的停车场中停车数量最多的地方吗(假设每辆车都可以在不移动任何其他车的情况下被驱走)?如果是这样的话,这是一个包装问题,而不是背包问题,对我来说这听起来是一个NP问题,但是对于任何一个现实世界中的地段来说,解决方案的范围是如此之小,可以通过实际的详尽搜索来解决。

Matthew Vines 14 年前

我认为技术上可能是NP完全的。但是我认为你可以开发出一套智能的解决方案,每一个都建立在最后一个解决方案的经验的基础上,并且从算法上从计算集中选择一个最佳的解决方案。你可能无法证明这是最好的解决方案。但从实际出发,你有一个优化的停车场,所以,如果你有无限的时间,你会在那里多挤3辆车,这真的很重要吗?