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 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 */