4组合优化 组合优化问题在实践中有着广泛的应用,同时也是计算机科学中的重要研究课题。本章 对于八皇后问题、SAT问题、装箱问题、背包问题及TSP问题等五个经典的组合优化问题, 给出其定义、串行算法描述、并行算法描述以及并行算法的MPI源程序, 1.1八皇后问题 1.1.1八皇后问题及其串行算法 所谓八皇后问题( Eight Queens Problem),是在8*8格的棋盘上,放置8个皇后。要求 每行每列放一个皇后而且每一条对角线和每一条反对角线上最多只能有一个皇后,即对同 时放置在棋盘的任意两个皇后(1,元)和(2,2),不允许(1-12)=(-12)或者 (+1)=(i2+2)的情况出现 八皇后问题的串行解法为如下的递归算法: 算法16.1八皇后问题的串行递归算法 /*从 chessboard的第row行开始放置皇后* procedure Place Queens( chessboard, row) oIn if row >8 then OutputResult( chessboard) /*结束递归并输出结果* for col=lto8do/*判断是否有列、对角线或反对角线冲突* (1)no collision=true (2)i= (3) while no collision and i< row do (3. 1)if collides( i, chessboard[i], row, col)then no collision false end if (3.2)i=i+1 end while (4) if no collision then (41) chessboard row]=col/*在当前位置放置一个皇后* /*递归地从下一行开始放置皇后* end for end if End/ Place Queens *
1 1. 4 组合优化 组合优化问题在实践中有着广泛的应用，同时也是计算机科学中的重要研究课题。本章 对于八皇后问题、SAT 问题、装箱问题、背包问题及 TSP 问题等五个经典的组合优化问题， 给出其定义、串行算法描述、并行算法描述以及并行算法的 MPI 源程序。 1.1 八皇后问题 1.1.1 八皇后问题及其串行算法 所谓八皇后问题（Eight Queens Problem），是在 8*8 格的棋盘上，放置 8 个皇后。要求 每行每列放一个皇后,而且每一条对角线和每一条反对角线上最多只能有一个皇后，即对同 时 放 置在 棋盘 的 任意 两个 皇 后 1 1 ( , ) i j 和 2 2 ( , ) i j ， 不 允许 1 2 1 2 ( ) ( ) i i j j − = − 或 者 1 1 2 2 ( ) ( ) i j i j + = + 的情况出现。 八皇后问题的串行解法为如下的递归算法： 算法 16.1 八皇后问题的串行递归算法 /* 从 chessboard 的第 row 行开始放置皇后 */ procedure PlaceQueens(chessboard, row) Begin if row > 8 then OutputResult(chessboard) /* 结束递归并输出结果 */ else for col = 1 to 8 do /* 判断是否有列、对角线或反对角线冲突 */ （1）no_collision = true （2）i = 1 （3）while no_collision and i < row do （3.1）if collides(i, chessboard[i], row, col) then no_collision = false end if （3.2）i = i + 1 end while （4）if no_collision then （4.1）chessboard[row] = col /* 在当前位置放置一个皇后 */ （4.2）go(step + 1, place) /* 递归地从下一行开始放置皇后 */ end if end for end if End /* PlaceQueens */
12八皇后问题的并行算法 该算法是将八皇后所有可能的解置于相应的棋盘上,主进程负责生成初始化的棋盘,并 将该棋盘发送到某个空闲的从进程,由该从进程求出该棋盘上满足初始化条件的所有的解 这里,我们假定主进程只初始化棋盘的前两列,即在棋盘的前两列分别放上2个皇后,这样 就可以产生8*8=64个棋盘 算法162八皇后问题的并行算法 (1)主进程算法 procedure Eight QueensMaster Begin (1) active slaves =n (2) while active slaves >0 do (2.1)从某个从进程i接收信号 signal (2.2) if signal= Accomplished then从从进程i接收并记录解 end if (2.3) if has more boards then (i)向从进程i发送 New Task信号 (ⅱi)向从进程i发送一个新棋盘 (i)向从进程i发送 Terminate信号 ii)active slaves =active slaves-I end while End/* Eight Queens Master * (2)从进程算法 procedure Eight Queen Slave Begin (1)向主进程发送 Ready信号 (2) finished= fal (3) while not finished do (3.1)从主进程接收信号 signal (3.2) if signal = New Task then (i)从主进程接收新棋盘 i)if新棋盘合法then 在新棋盘的基础上找出所有合法的解,并将解发送给主进程 end if else / signal Terminate * finished true end if end while End/* Eight Queen Slave MPI源程序请参见章末附录
2 1.1.2 八皇后问题的并行算法 该算法是将八皇后所有可能的解置于相应的棋盘上，主进程负责生成初始化的棋盘，并 将该棋盘发送到某个空闲的从进程，由该从进程求出该棋盘上满足初始化条件的所有的解。 这里，我们假定主进程只初始化棋盘的前两列，即在棋盘的前两列分别放上 2 个皇后，这样 就可以产生 8 * 8 = 64 个棋盘。 算法 16.2 八皇后问题的并行算法 （1）主进程算法 procedure EightQueensMaster Begin （1）active_slaves = n （2）while active_slaves > 0 do （2.1）从某个从进程 i 接收信号 signal （2.2）if signal = Accomplished then 从从进程 i 接收并记录解 end if （2.3）if has_more_boards then (ⅰ)向从进程 i 发送 NewTask 信号 (ⅱ)向从进程 i 发送一个新棋盘 else (ⅰ)向从进程 i 发送 Terminate 信号 (ⅱ)active_slaves = active_slaves - 1 end if end while End /* EightQueensMaster */ （2）从进程算法 procedure EightQueenSlave Begin （1）向主进程发送 Ready 信号 （2）finished = false （3）while not finished do （3.1）从主进程接收信号 signal （3.2）if signal = NewTask then (ⅰ)从主进程接收新棋盘 (ⅱ)if 新棋盘合法 then 在新棋盘的基础上找出所有合法的解，并将解发送给主进程 end if else /* signal = Terminate */ finished = true end if end while End /* EightQueenSlave */ MPI 源程序请参见章末附录
12SAT问题 121SAT问题及其串行算法 1SAT问题描述 所谓可满足性问题( Satisfiability Problem)即SAT问题,其定义为:对于一个命题逻 辑公式,是否存在对其变元的一个真值赋值公式使之成立。这个问题在许多领域都有着非常 重要的意义,而且对其快速求解算法的研究成为计算机科学的核心课题之一。例如在机器定 理证明领域,某命题是否是一个相容的公理集合的推论,这个问题归结为该命题的反命题与 该公理集合一起是否是不可满足的。特别是1971年Cook首次证明了SAT是NP完全的, 从而大量的计算问题都可以归结到SAT。正是由于SAT重要的理论和应用地位,众多学者 对它进行了广泛而深入的研究 由命题逻辑知识可以知道,任何命题逻辑公式都逻辑等价与一个合取范式 Conjunctive Normal form,简写为CNF,因此本文只讨论CNF的SAT求解问题 下面给出几种常见的SAT问题化简策略,以下均假定F是CNF范式:①单元子句规则: 若C=L}是F的子句,则F变为F'=F[F]:②纯文字规则:若文字L出现在F中,而一L 不出现F中,则L称为F的纯文字。F变为F=FF]:③重音子句规则:若C∈F且C是 重言子句,则从F中删去C得F'=FC;④两次出现规则:若L∈C1,L∈C2,且L和L 都不在其它子句中出现,则将C1,C2合并为C'=(C1-{L})U(C2{→L}),F变为F=F- C1,C2}UC}:⑤包含规则:若C1,C2是F的子句,且C1∈C2,则F中删去C2,得 C2}。 2SAT问题串行算法 SAT问题的DP算法是由 M. Davis和 H. Putnam于1960年首次提出,现在已经成为最 著名的SAT算法,其描述如下: 算法16.3SAT问题的DP算法 输入:合取范式F 输出:F是否可满足 (1)iF为空公式then return Yes if (2)ifF包含一个空子句then return No end if (3)iF包含一个子句{l}then /*单元子句规则* return DP(F/ID) end if (4)iF包含一个文字l,但不包含 I then/*纯文字规则 return DP(FI/D)
3 1.2 SAT 问题 1.2.1 SAT 问题及其串行算法 1.SAT 问题描述 所谓可满足性问题（Satisfiability Problem）即 SAT 问题，其定义为：对于一个命题逻 辑公式，是否存在对其变元的一个真值赋值公式使之成立。这个问题在许多领域都有着非常 重要的意义，而且对其快速求解算法的研究成为计算机科学的核心课题之一。例如在机器定 理证明领域，某命题是否是一个相容的公理集合的推论，这个问题归结为该命题的反命题与 该公理集合一起是否是不可满足的。特别是 1971 年 Cook 首次证明了 SAT 是 NP-完全的， 从而大量的计算问题都可以归结到 SAT。正是由于 SAT 重要的理论和应用地位，众多学者 对它进行了广泛而深入的研究。 由命题逻辑知识可以知道，任何命题逻辑公式都逻辑等价与一个合取范式(Conjunctive Normal Form，简写为 CNF),因此本文只讨论 CNF 的 SAT 求解问题。 下面给出几种常见的 SAT 问题化简策略，以下均假定 F 是 CNF 范式：①单元子句规则： 若 C=｛L｝是 F 的子句，则 F 变为 F’=F[F/1]；②纯文字规则：若文字 L 出现在 F 中，而 L 不出现 F 中，则 L 称为 F 的纯文字。F 变为 F’=F[F/1]；③重言子句规则：若 C∈F 且 C 是 重言子句，则从 F 中删去 C 得 F’=F-C；④两次出现规则：若 L∈C1， L∈C2，且 L 和 L 都不在其它子句中出现，则将 C1 ，C2 合并为 C’=( C1-｛L｝)∪( C2-｛ L｝)，F 变为 F’=F- ｛C1, C2｝∪｛C’｝；⑤包含规则：若 C1 ，C2是 F 的子句，且 C1∈C2，则 F 中删去 C2，得 F’=F-｛C2｝。 2.SAT 问题串行算法 SAT 问题的 DP 算法是由 M.Davis 和 H.Putnam 于 1960 年首次提出[2]，现在已经成为最 著名的 SAT 算法，其描述如下： 算法 16.3 SAT 问题的 DP 算法 输入：合取范式 F。 输出：F 是否可满足。 procedure DP(F) Begin (1) if F 为空公式 then return Yes end if (2) if F 包含一个空子句 then return No end if (3) if F 包含一个子句{l} then /* 单元子句规则 */ return DP(F[l/1]) end if (4) if F 包含一个文字 l，但不包含 l then /* 纯文字规则 */ return DP(F[l/1])
end if (5)选择一个未赋值的文字 (6)/*拆分 if DP(F[/1)=Yes then return Yes else return DP(F[OD) end if End/* dp * 可以看出,DP算法是对回溯算法的精化,其中应用了我们在前面提到的化简策略单元 子句规则和纯文字规则。前面已经介绍过,这些策略并不能在数量级上降低算法的时间复杂 度,但实验证明这些策略的应用可以极大的改善平均性能。其实,上面介绍的策略都可以应 用于SAT的求解,而且已经有了这方面的工作。 122SAT问题的并行算法 1并行化思路 通过我们在前面对串行DP算法的介绍可以看出,实际上DP算法仍然是利用深度优先 方法对可能的解空间做深度优先搜索,这样我们仍然可以把这个解空间看成一棵二叉树。而 它与回溯搜索算法的区别仅仅在于它利用了SAT的一些性质巧妙的找到了一些仅有一种赋 值可能的文字,这样就有效地减少了搜索开销。同时在搜索一棵子树时,对某个文字的赋值 可能导致新的单元子句的产生,这样,从平均意义上考虑,对这一性质的反复利用可以极大 地加快搜索速度。容易知道,对于寻找单元子句和纯文字的工作是在多项式时间内完成的, 因此我们可以由主进程预先把CNF的所有单元子句和纯文字找出来,对它们分别赋上可能 使CNF得到满足的值,并按照某种策略选取n个文字对他们预先赋值,共得到2组解。然 后把这些信息分别发送给各个从进程进行计算,并收集运算结果。这样既避免了各个从进程 重复寻找单元子句和纯文字,又有可能通过对选出的n个文字的赋值产生了新的单元子句, 从而加快了整个程序的搜索速度。 2并行DP算法 算法16.4SAT问题的并行DP算法 输入:合取范式F 输出:F是否可满足 (1)主进程算法 procedure PDPMaster(F (1)找出n个文字,并初始化任务队列 (2)j=0 (3)向每个从进程发送一个任务 (4) while true do (4.1)某个从进程p接收结果 (4.2) if result= true then (i)向所有从进程发送终止信号
4 end if (5) 选择一个未赋值的文字 l (6) /* 拆分 */ if DP(F [l/1]) = Yes then return Yes else return DP(F [l/0]) end if End /* DP */ 可以看出，DP 算法是对回溯算法的精化，其中应用了我们在前面提到的化简策略单元 子句规则和纯文字规则。前面已经介绍过，这些策略并不能在数量级上降低算法的时间复杂 度，但实验证明这些策略的应用可以极大的改善平均性能。其实，上面介绍的策略都可以应 用于 SAT 的求解，而且已经有了这方面的工作。 1.2.2 SAT 问题的并行算法 1.并行化思路 通过我们在前面对串行 DP 算法的介绍可以看出，实际上 DP 算法仍然是利用深度优先 方法对可能的解空间做深度优先搜索，这样我们仍然可以把这个解空间看成一棵二叉树。而 它与回溯搜索算法的区别仅仅在于它利用了 SAT 的一些性质巧妙的找到了一些仅有一种赋 值可能的文字，这样就有效地减少了搜索开销。同时在搜索一棵子树时，对某个文字的赋值 可能导致新的单元子句的产生，这样，从平均意义上考虑，对这一性质的反复利用可以极大 地加快搜索速度。容易知道，对于寻找单元子句和纯文字的工作是在多项式时间内完成的， 因此我们可以由主进程预先把 CNF 的所有单元子句和纯文字找出来，对它们分别赋上可能 使 CNF 得到满足的值，并按照某种策略选取 n 个文字对他们预先赋值，共得到 2 n 组解。然 后把这些信息分别发送给各个从进程进行计算，并收集运算结果。这样既避免了各个从进程 重复寻找单元子句和纯文字，又有可能通过对选出的 n 个文字的赋值产生了新的单元子句， 从而加快了整个程序的搜索速度。 2.并行 DP 算法 算法 16.4 SAT 问题的并行 DP 算法 输入：合取范式 F。 输出：F 是否可满足。 （1）主进程算法 procedure PDPMaster(F) Begin （1）找出 n 个文字，并初始化任务队列 （2）j = 0 （3）向每个从进程发送一个任务 （4）while true do （4.1）某个从进程 pi 接收结果 （4.2）if result = true then （i）向所有从进程发送终止信号
else (i)向所有从进程发送终止信号 (ii) return false (i)向p发送下一个任务 d if end while End / PDPMaster * (2)从进程算法 procedure PDPSlave for each processor p., where I≤i≤k while true do (1)从主进程接收信号 (2) if signal= task then (i)用该任务更新F (ⅱ)将DP(F)的结果发送给主进程 else if signal terminal then return end if end if end while nd for End/* PDPSlave * 3算法实现的说明 在这里我们实际上利用了集中控制的动态负载平衡技术,由主进程控制一个任务队列 首先给每个从进程发送一个任务,然后不断从这个队列中取出任务,并通过与相应的进程应 答决定是发送给它新的任务,还是结束所有进程。而从进程不断从主进程中接收信号,决定 是执行新的计算任务还是结束。 众所周知,DP算法中的拆分文字是非常重要的,特别是早期的文字拆分更显得举足轻 重,因为早期的错误会导致多搜索一个子树,工作量几乎增加一倍。例如,Gent和 Walsh 就给出了一个这样的例子,早期的文字选择错误导致了先求解一个具有350000个分枝 的不可满足的子问题。如果在初始的文字拆分中,提高DP算法的拆分文字的命中率,无疑 会达到事半功倍的效果 为了提高拆分文字的命中率,编程实现中,主进程划分任务的时候,预先找出CNF范 式中的纯文字和单元子句,这样就大大减少了需要搜索的子树数 MPⅠ源程序请参见所附光盘
5 （ii）return true else if (j > 2n ) then （i）向所有从进程发送终止信号 （ii）return false else （i）向 pi 发送下一个任务 end if end if end while End /* PDPMaster */ （2）从进程算法 procedure PDPSlave Begin for each processor pi，where 1 i k do while true do （1）从主进程接收信号 （2）if signal = task then （i）用该任务更新 F （ii）将 DP(F)的结果发送给主进程 else if signal = terminal then return end if end if end while end for End /* PDPSlave */ 3.算法实现的说明 在这里我们实际上利用了集中控制的动态负载平衡技术，由主进程控制一个任务队列。 首先给每个从进程发送一个任务，然后不断从这个队列中取出任务，并通过与相应的进程应 答决定是发送给它新的任务，还是结束所有进程。而从进程不断从主进程中接收信号，决定 是执行新的计算任务还是结束。 众所周知，DP 算法中的拆分文字是非常重要的，特别是早期的文字拆分更显得举足轻 重，因为早期的错误会导致多搜索一个子树，工作量几乎增加一倍。例如，Gent 和 Walsh 就给出了一个这样的例子，早期的文字选择错误导致了先求解一个具有 350,000,000 个分枝 的不可满足的子问题。如果在初始的文字拆分中，提高 DP 算法的拆分文字的命中率，无疑 会达到事半功倍的效果。 为了提高拆分文字的命中率，编程实现中，主进程划分任务的时候，预先找出 CNF 范 式中的纯文字和单元子句，这样就大大减少了需要搜索的子树数目。 MPI 源程序请参见所附光盘
13装箱问题 131装箱问题及其串行算法 经典的一维装箱问题( Bin Packing Problem)是指,给定n件物品的序列 Ln=,物品a1(l≤i≤m)的大小s(a1)∈(0,1,要求将这些物品装入单位容 量1的箱子B1,B2,…,Bn中,使得每个箱子中的物品大小之和不超过1,并使所使用的箱子 数目m最小。 下次适应算法( Next Fit Algorithm)是最早提出的、最简单的一个在线算法,[Joh73 首次仔细分析了下次适应算法的最坏情况性能。下次适应算法维持一个当前打开的箱子,它 依序处理输入物品,当物品到达时检查该物品能否放入这个当前打开的箱子中,若能则放入: 否则把物品放入一个新的箱子中,并把这个新箱子作为当前打开的箱子。算法描述如下: 算法16.5装箱问题的下次适应算法 输入:输入物品序列L=。 输出:使用的箱子数目m,各装入物品的箱子P= 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]+.+4/k>1且AD/+A+1]+…+A/k11≤1;其后利用倍增技术计算以A/1]为头的 链表的长度,而以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[l+A[2H+…+4[ (2) forJ to n pardo 借助F,使用二分法计算C[0j=max{4U]+4计+1]+…+4(k]≤1} nd for /*以下(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)forj= I to n pardo/*计算Bj=第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 源程序请参见所附光盘
14背包问题 141背包问题及其串行算法 0-1背包问题(-1 Knapsack Problem)的定义为:设集合A={a1,a2,-,an}代表m件物 品正整数pw分别表示第i件物品的价值与重量,那么0-1背包问题KNAP(4c)定义为, 求A的子集,使得重量之和小于背包的容量c,并使得价值和最大。也就是说求 max∑Px (16.1) subject to∑wx≤c i=1 其中x∈{0,1}。 解决0-1背包问题的最简单的方法是动态规划( Dynamic Programming)算法。我们先 看看KNAP(4,)的一个子问题KNAP(A,y),其中A={a,a2…,a},y≤c。显然,若a 并不在最优解中,那么KNAP(A1y)的解就是KNAP(A,y)的解。否则, KNAP(A-1,y-w)就是KNAP(A,y)的解。设/(y)是KNAP(4,y)的最优解,我们得 到下面的最优方法: f6( 0∥y≥0 -∞y<0 f(y)=max{1(y),f=(0y-)+p} for all0≤y≤ c and 1≤j≤m 设F(c)=(/(0,Jf(1)…,J(c)0≤j≤m,那么,动态规划算法就是依次地计 算F(c),F2(c)…,Fm(c)来求解问题。其中F(c)是KNAP(4,c)的最大价值向量。 动态规划算法是基于 Bellman递归循环,它是求解决背包问题的最直接的方法。基于 (16.2)式我们可以写出串行算法如下 算法16.70-1背包问题的串行动态规划算法 输入:各件物品的价值p,…pm,各件物品的重量w,…wm,背包的容量c 输出:能够放入背包的物品的最大总价值fa(c) procedure Knapsack(p, w, c)
8 1.4 背包问题 1.4.1 背包问题及其串行算法 0-1 背包问题（0-1 Knapsack Problem）的定义为：设集合 , , , 1 2 { } A a a a = m 代表 m 件物 品,正整数 , i r p w 分别表示第 i 件物品的价值与重量，那么 0-1 背包问题 KNAP(A,c)定义为, 求 A 的子集，使得重量之和小于背包的容量 c，并使得价值和最大。也就是说求： 1 1 max m i i i m i i i p x subject to w x c = = (16.1) 其中 {0,1} i x 。 解决 0-1 背包问题的最简单的方法是动态规划（Dynamic Programming）算法。我们先 看看 KNAP(A，c)的一个子问题 KNAP( , A y j )，其中 1 2 { , , , }, A a a a y c j j = 。显然，若 j a 并 不 在 最 优 解 中 ， 那 么 KNAP 1 ( , ) A y j− 的 解 就 是 KNAP (A , y) j 的 解 。 否 则 ， KNAP ( , ) j 1 wj A − y − 就是 KNAP (A , y) j 的解。设 f ( y) j 是 KNAP (A , y) j 的最优解，我们得 到下面的最优方法： ( ) ( ) ( ) ( ) 0 1 1 0 0 0 max , 0 1 j j j i j if y f y if y f y f y f y w p for all y c and j m − − = − = − + (16.2) 设 F (c) ( f (0), f (1), , f (c)) j j j j = 0 j m ，那么，动态规划算法就是依次地计 算 ( ), ( ), , ( ) 1 2 F c F c F c m 来求解问题。其中 F (c) j 是 KNAP( Aj ，c)的最大价值向量。 动态规划算法是基于 Bellman 递归循环，它是求解决背包问题的最直接的方法。基于 (16.2)式我们可以写出串行算法如下： 算法 16.7 0-1 背包问题的串行动态规划算法 输入：各件物品的价值 p1,…,p.m，各件物品的重量 w1,…,wm，背包的容量 c。 输出：能够放入背包的物品的最大总价值 fm(c)。 procedure Knapsack(p, w, c) Begin
(1) for i=0 to c do fo(i=0 end for (2) fori=1 to m do 1)f(0)=0 (2.2) forj= 1 to c do ifw1≤ I then ifp;+ fi10j-Wi>f-10 then f()=pi+f;(-w) f()=f() end if d for End/*Knapsack * 可以看出,串行的动态规划算法需要占用很大的空间,其本质是 Bellman递归,最坏和 最好的情况下的时间差不多相同。虽然,它在问题规模比较小时,可以很好的解决问题,但 是,随着问题规模的扩大,串行动态规划算法就显得力不从心了。 142背包问题的并行算法 现在,我们要做的是把串行程序改成并行程序。首先,我们分析一下串行程序的特点。 注意到第(2.2)步的for循环,f()只用到上一步f(y)的值,而与同一个i循环无关,这样, 可以把第(22)步直接并行化。得到下面的并行算法: 算法1680-1背包问题的并行算法 输入:各件物品的价值p,…,pm,各件物品的重量 Wm,背包的容量c 输出:能够放入背包的物品的最大总价值fm(c)。 arallelKnapsack(p, w, c) Begin (1) for each processor0≤j≤cdof6()=0 end for (2)for i=I to m pardo (2. 1)for each processor 0<j<w do f()=f1() end for (2.2) for each processor w1≤j≤cdo f(=max{1(),f=(-v)+P2} End/* ParallelKnapsack *
9 （1）for i = 0 to c do f0(i) = 0 end for （2）for i = 1 to m do （2.1）fi(0) = 0 （2.2）for j = 1 to c do if wi j then if pi + fi-1(j - wi) > fi-1(j) then fi(j) = pi + fi-1(j – wi) else fi(j) = fi-1(j) end if else fi(j) = fi-1(j) end if end for end for End /* Knapsack */ 可以看出，串行的动态规划算法需要占用很大的空间，其本质是 Bellman 递归，最坏和 最好的情况下的时间差不多相同。虽然，它在问题规模比较小时，可以很好的解决问题，但 是，随着问题规模的扩大，串行动态规划算法就显得力不从心了。 1.4.2 背包问题的并行算法 现在，我们要做的是把串行程序改成并行程序。首先，我们分析一下串行程序的特点。 注意到第（2.2）步的 for 循环，fi(j)只用到上一步 fi(y)的值，而与同一个 i 循环无关，这样， 可以把第（2.2）步直接并行化。得到下面的并行算法： 算法 16.8 0-1 背包问题的并行算法 输入：各件物品的价值 p1,…,p.m，各件物品的重量 w1,…,wm，背包的容量 c。 输出：能够放入背包的物品的最大总价值 fm(c)。 procedure ParallelKnapsack(p, w, c) Begin （1）for each processor 0 j c do 0 f j ( ) 0 = end for （2）for i = 1 to m pardo （2.1）for each processor 0 i j w do 1 ( ) ( ) i i f j f j = − end for （2.2）for each processor w j c i do 1 1 ( ) max{ ( ), ( ) } i i i i i f j f j f j w p = − + − − end for end for End /* ParallelKnapsack */
MPI源程序请参见所附光盘 1.5TSP问题 151TSP问题及其串行算法 ISP问题( Traveling-Salesman Problem)可描述为:货郎到各村去卖货,再回到出发处, 每村都要经过且仅经过一次,为其设计一种路线,使得所用旅行售货的时间最短 TSP问题至今还没有有效的算法,是当今图论上的一大难题。目前只能给出近似算法, 其中之一是所谓“改良圈算法”,即已知v2,V1是G的 Hamilton圈,用下面的算法把它 的权减小: 算法16.9TSP问题的改良圈算法 输入:任意的一个 Hamilton圈。 输出:在给定的 Hamilton圈上降低权而获得较优的 Hamilton圈。 procedure ApproxTSP Bes (1)任意选定一个 Hamiltion圈,将圈上的顶点顺次记为v1,"2…,v,, 则该圈为C={2,V2V3…,v,Vn} (2)whil存在i使得(w",""+∈C,w"/,"V∈E(G)d if w(vV)+w+ VD)<w(vvi))+(v, v+)then (2.1)C=(C-{V+1,""+)v,V+1+ (2.2)将新的圈C上的顶点顺次记为v1,2…,V end while End /*ApproxTSP * 152TSP问题的并行算法 并行算法实际上是对串行算法的改进,主要是在算法169的步骤(1)上的改进。每个从 进程检查原来的圈上不同的对边,即对进程k(1≤k≤m),检查下标索引为i,j的对边, v(v,v)+w(v1,v+)<w(v,V)+(v,+)是否成立:如果成立,则记下减小的权;在 每一轮上,选择权减小最多的对边来改进原圈,得到新的改良圈:直到不能有任何改进为止 得到的改进算法仍然是近似算法 算法16.10并行TSP算法 输入:任意不同两点之间的距离w(ij)。 输出:在这些给定点上的一个较优的回路
10 MPI 源程序请参见所附光盘。 1.5 TSP 问题 1.5.1 TSP 问题及其串行算法 TSP 问题（Traveling-Salesman Problem）可描述为：货郎到各村去卖货，再回到出发处， 每村都要经过且仅经过一次，为其设计一种路线，使得所用旅行售货的时间最短。 TSP 问题至今还没有有效的算法，是当今图论上的一大难题。目前只能给出近似算法， 其中之一是所谓“改良圈算法”，即已知 1 2 1 ... v v v v v 是 G 的 Hamilton 圈，用下面的算法把它 的权减小： 算法 16.9 TSP 问题的改良圈算法 输入：任意的一个 Hamilton 圈。 输出：在给定的 Hamilton 圈上降低权而获得较优的 Hamilton 圈。 procedure ApproxTSP Begin （1）任意选定一个 Hamiltion 圈，将圈上的顶点顺次记为 1 2 , , , v v v v ， 则该圈为 1 2 2 3 1 1 { , , , , } C v v v v v v v v = v v v − （2）while 存在 i≠j 使得( 1 1 , i i j j v v v v C + + , 1 , ( ) i j i j v v v v E G + ) do if 1 1 1 1 ( ) ( ) ( ) ( ) w v v w v v w v v w v v i j i j i i j j + + + + + + then (2.1) 1 1 1 1 ( { , }) { , } C C v v v v v v v v = − i i j j i j i j + + + + (2.2) 将新的圈 C 上的顶点顺次记为 1 2 , , , v v v v end if end while End /* ApproxTSP */ 1.5.2 TSP 问题的并行算法 并行算法实际上是对串行算法的改进，主要是在算法 16.9 的步骤(1)上的改进。每个从 进程检查原来的圈上不同的对边，即对进程 k k n (1 ) ，检查下标索引为 i，j 的对边， 1 1 1 1 ( , ) ( , ) ( , ) ( , ) w v v w v v w v v w v v i j i j i i j j + + + + + + 是否成立；如果成立，则记下减小的权；在 每一轮上，选择权减小最多的对边来改进原圈，得到新的改良圈；直到不能有任何改进为止。 得到的改进算法仍然是近似算法。 算法 16.10 并行 TSP 算法 输入：任意不同两点之间的距离 w(i,j)。 输出：在这些给定点上的一个较优的回路