优化停车场问题。我应该使用什么算法来容纳停车场中最多数量的汽车？
我将使用什么算法（或非暴力）将尽可能多的汽车放入停车场（假设所有汽车尺寸相同），以便至少有一个出口（从容器）并且汽车不会被阻塞。或者有人可以向我展示一个以编程方式解决此问题的示例。
停车场的形状各不相同固然很好，但如果你想假设它是某种不变的形状，那就没问题了。
另一个编辑： 假设停车场的行驶距离不是一个因素（尽管如果它是停车场汽车数量的加权因素，那就太棒了）。
另一个编辑： 假设是二维的（没有起重机或在汽车上行驶）。
另一个编辑： 一旦车辆停放，您就无法移动车辆（这不是代客停车场）。
What algorithms (brute force or not) would I use to put in as many cars (assume all cars are the same size) in a parking lot so that there is at least one exit (from the container) and a car cannot be blocked. Or can someone show me an example of this problem solved programmatically.
The parking lot varies in shape would be nice but if you want to assume it's some invariant shape that is fine.
Another Edit:
Assume that driving distance in the parking lot is not a factor (although it would be totally awesome if it was weighted factor to number of cars in lot).
Another Edit:
Assume 2 Dimensional (no cranes or driving over cars).
Another Edit:
You cannot move cars around once they are parked (it's not a valet parking lot).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
好吧，让我们简化/具体化一下。假设我们的车是单位正方形，停车场是N x N，我们需要从左下角进/出。一个简单的模式使停车场几乎 2/3 充满了汽车（显示为 N=12）：
我可以证明，您能做的最好的事情就是让停车场充满 2/3。想象一下，您通过从一个完全满的车库开始并一次开出一辆（当前可到达的）汽车来建立空的空间。每次移除一辆汽车时，您最多会产生 3 辆新可达的汽车，并移除一辆曾经可达的汽车（现在是空的空间）。因此，对于你创造的每一个空间，你最多可以创造 2 辆可到达的汽车。要制作 2/3 N^2 可达汽车，您需要至少制作 1/3 N^2 空间，这就是您拥有的所有正方形。所以你最多可以把车库装满 2/3。
上面的简单模式是渐近最优的，因为当 N → 时，其密度接近 2/3。无穷大。 （有点无聊，我希望一些看起来像树的图案会做得更好。）
Well, let's simplify/concreteify a bit. Assume that our cars are unit squares, the parking lot is N x N, and we need to enter/exit from the lower left corner. A simple pattern gets the lot almost 2/3 full with cars (shown for N=12):
I can prove that the best you can possibly do is to get the lot 2/3 full. Imagine that you build up the empty spaces by starting with a completely full garage and driving out a (currently reachable) car one at a time. Each time you remove a car, you produce up to 3 newly reachable cars, and remove one once-reachable car (now an empty space). So for every space you make, you create at most 2 more reachable cars. To make 2/3 N^2 reachable cars, you need to make at least 1/3 N^2 spaces, and that's all the squares you have. So you can fill the garage at most 2/3 full.
The simple pattern above is asymptotically optimal, as its density approaches 2/3 as N -> infinity. (Kinda boring, I was hoping some tree-looking pattern would do better.)
这基本上等同于 bin-packing，并增加了退出位于特定位置的要求并且所有的汽车都可以退出——这本身就是一个难题！
所以你的问题至少是NP难的。
This is basically equivalent to bin-packing, with the added requirement that an exit be in a particular place and all the cars can exit -- which is itself a hard problem!
So your problem is at least NP-hard.
您对效率的定义是在给定尺寸和形状的情况下的最大停车位数量（假设每辆车都可以在不移动任何其他车辆的情况下开走）？如果是这样，那么这是一个包装问题，而不是背包问题，对我来说这听起来是 NP，但任何现实世界批次的解决方案范围都很小，可以通过实际的详尽搜索来解决。
Is your definition of efficiency the greatest number of parking spots in a lot of a given size and shape (assuming that each car can be driven away without moving any other car)? If so, it is a packing problem, not a knapsack problem, and it sounds NP to me, but the range of solutions for any real-world lot being so small it could be solved with an practical exhaustive search.
我认为技术上可能是NP完全的。但我认为您可以开发一组智能解决方案，每个解决方案都建立在上一个解决方案的经验之上，并通过算法从计算集中选择最佳解决方案。您可能无法证明这是最好的解决方案。但从实际角度来看，你有一个优化的停车场，那么在无限长的时间内你会再挤 3 辆汽车，这真的很重要吗？
I think it may be technically NP complete. But I think that you could develop an intelligent set of solutions, each one building off of the experience with the last, and algorithmically choose a best solution from the calculated set. You may not be able to prove it is the best possible solution. But from a practical standpoint, you have an optimized parking lot, so does it really matter that given an infinite amount of time you would have squeezed 3 more cars in there?