并行计算-实验指导-实验04 组合优化new

《并行计算-实验指导-实验04 组合优化new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验4组合优化1.1八皇后问题11.1八皇后问题及其串行算法11.2八皇后问题的并行算法22.2SAT问题42.1SAT问题及其串行算法42.2SAT问题的并行算法53.3装箱问题73.1装箱问题及其串行算法73.2装箱问题的并行算法84.4背包问题104.1背包问题及其串行算法104.2背包问题的并行算法125.4TSP问题125.1TSP问题及其串行算法125.2TSP问题的并行算法136.小结157.参考文献168.附录八皇后问题并行算法的MPI源程序16组合优化问题在实践中有着广泛的应用，同时也是计算机科学中的重要研究课题。本章对于八皇后问题、SAT问题、装箱

2、问题、背包问题及TSP问题等五个经典的组合优化问题，给出其定义、串行算法描述、并行算法描述以及并行算法的MPI源程序。1.1八皇后问题1.1八皇后问题及其串行算法所谓八皇后问题（EightQueensProblem），是在8*8格的棋盘上，放置8个皇后。要求每行每列放一个皇后,而且每一条对角线和每一条反对角线上最多只能有一个皇后，即对同时放置在棋盘的任意两个皇后和，不允许或者的情况出现。20八皇后问题的串行解法为如下的递归算法：算法16.1八皇后问题的串行递归算法/*从chessboard的第row行开始放置皇后*/procedurePlaceQueens(chess

3、board,row)Beginifrow>8thenOutputResult(chessboard)/*结束递归并输出结果*/elseforcol=1to8do/*判断是否有列、对角线或反对角线冲突*/（1）no_collision=true（2）i=1（3）whileno_collisionandi

4、/*在当前位置放置一个皇后*/（4.2）go(step+1,place)/*递归地从下一行开始放置皇后*/endifendforendifEnd/*PlaceQueens*/1.2八皇后问题的并行算法该算法是将八皇后所有可能的解置于相应的棋盘上，主进程负责生成初始化的棋盘，并将该棋盘发送到某个空闲的从进程，由该从进程求出该棋盘上满足初始化条件的所有的解。这里，我们假定主进程只初始化棋盘的前两列，即在棋盘的前两列分别放上2个皇后，这样就可以产生8*8=64个棋盘。算法16.2八皇后问题的并行算法20（1）主进程算法procedureEightQueensMasterBe

5、gin（1）active_slaves=n（2）whileactive_slaves>0do（2.1）从某个从进程i接收信号signal（2.2）ifsignal=Accomplishedthen从从进程i接收并记录解endif（2.3）ifhas_more_boardsthen(ⅰ)向从进程i发送NewTask信号(ⅱ)向从进程i发送一个新棋盘else(ⅰ)向从进程i发送Terminate信号(ⅱ)active_slaves=active_slaves-1endifendwhileEnd/*EightQueensMaster*/（2）从进程算法procedureEi

6、ghtQueenSlaveBegin（1）向主进程发送Ready信号（2）finished=false（3）whilenotfinisheddo（3.1）从主进程接收信号signal（3.2）ifsignal=NewTaskthen(ⅰ)从主进程接收新棋盘(ⅱ)if新棋盘合法then在新棋盘的基础上找出所有合法的解，并将解发送给主进程endifelse/*signal=Terminate*/finished=trueendif20endwhileEnd/*EightQueenSlave*/MPI源程序请参见章末附录。1.2SAT问题2.1SAT问题及其串行算法1.SA

7、T问题描述所谓可满足性问题（SatisfiabilityProblem）即SAT问题，其定义为：对于一个命题逻辑公式，是否存在对其变元的一个真值赋值公式使之成立。这个问题在许多领域都有着非常重要的意义，而且对其快速求解算法的研究成为计算机科学的核心课题之一。例如在机器定理证明领域，某命题是否是一个相容的公理集合的推论，这个问题归结为该命题的反命题与该公理集合一起是否是不可满足的。特别是1971年Cook首次证明了SAT是NP-完全的，从而大量的计算问题都可以归结到SAT。正是由于SAT重要的理论和应用地位，众多学者对它进行了广泛而深入的研究。由命题逻