分支定界算法的分布并行化研究.pdf

1、分支定界算法是求解優(yōu)化問題的重要方法。雖然它有很高的計算精度，但是，高的計算時間復(fù)雜度，降低了它的實際應(yīng)用價值。本文設(shè)計實現(xiàn)的一種專用于計算分支定界算法的機(jī)群計算平臺，能減少分支定界算法的計算時間復(fù)雜度，提高分支定界算法的效率。 本論文在深入分析其它各種啟發(fā)式算法和分布式并行計算的基礎(chǔ)上，針對上述平臺，就如何減少分支定界算法的時間復(fù)雜度問題作了創(chuàng)新性和探索性研究。主要內(nèi)容為： 1.詳細(xì)研究了分支定界算法，提出并實現(xiàn)了一種

2、新的分布并行加速機(jī)制可以把計算平臺機(jī)群中的任何一臺計算機(jī)上計算出的當(dāng)前全局最佳本分值，實時地廣播給所有其它并行的計算機(jī)，作為它們的新最佳本分值，來實現(xiàn)分支節(jié)點的快速并行淘汰。 2.詳細(xì)研究了幾種主要的啟發(fā)式算法，并使用啟發(fā)式算法修改了分支定界算法，在保證計算精度的前提下，提高了分支節(jié)點的淘汰效率。 3.詳細(xì)研究了幾種并行計算算法，并通過分布并行減小了組合優(yōu)化問題的規(guī)模。 4.本文選用旅行商(TSP)問題實例作為測