分布式并行处理.doc

学生学号
1
论文成绩
武汉理工大学
研究生课程论文
课程名称 分布式并行处理
论文题目 装箱问题的算法报告
专业班级 计算机应用1002班
学生姓名 李 霞
任课老师 袁景凌
2010 — 2011 学年 第 二 学期
装箱问题的算法报告
一．实验环境
Visual C++ ，MPICH2
二．实验目的
（1）通过这次实验，更好的了解装箱问题算法的串行下次适应算法和并行下次适应算法及其思想，对这两个算法进行实现，并分析实验结果。
（2）在（1）的基础上，分析并行算法与串行算法的差别以及并行算法的优越性。
（3）最后通过分析装箱问题的几种算法，理解各种算法的思想及与其他算法相比的优越性。
三．实验内容
装箱问题及其串行算法：经典的一维装箱问题(Bin Packing Problem)是指，给定件物品的序列，物品的大小，要求将这些物品装入单位容量1的箱子中，使得每个箱子中的物品大小之和不超过1，并使所使用的箱子数目最小。
下次适应算法（Next Fit Algorithm）是最早提出的、最简单的一个在线算法，[Joh73]首次仔细分析了下次适应算法的最坏情况性能。下次适应算法维持一个当前打开的箱子，它依序处理输入物品，当物品到达时检查该物品能否放入这个当前打开的箱子中，若能则放入；否则把物品放入一个新的箱子中，并把这个新箱子作为当前打开的箱子。算法描述如下：
串行下次适应算法
输入：输入物品序列。
输出：使用的箱子数目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 */
装箱问题的并行算法：下次适应算法使用一遍扫描物品序列来实现，本身具有固有的顺序性，其时间复杂度为O(n)。我们使用平衡树和倍增技术对其进行并行化。首先利用前缀和算法建立一个链表簇，令A[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)为头的链表的长度即是下次适应算法所使用的箱子数目。接下来利用在上一步骤中产生的中间数据反向建立一棵二叉树，使该二叉树的叶节