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

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

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