装箱 - 强力递归解决方案 - 如何使它更快 [英] Bin Packing - Brute force recursive solution - How to make it faster
问题描述
我有一个数组，其中包含不同尺寸的材料清单： {4,3,4,1,7,8} 。然而，仓可容纳高达物料大小10.我需要找出收拾数组中的所有元素所需箱的最低数量。
I have an array which contains a list of different sizes of materials : {4,3,4,1,7,8} . However, the bin can accomodate materials upto size 10. I need to find out the minimum number of bins needed to pack all the elements in the array.
有关上述阵列，您可以在3箱包装和它们划分如下： {4,4,1} ， {3， 7} ， {8} 。有迹象表明，还适合为三个库存管其他可能的安排，但它不能用较少完成
For the above array, you can pack in 3 bins and divide them as follows: {4,4,1}, {3,7} , {8} . There are other possible arrangements that also fit into three stock pipes, but it cannot be done with fewer
我试图通过递归来解决这个问题，才能更好地理解它。
I am trying to solve this problem through recursion in order to understand it better.
我使用这的DP配方（PDF文件第20页）
I am using this DP formulation (page 20 of the pdf file)
考虑一个输入端（N1，...，nk）个，其中n =Σnj项
确定设置的k元组（输入的子集），其可以被包装成一个单一的仓
也就是说，所有元组（Q1，...，QK），这些OPT（Q1，...，QK）= 1
记这一套由Q对于每一个K-元组Q，我们有OPT（Q）= 1
通过使用递推计算剩余值：OPT（I1，...，IK）= 1 +
minOPT（I1 - Q1，...，IK - QK）
Consider an input (n1;:::;nk) with n = ∑nj items
Determine set of k-tuples (subsets of the input) that can be packed into a single bin
That is, all tuples (q1;:::;qk) for which OPT(q1;:::;qk) = 1
Denote this set by Q For each k-tuple q , we have OPT(q) = 1
Calculate remaining values by using the recurrence : OPT(i1;:::;ik) = 1 + minOPT(i1 - q1;:::;ik - qk)
我已经做了code，并能正常工作的小数据集。但是，如果我增加数组的大小超过6个元素，它变得极其缓慢 - 大约需要25秒解决包含8个元素你能告诉我，如果孤单什么毛病算法对数组？我不需要一个替代的解决方案--- 只需要知道这是为什么这么慢，以及它如何可以改进
I have made the code, and it works fine for small data set. But if increase the size of my array to more than 6 elements, it becomes extremely slow -- takes about 25 seconds to solve an array containing 8 elements Can you tell me if theres anything wrong with the algorithm? I dont need an alternative solution --- just need to know why this is so slow, and how it can be improved
下面是code我已经用C ++编写：
Here is the code I have written in C++ :
void recCutStock(Vector<int> & requests, int numStocks)
{
if (requests.size() == 0)
{
if(numStocks <= minSize)
{
minSize = numStocks;
}
// cout<<"GOT A RESULT : "<<numStocks<<endl;
return ;
}
else
{
if(numStocks+1 < minSize) //minSize is a global variable initialized with a big val
{
Vector<int> temp ; Vector<Vector<int> > posBins;
getBins(requests, temp, 0 , posBins); // 2-d array(stored in posBins) containing all possible single bin formations
for(int i =0; i < posBins.size(); i++)
{
Vector<int> subResult;
reqMinusPos(requests, subResult, posBins[i]); // subtracts the initial request array from the subArray
//displayArr(subResult);
recCutStock(subResult, numStocks+1);
}
}
else return;
}
}
的getBins功能如下：
The getBins function is as follows :
void getBins(Vector<int> & requests, Vector<int> current, int index, Vector<Vector<int> > & bins)
{
if (index == requests.size())
{
if(sum(current,requests) <= stockLength && sum(current, requests)>0 )
{
bins.add(current);
// printBins(current,requests);
}
return ;
}
else
{
getBins(requests, current, index+1 , bins);
current.add(index);
getBins(requests, current, index+1 , bins);
}
}
推荐答案
的动态规划算法为O（n ^ {2k个}）其中，k是不同的项目数，n是物品的总数量。这可能是非常缓慢的，不论实施。通常情况下，解决了NP问题时，启发式所需要的速度。
The dynamic programming algorithm is O(n^{2k}) where k is the number of distinct items and n is the total number of items. This can be very slow irrespective of the implementation. Typically, when solving an NP-hard problem, heuristics are required for speed.
我建议你考虑下一步飞度降低高度（NFDH）和First飞度从科夫曼等降低高度（FFDH）。他们是2优和17/10-最佳，分别为，他们运行在O（N log n）的时间。
I suggest you consider Next Fit Decreasing Height (NFDH) and First Fit Decreasing Height (FFDH) from Coffman et al. They are 2-optimal and 17/10-optimal, respectively, and they run in O(n log n) time.
我建议你先试试NFDH：排序按递减顺序，结果存储在一个链表，然后反复尝试（第一大值）插入从头开始的项目，直到你填补了垃圾桶或没有更多的可插入的物品。然后进入下一个箱等。
I recommend you first try NFDH: sort in decreasing order, store the result in a linked list, then repeatedly try to insert the items starting from the beginning (largest values first) until you have filled the bin or there is no more items that can be inserted. Then go to the next bin and so on.
引用
欧文卡瑟，丹尼尔·雷赛，标签云图：算法云可视化，标记和元数据的社会信息组织（2007年WWW），2007年（参见5.1节的相关讨论。）
Owen Kaser, Daniel Lemire, Tag-Cloud Drawing: Algorithms for Cloud Visualization, Tagging and Metadata for Social Information Organization (WWW 2007), 2007. (See Section 5.1 for a related discussion.)
电子。 G.考夫曼，小，MR Garey，DS约翰逊，以及可再生能源的Tarjan。性能界水平为导向的二维包装算法。 SIAM J. COMPUT，9（4）：808-826，1980年
E. G. Coffman, Jr., M. R. Garey, D. S. Johnson, and R. E. Tarjan. Performance bounds for level-oriented two-dimensional packing algorithms. SIAM J. Comput., 9(4):808–826, 1980.
这篇关于装箱 - 强力递归解决方案 - 如何使它更快的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
