P=1 end if end for (3.2)C=(C-pp+,q+D)ulp"g, p+i q+ 将新的圈C上的顶点顺次记为v1v2…,v (33)将△发送给主进程 (3.4)从主进程接收最优改良对应的处理器编号m (3.5) ifk=0 then accomplished=true else ifk=m then 向其它所有从进程发送改良圈 else 从从进程m接收改良圈C end if end while End /* ParallelTspslave * MPI源程序请参见所附光盘。 16小结 本章主要讨论了八皇后、SAT、装箱、背包和TSP等经典组和优化问题的并行算法及其 MPI编程实现。对这些问题读者如欲进一步学习可参考文献[、[2]、[3]、[4和[5 参考文献 ]朱洪,陈増武,段振华,周克成编著.算法设计和分析.上海科学技术文献出版社, 2]. Davis M, Putnam H. A Computing Procedure for Quantification Theory. J. of the ACM, 1960 [3]. 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 [4].陈国良,吴明,顾钧搜索背包问题的并行分支界限算法.计算机研究与发展,2001.6, 38(6:741~745 S].万颖瑜,周智,陈国良,顾钧 Sizescale:求解旅行商问题(ISP)的新算法.计算机研究与 发展,2002.10,39(10)1294130212 p i = q j = end if end if end for （3.2） 1 1 1 1 ( { , }) { , } C C v v v v v v v v = −  p p q q p q p q + + + + ， 将新的圈 C 上的顶点顺次记为 1 2 , , , v v v v （3.3）将 wk 发送给主进程 （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 源程序请参见所附光盘。 1.6 小结 本章主要讨论了八皇后、SAT、装箱、背包和 TSP 等经典组和优化问题的并行算法及其 MPI 编程实现。对这些问题读者如欲进一步学习可参考文献[1]、[2]、[3]、[4]和[5]。 参考文献 [1]. 朱洪, 陈增武, 段振华, 周克成 编著. 算法设计和分析. 上海科学技术文献出版社, 1989 [2]. Davis M, Putnam H. A Computing Procedure for Quantification Theory. J. of the ACM, 1960, 7: 201~215 [3]. 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 [4]. 陈国良, 吴明, 顾钧. 搜索背包问题的并行分支界限算法. 计算机研究与发展, 2001.6, 38(6):741~745 [5]. 万颖瑜, 周智, 陈国良, 顾钧. Sizescale:求解旅行商问题(TSP)的新算法. 计算机研究与 发展, 2002.10, 39(10):1294~1302