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 源程序请参见章末附录