抛物线背包问题

Question

假设我有一个抛物线。现在我还有一堆相同宽度的棒子（是的，我的绘图技巧很棒！）。如何将这些棒子堆在抛物线内，使它使用的空间尽可能小？我相信这属于背包问题的范畴，但这个维基百科页面似乎没有让我更接近实际解决方案。这是NP难问题吗？

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

- rook

---

在mathoverflow.net上更合适吗？ - user229044

这些棍子能被打断吗？如果不能，那么“最小化空间”的要求不就取决于最大的棍子吗？最大的棍子和下一个棍子之间可能存在很大的间隙。这是一个有趣的问题。 - James

车-这个问题不能是NP-complete，因为它不是一个“决策问题”。要使问题成为NP-complete，它必须属于NP，这些都是决策问题（它们都有是/否回答）。但是，它可能是* NP-hard *，这意味着它至少与NP中的任何问题一样难。您可以将其构想为一个决策问题“在给定长度和某个抛物线的情况下，您是否可以将它们适合高度不超过h？” 以使其成为候选的NP-complete问题。 - templatetypedef

尽管从技术上讲是正确的，但在复杂性理论中通常惯例是推断一个优化问题与其相关的自然决策问题之间的等价性。换句话说，对于每个旨在最小化f(x)的优化问题，它的自然决策问题被表述为“对于给定的K，是否存在一些x使得f(x) < K?”。在这种情况下，自然决策问题是：“对于给定的K，是否有一种方法将棒子堆叠在高度< K之内？” - mhum

评论中的“这是否是NP难问题”子线程可能应该放在math.se上。这个问题本身可能在那里或者这里都可以得到同样好的回答。 - Ben Voigt

Answer 1

我使用 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

这是公共资源库，所以请随意创建分支并添加其他算法。由于它是一个有趣的问题，我将来可能会添加更多算法。

- gradbot

---

这个“首次适应减少”算法可能远非最佳。请看“首次适应减少”算法错误示例（左侧） 但是它是一个非常好的起点，并且速度非常快。如果你需要更多的东西（或许你不需要），特别是如果你想避免人工参与：看，如果你交换这两个，效果会更好，那么你可以在该算法的结果上运用元启发式算法去改进。 - Geoffrey De Smet

Answer 2

简化问题

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

• 我交换轴并将它们加在一起，这导致x2增长
• 我假设它是一个闭区间[a,b]上的二次函数，其中a=0，对于这个例子，b = 3

假设你有给定b（区间的第二部分）和w（段的宽度），那么你可以通过n=Floor[b/w]找到总段数。在这种情况下，存在一种平凡的情况来最大化Riemann和和函数以获取第i个段的高度：f(b-(b*i)/(n+1))。实际上这是一个假设，我不确定百分之百。

在闭区间[0, 3]上的函数Sqrt[x]的17段高度的最大化示例：

在这种情况下，段的高度函数是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最简单的方法之一是在(上限-下限)/2处取一个中心点，查看是否存在解。然后它成为新的更高或更低的限制，并且您重复该过程，直到达到所需的精度。

---

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

例如：

• 按长度排序棍子：从大到小
• 开始“放置最大项”以适合第一个箱子

- Margus

---

你的上限显然是错误的（拿一根比最低的箱子更长的木棍就可以证明）。 - Ben Voigt

@Ben Voigt：您是正确的，那是一个粗心的错误。感谢您抽出时间指出它。 - Margus

最坏的情况是，我认为你需要把这两个加在一起（例如，4根棍子都是100长，最优解是占据10、11、12、13行）。 - Ben Voigt

这似乎是解决方案的“程序员”版本。现在我读了你的帖子，我看到了相似之处。但是，由于您的帖子没有显示此问题不在P中（这只会让人们停止浪费时间寻找更好的解决方案），读者可能会对我的答案中更或多或少非正式的双向约简感兴趣（我承认需要一些复杂性理论背景才能理解）。 - sleeplessnerd

Answer 3

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

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

- dfb

---

您的降维方向不正确。您已经展示出可以将此问题转化为装箱问题，但这只是表明装箱问题至少与此问题一样难。您需要展示相反的方向——任何装箱问题的实例都可以被转化为此问题的实例——以证明此问题至少与NP难度的装箱问题一样困难。 - templatetypedef

取决于你是否想要最小化垂直空间？如果不是，我认为任何打包都会有相同数量的空间。 - dfb

@templatetypedef - 这是正确的，这更像是一个指针而不是证明。我认为显而易见的缩减方法是为每个箱子创建宽度为x的形状，这可能是正确的方向。 - dfb

@spintheblack: “装箱问题”（Bin-packing）并不是这个问题的一个特殊情况（以任何明显的方式）。经典的“装箱问题”中所有的箱子大小都相同，而这里的箱子大小是可变的。此外，如果我们将经典的“装箱问题”扩展到包括大小可变的箱子，我们仍然面临着这个问题：这个问题中的箱子大小受到特定形式的限制。 - mhum

@mhum - 你所写的正是我所依据的，所以也许我漏掉了什么。如果你同意装箱问题是多尺寸装箱问题有序箱子（箱子x_1 <= x_2 <= ...必须按升序装入），那么我认为我们是在同一页面上。 - dfb

Answer 4

我非常确定这等同于装箱问题：

非正式的降低难度方法：

假设x是最宽行的宽度，将箱子变成2x大，并为每一行创建一个占位元素，其大小为2x-rowWidth。因此，两个占位符元素无法放入一个箱子中。

要在抛物线背包上减少装箱问题，只需为所有大于所需箱子尺寸的行创建占位符元素，其大小为width-binsize。此外，为所有小于binsize的行添加填满整行的占位符。

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

其他想法可以在这里查看：http://en.wikipedia.org/wiki/Cutting_stock_problem

- sleeplessnerd

Answer 5

如何将这些棍子堆叠在抛物线内，使其尽可能地减少（垂直）所占用的空间？

只需像处理其他“装箱”问题一样处理即可。我会使用元启发式算法（例如禁忌搜索、模拟退火等），因为这些算法不是特定于问题的。

例如，如果我从Cloud Balance problem（一种装箱问题形式）开始，在Drools Planner中解决。如果所有的棍子高度相同，并且上下两个棍子之间没有垂直空间，那么我需要改变的就不多了：

将计算机重命名为“抛物线行”。删除其属性（CPU、内存、带宽）。给它一个独特的“级别”（其中0是最低的行）。创建若干个“抛物线行”。

将进程重命名为“棒”。

将进程分配重命名为“棒分配”。

重写硬约束条件，以便检查是否有足够的空间来容纳分配给“抛物线行”的所有“棒”的总和。

重写软约束条件，以使所有“抛物线行”的最高“级别”最小化。

- Geoffrey De Smet

---

有趣，但我不知道这与算法分析有什么关系。 - rook

以下是关于编程的内容，介绍如何使用概率方法来解决NP难问题。 - Martin DeMello

Answer 6

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

- Micromega

Answer 7

赞扬那些提到级别可以在不同高度的人（例如：假设棍子是1“厚”，级别1从0.1单位到1.1单位，或者它可以从0.2到1.2单位）。

当然，您可以扩展“多个箱装法”方法并测试任意小的增量。 （例如：使用从0.0、0.1、0.2、... 0.9开始的级别运行多个箱装法），然后选择最佳结果，但是除非您有某种验证已经得到“正确”（更准确地说，您已经正确地包含了所有“行”所包含的内容，此时您可以将它们向下移动，直到它们与抛物线的边缘相遇），否则似乎会陷入无限计算的困境。

此外，OP没有明确指定棍子必须水平放置-尽管也许OP用那些精美的图画暗示了这一点。

我不知道如何最优地解决这个问题，但我敢打赌，在某些情况下，您可以随机放置木棍，然后测试它们是否在抛物线“内部”，这将超越任何仅依赖水平行的方法。 （考虑我们试图用一根长棍填满的狭窄抛物线的情况。） 我建议只是把它们全部扔进去然后摇晃 ;)

- Allen