4 组合优化 组合优化问题在实践中有着广泛的应用，同时也是计算机科学中的重要研究课题。本章对于八皇后问题、SAT问题、装箱问题、背包问题及TSP问题等五个经典的组合优化问题，给出其定义、串行算法描述、并行算法描述以及并行算法的MPI源程序。 八皇后问题 八皇后问题及其串行算法 所谓八皇后问题（Eight Queens Problem），是在8*8格的棋盘上，放置8个皇后。要求每行每列放一个皇后,而且每一条对角线和每一条反对角线上最多只能有一个皇后，即对同时放置在棋盘的任意两个皇后和，不允许或者的情况出现。 八皇后问题的串行解法为如下的递归算法： 算法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 */ 八皇后问题的并行算法 该算法是将八皇后所有可能的解置于相应的棋盘上，主进程负责生成初始化的棋盘，并将该棋盘发送到某个空闲的从进程，由该从进程求出该棋盘上满足初始化条件的所有的解。这里，我们假定主进程只初始化棋盘的前两列，即在棋盘的前两列分别放上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源程序请参见章末附录。 SAT问题 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) 选择一个未赋值的文字l (6) /* 拆分 */ if DP(F [l/1]) = Yes then return Yes else return DP(F [l/0]) end if End /* DP */ 可以看出，DP算法是对回溯算法的精化，其中应用了我们在前面提到的化简策略单元子句规则和纯文字规则。前面已经介绍过，这些策略并不能在数量级上降低算法的时间复杂度，但实验证明这些策略的应用可以极大的改善平均性能。其实，上面介绍的策略都可以应用于SAT的求解，而且已经有了这方面的工作。 SAT问题的并行算法 1.并行化思路 通过我们在前面对串行DP算法的介绍可以看出，实际上DP算法仍然是利用深度优先方法对可能的解空间做深度优先搜索，这样我们仍然可以把这个解空间看成一棵二叉树。而它与回溯搜索算法的区别仅仅在于它利用了SAT的一些性质巧妙的找到了一些仅有一种赋值可能的文字，这样就有效地减少了搜索开销。同时在搜索一棵子树时，对某个文字的赋值可能导致新的单元子句的产生，这样，从平均意义上考虑，对这一性质的反复利用可以极大地加快搜索速度。容易知道，对于寻找单元子句和纯文字的工作是在多项式时间内完成的，因此我们可以由主进程预先把CNF的所有单元子句和纯文字找出来，对它们分别赋上可能使CNF得到满足的值，并按照某种策略选取n个文字对他们预先赋值，共得到2n组解。然后把这些信息分别发送给各个从进程进行计算，并收集运算结果。这样既避免了各个从进程重复寻找单元子句和纯文字，又有可能通过对选出的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）向所有从进程发送终止信号 （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  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源程序请参见所附光盘。 装箱问题 装箱问题及其串行算法 经典的一维装箱问题(Bin Packing Problem)是指，给定件物品的序列，物品的大小，要求将这些物品装入单位容量1的箱子中，使得每个箱子中的物品大小之和不超过1，并使所使用的箱子数目最小。 下次适应算法（Next Fit Algorithm）是最早提出的、最简单的一个在线算法，[Joh73]首次仔细分析了下次适应算法的最坏情况性能。下次适应算法维持一个当前打开的箱子，它依序处理输入物品，当物品到达时检查该物品能否放入这个当前打开的箱子中，若能则放入；否则把物品放入一个新的箱子中，并把这个新箱子作为当前打开的箱子。算法描述如下： 算法16.5 装箱问题的下次适应算法 输入：输入物品序列。 输出：使用的箱子数目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 */ 装箱问题的并行算法 算法16.5使用一遍扫描物品序列来实现，本身具有固有的顺序性，其时间复杂度为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)为头的链表的长度即是下次适应算法所使用的箱子数目。接下来利用在上一步骤中产生的中间数据反向建立一棵二叉树，使该二叉树的叶节点恰好是下次适应算法在各箱子中放入的第一个物品的序号；最后，根据各箱子中放入的第一个物品的序号，使用二分法确定各物品所放入的箱子的序号。 算法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 / 2h 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源程序请参见所附光盘。 背包问题 背包问题及其串行算法 0-1背包问题（0-1 Knapsack Problem）的定义为：设集合代表m件物品,正整数分别表示第件物品的价值与重量，那么0-1背包问题KNAP(A,c)定义为,求A的子集，使得重量之和小于背包的容量c，并使得价值和最大。也就是说求：  (16.1) 其中。 解决0-1背包问题的最简单的方法是动态规划（Dynamic Programming）算法。我们先看看KNAP(A，c)的一个子问题KNAP()，其中。显然，若并不在最优解中，那么KNAP的解就是KNAP的解。否则，KNAP就是KNAP的解。设是KNAP的最优解，我们得到下面的最优方法：  (16.2) 设 ，那么，动态规划算法就是依次地计算来求解问题。其中是KNAP(，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 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递归，最坏和最好的情况下的时间差不多相同。虽然，它在问题规模比较小时，可以很好的解决问题，但是，随着问题规模的扩大，串行动态规划算法就显得力不从心了。 背包问题的并行算法 现在，我们要做的是把串行程序改成并行程序。首先，我们分析一下串行程序的特点。注意到第（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  do  end for （2）for i = 1 to m pardo （2.1）for each processor  do  end for （2.2）for each processor  do  end for end for End /* ParallelKnapsack */ MPI源程序请参见所附光盘。 TSP问题 TSP问题及其串行算法 TSP问题（Traveling-Salesman Problem）可描述为：货郎到各村去卖货，再回到出发处，每村都要经过且仅经过一次，为其设计一种路线，使得所用旅行售货的时间最短。 TSP问题至今还没有有效的算法，是当今图论上的一大难题。目前只能给出近似算法，其中之一是所谓“改良圈算法”，即已知是G的Hamilton圈，用下面的算法把它的权减小： 算法16.9 TSP问题的改良圈算法 输入：任意的一个Hamilton圈。 输出：在给定的Hamilton圈上降低权而获得较优的Hamilton圈。 procedure ApproxTSP Begin （1）任意选定一个Hamiltion圈，将圈上的顶点顺次记为， 则该圈为 （2）while 存在i≠j使得(, ) do if  then (2.1)  (2.2) 将新的圈上的顶点顺次记为 end if end while End /* ApproxTSP */ TSP问题的并行算法 并行算法实际上是对串行算法的改进，主要是在算法16.9的步骤(1)上的改进。每个从进程检查原来的圈上不同的对边，即对进程，检查下标索引为i，j的对边，是否成立；如果成立，则记下减小的权；在每一轮上，选择权减小最多的对边来改进原圈，得到新的改良圈；直到不能有任何改进为止。得到的改进算法仍然是近似算法。 算法16.10 并行TSP算法 输入：任意不同两点之间的距离w(i,j)。 输出：在这些给定点上的一个较优的回路。 （1）主进程算法 procedure ParallelApproxTSPMaster(w) Begin （1）任意选定一个Hamilton圈，将圈上的顶点顺次记为， 则该圈为 （2）将C发送给每个从进程 （3）while true do （3.1）从每个从进程接收 （3.2）， 并记录最小的所对应的处理器编号，记为m （3.3）if then /*没有任何改进*/ 向所有从进程发送终止信号 return C else 将m发送到各处理器 end if end while End /* PrallelApproxTSPMaster */ （2）从进程算法 procedure ParallelApproxTSPSlave Begin /* 设当前从进程的编号为 */ （1）从主进程接收Hamilton圈，将圈上的顶点顺次记为， 则该圈为 （2）accomplished = false （3）while not accomplished do （3.1）for all 且 do if (i + j) mod n = k then  if temp >  then    end if end if end for （3.2）， 将新的圈上的顶点顺次记为 （3.3）将发送给主进程 （3.4）从主进程接收最优改良对应的处理器编号m （3.5）if k = 0 then accomplished = true else if k = m then 向其它所有从进程发送改良圈C else 从从进程m接收改良圈 C end if end if end while End /* ParallelTSPSlave */ MPI源程序请参见所附光盘。 小结 本章主要讨论了八皇后、SAT、装箱、背包和TSP等经典组和优化问题的并行算法及其MPI编程实现。对这些问题读者如欲进一步学习可参考文献[1]、[2]、[3]、[4]和[5]。 参考文献 朱洪, 陈增武, 段振华, 周克成 编著. 算法设计和分析. 上海科学技术文献出版社, 1989 Davis M, Putnam H. A Computing Procedure for Quantification Theory. J. of the ACM, 1960, 7: 201~215 Gu xiaodong, Chen Guoliang, Gu Jun, Huang Liusheng, Yunjae Jung. Performance Analysis and Improvement for Some Liner on-line Bin-Packing Algorithms. J. of Combinatorial Optimization, 2002,12, 6:455~471 陈国良, 吴明, 顾钧. 搜索背包问题的并行分支界限算法. 计算机研究与发展, 2001.6, 38(6):741~745 万颖瑜, 周智, 陈国良, 顾钧. Sizescale:求解旅行商问题(TSP)的新算法. 计算机研究与发展, 2002.10, 39(10):1294~1302 附录 八皇后问题并行算法的MPI源程序 1.源程序 Pqueens.c #include <mpi.h> #include <stdio.h> #define QUEENS 8 #define MAX_SOLUTIONS 92 typedef int bool; const int true = 1; const int false = 0; enum msg_content { READY, ACCOMPLISHED, NEW_TASK, TERMINATE }; enum msg_tag { REQUEST_TAG, SEED_TAG, REPLY_TAG, NUM_SOLUTIONS_TAG, SOLUTIONS_TAG }; int solutions[MAX_SOLUTIONS][QUEENS]; int solution_count = 0; bool collides(int row1, int col1, int row2, int col2) { return (col1 == col2) || (col1 - col2 == row1 - row2) || (col1 + row1 == col2 + row2); } /* collides */ int generate_seed() { static int seed = 0; do { seed++; } while (seed <= QUEENS * QUEENS – 1 && collides(0, seed / QUEENS, 1, seed % QUEENS)); if (seed > QUEENS * QUEENS - 1) return 0; else return seed; } /* generate_seed */ void print_solutions(int count, int solutions[][QUEENS]) { int i, j, k; for (i = 0; i < count; i++) { printf("Solution %d :\n", i + 1); for (j = 0; j < QUEENS; j++) { printf("%d ", solutions[i][j]); for (k = 0; k < solutions[i][j]; k++) printf("- "); printf("* "); for (k = QUEENS - 1; k > solutions[i][j]; k--) printf("- "); printf("\n"); } printf("\n"); } } /* print_solutions */ bool is_safe(int chessboard[], int row, int col) { int i; for (i = 0; i < row; i++) { if (collides(i, chessboard[i], row, col)) return false; } /* for */ return true; } /* is_safe */ void place_queens(int chessboard[], int row) { int i, col; if (row >= QUEENS) { /* 记录当前解 */ for (i = 0; i < QUEENS; i++) { solutions[solution_count][i] = chessboard[i]; } solution_count++; } else { for (col = 0; col < QUEENS; col++) { if (is_safe(chessboard, row, col)) { /* 在当前位置放置一个 皇后 */ chessboard[row] = col; /* 递归放置下一个皇后 */ place_queens(chessboard, row + 1); } /* if */ } /* for */ } /* else */ } /* place_queens */ void sequential_eight_queens() { int chessboard[QUEENS]; solution_count = 0; place_queens(chessboard, 0); print_solutions(solution_count, solutions); } void eight_queens_master(int nodes) { MPI_Status status; int active_slaves = nodes - 1; int new_task = NEW_TASK; int terminate = TERMINATE; int reply; int child; int num_solutions; int seed; while (active_slaves) { MPI_Recv(&reply, 1, MPI_INT, MPI_ANY_SOURCE, REPLY_TAG, MPI_COMM_WORLD, &status); child = status.MPI_SOURCE; if (reply == ACCOMPLISHED) { /* 从子进程接收并记录解 */ MPI_Recv(&num_solutions, 1, MPI_INT, child, NUM_SOLUTIONS_TAG, MPI_COMM_WORLD, &status); if (num_solutions > 0) { MPI_Recv(solutions[solution_ count], QUEENS * num_solutions, MPI_INT, child, SOLUTIONS_TAG, MPI_COMM_WORLD, &status); solution_count += num_solutions; } } seed = generate_seed(); if (seed) /* 还有新的初始棋盘 */ { /* 向子进程发送一个合法的新棋盘 */ MPI_Send(&new_task, 1, MPI_INT, child, REQUEST_TAG, MPI_COMM_WORLD); MPI_Send(&seed, 1, MPI_INT, child, SEED_TAG, MPI_COMM_WORLD); } else /* 已求出所有解 */ { /* 向子进程发送终止信号 */ MPI_Send(&terminate, 1, MPI_INT, child, REQUEST_TAG, MPI_COMM_WORLD); active_slaves--; } } /* while */ print_solutions(solution_count, solutions); } /* eight_queens_master */ void eight_queens_slave(int my_rank) { MPI_Status status; int ready = READY; int accomplished = ACCOMPLISHED; bool finished = false; int request; int seed; int num_solutions = 0; int chessboard[QUEENS]; MPI_Send(&ready, 1, MPI_INT, 0, REPLY_TAG, MPI_COMM_WORLD); while (! finished) { /* 从主进程接收消息 */ MPI_Recv(&request, 1, MPI_INT, 0, REQUEST_TAG, MPI_COMM_WORLD, &status); if (request == NEW_TASK) { /* 从主进程接收初始棋盘 */ MPI_Recv(&seed, 1, MPI_INT, 0, SEED_TAG, MPI_COMM_WORLD, &status); /* 在初始棋盘基础上求解 */ chessboard[0] = seed / QUEENS; chessboard[1] = seed % QUEENS; solution_count = 0; place_queens(chessboard, 2); /* 将解发送给主进程 */ MPI_Send(&accomplished, 1, MPI_INT, 0, REPLY_TAG, MPI_COMM_WORLD); MPI_Send(&solution_count, 1, MPI_INT,0, NUM_SOLUTIONS_TAG, MPI_COMM_WORLD); if (solution_count > 0) { MPI_Send(*solutions, QUEENS * solution_count, MPI_INT, 0, SOLUTIONS_TAG, MPI_COMM_WORLD); } } else /* request == TERMINATE */ { finished = true; } } /* whlie */ } /* eight_queens_slave */ /***** main *****/ int main(int argc, char* argv[]) { int nodes, my_rank; MPI_Init(&argc, &argv); MPI_Comm_size(MPI_COMM_WORLD, &nodes); MPI_Comm_rank(MPI_COMM_WORLD, &my_rank); if (nodes == 1) { sequential_eight_queens(); } if (! my_rank) { eight_queens_master(nodes); } else { eight_queens_slave(my_rank); } MPI_Finalize(); return 0; } /* main */ 2.运行实例 编译：mpicc queen.c –o queen 运行：mpirun –np 4 queen 运行结果： Solution 1 : 0 * - - - - - - - 4 - - - - * - - - 7 - - - - - - - * 5 - - - - - * - - 2 - - * - - - - - 6 - - - - - - * - 1 - * - - - - - - 3 - - - * - - - - Solution 2 : 0 * - - - - - - - 6 - - - - - - * - 3 - - - * - - - - 5 - - - - - * - - 7 - - - - - - - * 1 - * - - - - - - 4 - - - - * - - - 2 - - * - - - - - Solution 3 : 0 * - - - - - - - 6 - - - - - - * - 4 - - - - * - - - 7 - - - - - - - * 1 - * - - - - - - 3 - - - * - - - - 5 - - - - - * - - 2 - - * - - - - - ……(略) Solution 91 : 1 - * - - - - - - 6 - - - - - - * - 2 - - * - - - - - 5 - - - - - * - - 7 - - - - - - - * 4 - - - - * - - - 0 * - - - - - - - 3 - - - * - - - - Solution 92 : 1 - * - - - - - - 6 - - - - - - * - 4 - - - - * - - - 7 - - - - - - - * 0 * - - - - - - - 3 - - - * - - - - 5 - - - - - * - - 2 - - * - - - - - 说明：若指定进程数为1，则使用串行算法sequential_eight_queens()求解。