有关优化和决策版本的装箱 [英] Bin Packing regarding Optimization and Decision Versions

问题描述

我正在为考试而学习，我们遇到了一系列练习问题.这是我正在努力解决的问题，希望有人可以帮助您阐明解决此问题的正确方法:

I'm studying for an exam and we were given a set of practice problems. Here's one I'm struggling with and I hope somebody can help shed some light on the right approach to this problem:

这是我最初要解决的问题:

Here's my initial go at the problem:

决策版本: 为了使用决策版本找到最佳解决方案，我将尝试使用各种K，直到得到肯定的答案.假设优化的解决方案是7，我会尝试:

Decision Version: To find the optimal solution using the decision version, I would try using various K's until I got a yes answer. Let's say the optimized solution is 7, I would try :

k=1, no
k=2, no
k=3, no
k=4, no
k=5, no
k=6, no
k=7, yes. 

因此，现在我们知道最佳解决方案是7个纸箱，我们通过按从最大到最小的大小对项目进行排序，并填充最大到最小的纸箱，然后循环遍历这些纸箱，直到解决它们，从而解决了决策版本集合中没有更多元素.

So now that we know that the optimal solution is 7 bins, we solve the decision version by sorting the items by sizes from largest to smallest, and filling up the bins filling largest to smallest, and looping back over the bins until they are no more elements in the set.

如果我们有一个最佳解决方案，并且想求解决策版本，那么我将采用最优解决方案返回的垃圾箱数量，并在决策版本上运行它，以查看是否返回是.

If we have an optimal solution and we want to solve the decision version, I would take the number of bins returned by the optimal solution, and run it on the decision version to see if it returns yes.

我之前从未真正看到过这样的问题，所以我不确定应该采用什么样的格式.

I've never really seen a problem like this before so I'm not sure how the proper format is supposed to be.

任何帮助将不胜感激！

Any help would be greatly appreciated!

推荐答案

有一种更好的方法可以基于决策问题来解决优化问题，请注意，您的解决方案是指数形式的(伪多项式，但仍然是指数形式)输入 的大小，因为如果决策问题在T(n)中运行，则建议的解决方案在O(k*T(n))中运行，但是由于k在大小上实际上是指数的输入(只需要log(k)位来表示它)，您就拥有了指数运行时间.

There is a much better approach to solving the optimization problem based on the decision problem, note that your solution is exponential (pseudo-polynomial, but still exponential) in the size of the input, since if you have an algorithm that runs in T(n) on the decision problem, the suggested solution runs in O(k*T(n)), but since k is actually exponential in the size of the input (you need only log(k) bits to represent it), you have an exponential run time.

但是，您可以对问题进行二进制搜索，并且只需要对决策问题的算法进行调用即可解决优化问题.

However, you can apply binary search on the problem, and require only O(log(k)) invokations of the algorithm of the decision problem in order to solve the optimization problem.

现在，如果P = NP，并且这种算法(用于解决决策问题)存在于多项式时间O(p(n))中，则将在O(p(n) * log(k))中完成对优化问题的求解-这是输入大小的多项式.

Now, if P=NP, and such algorithm (for solving the decision problem) exists in polynomial time O(p(n)), solving the optimization problem will be done in O(p(n) * log(k)) - which is polynomial in the size of the input.

二进制搜索将如下所示:

The binary search will go something like that:

k <- 1
while decision_bin_packing(G,k) == false:
    k <- k * 2
perform binary search for the smallest value t in [k/2,k] such that decision_bin_packing(G,t)==true

最后的二进制搜索是相当标准的，并且只需decision_bin_packing的O(logk)调用即可轻松实现.

The last binary search is pretty standard, and can be easily implemented with only O(logk) invokations of decision_bin_packing.

这篇关于有关优化和决策版本的装箱的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！