60

假设我有一条抛物线。现在我也有一堆相同宽度的棍子（是的，我的绘画技巧很棒！）。我怎样才能将这些棒堆叠在抛物线内，以便尽可能减少它使用的空间？我相信这属于背包问题的范畴，但是这个维基百科页面似乎并没有让我更接近现实世界的解决方案。这是一个NP-Hard问题吗？

在这个问题中，我们试图最小化消耗的面积（例如：积分），其中包括垂直面积。

在此处输入图像描述

4

7 回答 7

23

我使用processing.js和 HTML5 画布 在 JavaScript 中编写了一个解决方案。

如果您想创建自己的解决方案，这个项目应该是一个很好的起点。我添加了两种算法。一种将输入块从最大到最小排序，另一种随机打乱列表。然后尝试将每个项目从底部（最小的桶）开始放入桶中并向上移动，直到它有足够的空间容纳。

根据输入的类型，排序算法可以在 O(n^2) 中给出良好的结果。这是排序输出的示例。

排序插入

这是按顺序插入算法。

function solve(buckets, input) {
  var buckets_length = buckets.length,
      results = [];

  for (var b = 0; b < buckets_length; b++) {
    results[b] = [];
  }

  input.sort(function(a, b) {return b - a});

  input.forEach(function(blockSize) {
    var b = buckets_length - 1;
    while (b > 0) {
      if (blockSize <= buckets[b]) {
        results[b].push(blockSize);
        buckets[b] -= blockSize;
        break;
      }
      b--;
    }
  });

  return results;
}

github 上的项目 - https://github.com/gradbot/Parabolic-Knapsack

这是一个公共回购，所以可以随意分支和添加其他算法。将来我可能会添加更多，因为这是一个有趣的问题。

于 2011-03-22T03:55:14.843 回答
15

简化

首先，我想简化问题，为此：

  • 我切换轴并将它们相互添加，这导致 x2 增长
  • 我假设它是封闭区间上的抛物线[a, b], where a = 0，对于这个例子b = 3

假设给定了b（区间的第二部分）和w（段的宽度），那么您可以通过 找到段的总数n=Floor[b/w]。在这种情况下，存在最大化黎曼和和函数以获得第 i 个段高度的简单情况是：f(b-(b*i)/(n+1)))。实际上这是一个假设，我不是 100% 确定的。

函数实数值 17的闭区间段的最大值示例：[0, 3]Sqrt[x]

在此处输入图像描述

在这种情况下，段高度函数是Re[Sqrt[3-3*Range[1,17]/18]]，值是：

  • 确切形式：

{Sqrt[17/6], 2 Sqrt[2/3], Sqrt[5/2], Sqrt[7/3], Sqrt[13/6], Sqrt[2], Sqrt[11/6], Sqrt [5/3]、Sqrt[3/2]、2/Sqrt[3]、Sqrt[7/6]、1、Sqrt[5/6]、Sqrt[2/3]、1/Sqrt[2]、 1/Sqrt[3], 1/Sqrt[6]}

  • 近似形式：

{1.6832508230603465，1.632993161855452，1.5811388300841898，1.5275252316519468，1.4719601443879744，1.4142135623730951，1.35400640077266，1.2909944487358056，1.224744871391589，1.1547005383792517，1.0801234497346435，1，0.9128709291752769，0.816496580927726，0.7071067811865475，0.5773502691896258，0.4082482904638631}

您归档的是一个装箱问题，其中部分装满了垃圾箱。

寻找 b

如果是未知的，或者我们的任务是在所有棒形成初始束配合的情况下b找到最小的可能。b然后我们可以至少b将值限制为：

  1. 下限：如果段高度之和 = 棒高度之和
  2. 上限：分段数 = 最长棒数 < 最长分段高度

最简单的查找方法之一b是在(higher limit-lower limit)/2存在解决方案时进行查找。然后它变成新的上限或下限，您重复该过程，直到满足所需的精度。

当您在寻找时，b您不需要精确的结果，而是次优的，如果您使用有效的算法找到与实际值相对接近的枢轴点，速度会更快b。

例如：

  • 按长度排序棍子：从大到小
  • 开始“将最大的物品”放入适合您的第一个箱子
于 2011-02-23T22:48:59.497 回答
12

这相当于有多个背包（假设这些块的“高度”相同，这意味着每条“行”都有一个背包），因此是装箱问题的一个实例。

见http://en.wikipedia.org/wiki/Bin_packing

于 2011-02-22T22:37:38.353 回答
2

如何将这些棒堆叠在抛物线内，以便尽可能减少它使用的（垂直）空间？

只需像处理任何其他装箱问题一样处理它。我会对其进行元启发式算法（例如禁忌搜索，模拟退火，...），因为这些算法不是特定于问题的。

例如，如果我从Drools Planner中的Cloud Balance 问题（= Bin Packing 的一种形式）开始。如果所有的棍子都具有相同的高度，并且 2 根棍子之间没有垂直空间，那么我不需要改变太多：

  • 重命名Computer为ParabolicRow. 删除它的属性（cpu、内存、带宽）。给它一个唯一的level（其中 0 是最低行）。创建多个ParabolicRows.
  • 重命名Process为Stick
  • 重命名ProcessAssignement为StickAssignment
  • 重写硬约束，以便检查是否有足够的空间容纳所有Sticks分配给 a的总和ParabolicRow。
  • 重写软约束以最小化level所有ParabolicRows.
于 2011-02-23T08:42:20.283 回答
2

我很确定它相当于装箱：

非正式减少

将最宽行的宽度设为 x，使 bin 大 2 倍，并为每一行创建一个占位符元素，该元素是 2x-rowWidth 大。所以两个占位符元素不能被打包到一个 bin 中。

为了减少抛物线背包上的装箱，您只需为所有大于所需 binsize 且大小为 width-binsize 的行创建占位符元素。此外，为小于填充整行的 binsize 的所有行添加占位符。

这显然意味着您的问题是 NP 难的。

对于其他想法，请看这里：http ://en.wikipedia.org/wiki/Cutting_stock_problem

于 2011-03-22T14:23:18.933 回答
1

这很可能是 1-0 背包或垃圾箱包装问题。这是一个 NP 难题，很可能这个问题我不明白，我无法向您解释，但您可以使用贪心算法进行优化。这是一篇关于它的有用文章http://www.developerfusion.com/article/5540/bin-packing，我用它在 phpclasses.org 上制作我的 php 类 bin-packing。

于 2011-03-22T14:28:13.803 回答
1

向那些提到级别可能处于不同高度这一事实的人提供支持（例如：假设棒是 1 个“厚”级别 1 从 0.1 个单位变为 1.1 个单位，或者它可以从 0.2 个单位变为 1.2 个单位）

您当然可以扩展“多箱包装”方法并测试任意小的增量。（例如：运行多重装箱方法，级别从 0.0、0.1、0.2、... 0.9 开始），然后选择最佳结果，但除非您有一些方法，否则您似乎会在无限时间内卡住计算验证您是否“正确”（或更准确地说，您的所有“行”对于它们所包含的内容都是正确的，此时您可以将它们向下移动，直到它们遇到抛物线的边缘）

此外，OP 没有指定必须水平放置木棍 - 尽管 OP 可能暗示了这些甜美的图画。

我不知道如何以最佳方式解决这样的问题，但我敢打赌，在某些情况下，您可以随机放置棍子，然后测试它们是否在抛物线“内部”，它会击败任何仅依赖水平的方法行。（考虑我们试图用一根长棒填充的窄抛物线的情况。）

我说把它们都扔进去然后摇晃它们；）

于 2013-03-08T16:50:06.857 回答