13装箱问题 131装箱问题及其串行算法 经典的一维装箱问题( Bin Packing Problem)是指,给定n件物品的序列 Ln=<a1,a2…,an>,物品a;(1≤i≤n)的大小s(a1)∈(0.1,要求将这些物品装入单位容 量1的箱子B1,B2…,Bn中,使得每个箱子中的物品大小之和不超过1,并使所使用的箱子 数目m最小。 下次适应算法( Next Fit Algorithm)是最早提出的、最简单的一个在线算法,[Joh73 首次仔细分析了下次适应算法的最坏情况性能。下次适应算法维持一个当前打开的箱子,它 依序处理输入物品,当物品到达时检查该物品能否放入这个当前打开的箱子中,若能则放入: 否则把物品放入一个新的箱子中,并把这个新箱子作为当前打开的箱子。算法描述如下: 算法16.5装箱问题的下次适应算法 输入:输入物品序列L=<a12a2,…,an>。 输出:使用的箱子数目m,各装入物品的箱子P=<B1,B2,…,Bn> procedure NextFit Begin (1)S(B)=1/初始化当前打开的箱子B,令B已满* (2)m=0 /*使用箱子计数 (3)fori=1 to n do ifs(ai)+s(B)s I then (i)s(B)=s(B)+sa)/*把a放入B中 (i)m=m+1 /*使用的箱子数加一*/ (ii)b=Bm /*新打开箱子Bm*/ (iii)s(B)=s(ai) /*把a放入B中 end if End / NextFit * 132装箱问题的并行算法 算法16.5使用一遍扫描物品序列来实现,本身具有固有的顺序性,其时间复杂度为On)。 我们使用平衡树和倍增技术对其进行并行化。首先利用前缀和算法建立一个链表簇,令A7 为输入物品序列中第i件物品的大小,如果链表指针由AD指向Ak,则表示 AD+4+1]+.+4k>1且A++1]++A/k-1]≤1;其后利用倍增技术计算以4①]为头的 链表的长度,而以A(1)为头的链表的长度即是下次适应算法所使用的箱子数目。接下来利用 在上一步骤中产生的中间数据反向建立一棵二叉树,使该二叉树的叶节点恰好是下次适应算 法在各箱子中放入的第一个物品的序号:最后,根据各箱子中放入的第一个物品的序号,使 6
6 1.3 装箱问题 1.3.1 装箱问题及其串行算法 经典的一维 装 箱 问 题 (Bin Packing Problem) 是指，给定 n 件物品的序列 1 2 , , , L a a a n n = ，物品 a (1 i n) i 的大小 ( )(0,1] ai s ，要求将这些物品装入单位容 量 1 的箱子 1 2 , , , B B B m 中，使得每个箱子中的物品大小之和不超过 1，并使所使用的箱子 数目 m 最小。 下次适应算法（Next Fit Algorithm）是最早提出的、最简单的一个在线算法，[Joh73] 首次仔细分析了下次适应算法的最坏情况性能。下次适应算法维持一个当前打开的箱子，它 依序处理输入物品，当物品到达时检查该物品能否放入这个当前打开的箱子中，若能则放入； 否则把物品放入一个新的箱子中，并把这个新箱子作为当前打开的箱子。算法描述如下： 算法 16.5 装箱问题的下次适应算法 输入：输入物品序列 1 2 , , , L a a a = n 。 输出：使用的箱子数目 m，各装入物品的箱子 1 2 , , , P B B B = m 。 procedure NextFit Begin （1）s(B) = 1 /* 初始化当前打开的箱子 B，令 B 已满 */ （2）m = 0 /* 使用箱子计数 */ （3）for i = 1 to n do if s(ai) + s(B) 1 then （i） s(B) = s(B) + s(ai) /* 把 ai 放入 B 中 */ else （i） m = m + 1 /* 使用的箱子数加一 */ （ii） B = Bm /* 新打开箱子 Bm */ （iii）s(B) = s(ai) /* 把 ai 放入 B 中 */ end if end for End /* NextFit */ 1.3.2 装箱问题的并行算法 算法 16.5 使用一遍扫描物品序列来实现，本身具有固有的顺序性，其时间复杂度为 O(n)。 我们使用平衡树和倍增技术对其进行并行化。首先利用前缀和算法建立一个链表簇，令 A[i] 为 输 入 物 品 序列 中 第 i 件物品的大小, 如 果链 表 指 针由 A[j] 指 向 A[k] ，则表示 A[j]+A[j+1]+…+A[k]>1 且 A[j]+A[j+1]+…+A[k-1]1；其后利用倍增技术计算以 A[1]为头的 链表的长度，而以 A(1)为头的链表的长度即是下次适应算法所使用的箱子数目。接下来利用 在上一步骤中产生的中间数据反向建立一棵二叉树，使该二叉树的叶节点恰好是下次适应算 法在各箱子中放入的第一个物品的序号；最后，根据各箱子中放入的第一个物品的序号，使
用二分法确定各物品所放入的箱子的序号。 算法166并行下次适应算法 输入:数组An],其中4[为输入物品序列中第i个物品的大小。 输出:使用的箱子数目m,每个物品应放入的箱子序号数组B[n procedure PNext Fit (1)调用求前缀和的并行算法计算FUj}=A[1+A[2H+…+4[ (2) forj=I to n pardo 借助F,使用二分法计算C[0j=max{4U]+4计+1]+…+4(k]≤1} nd fe /*以下(3)-(8),计算下次适应算法使用的箱子数目m (3)C[0,n+1=n (4)h=0 (5) for j=l to n pardo E[, J=l end for (6) while Cth,1]≠nd (6.1)h=h+1 (6.2)forj=I to n pardo if CTh-1,J]=n then (i) E[h,j]=E[h-1,j1 (ii)C[,j]=CTh-1j1 (i)E[h,j=E[h-1,j+E[h-1,Ch-1,j+1 (i1)Ch,j=CTh-1, Ch-1,J+1] d if end for end while (7) height=h (9)/计算D[O,j=第j个箱子中第一件物品在输入序列中的编号* for h= height downto o do forj=1 to n/2 pardo (i) ifj=even then D[h j]=C[h, D[h-1,j/2J]+1 endif (ii) ifj=I then D[h, 1]=1 endif (iii) ifj=odd>I then D[h, j]=D[h-1, [j+1)/2]endif end for (10) for F=l to n pardo/*计算B[=第j个物品所放入的箱子序号* 使用二分法计算B]=max{kD0k],D[Ok+1或者k=m} end for End/* PNext Fit*/ MPI源程序请参见所附光盘
7 用二分法确定各物品所放入的箱子的序号。 算法 16.6 并行下次适应算法 输入：数组 A[1,n]，其中 A[i]为输入物品序列中第 i 个物品的大小。 输出：使用的箱子数目 m，每个物品应放入的箱子序号数组 B[1,n]。 procedure PNextFit Begin （1）调用求前缀和的并行算法计算 F[j]= A[1]+A[2]+…+A[j] （2）for j = 1 to n pardo 借助 F[j]，使用二分法计算 C[0,j]= max{k|A[j]+A[j+1]+…+A[k] 1} end for /* 以下（3）-（8），计算下次适应算法使用的箱子数目 m */ （3）C[0, n+1] = n （4）h = 0 （5）for j=1 to n pardo E[0, j]=1 end for （6）while C[h,1] n do （6.1）h = h + 1 （6.2）for j = 1 to n pardo if C[h - 1, j] = n then （i）E[h, j] = E[h-1, j] （ii）C[h,j] = C[h - 1,j] else （i）E[h, j] = E[h - 1, j] + E[h - 1,C[h - 1, j] + 1] （ii）C[h, j] = C[h - 1,C[h - 1, j] + 1] end if end for end while （7）height = h （8）m = E[height, 1] （9）/* 计算 D[0, j]=第 j 个箱子中第一件物品在输入序列中的编号 */ for h = height downto 0 do for j = 1 to n / 2 h pardo （i）if j = even then D[h,j] = C[h,D[h-1,j/2]]+1 endif （ii）if j = 1 then D[h,1] = 1 endif （iii）if j = odd > 1 then D[h,j] = D[h-1,[j+1]/2] endif end for end for （10）for j=1 to n pardo /* 计算 B[j] = 第 j 个物品所放入的箱子序号 */ 使用二分法计算 B[j] = max{ k | D[0,k] j , D[0,k+1] >j 或者 k = m } end for End /* PNextFit */ MPI 源程序请参见所附光盘