【正文】 } else {//結(jié)尾節(jié)點 int x。 for (x = 0 。x cityCount 。x++) { if ( == [x][0].ToString()) { break。 } } TreeNode node = new TreeNode()。 = 。//設(shè)置結(jié)尾節(jié)點 = (() + (cityA)).ToString()。 (node)。 if (isFirstAnswer == 1) { minDistance = ()。 minNode = node。 isFirstAnswer = 0。 } else if (() minDistance) { minDistance = ()。 minNode = node。 } }//if }//while }//if return minNode。} 程序的運行和正確性 程序的運行開啟客戶端，輸入服務(wù)器的IP地址，這里輸入的是localhost，也就是本地。此時，連接成功時，服務(wù)器會返回連接成功的消息和必要的數(shù)據(jù)，如客戶端編號，如圖51所示：圖51 客戶端成功連接到服務(wù)器端 連接成功后，服務(wù)器會返回連接成功的提示，在“來自服務(wù)器的消息”框中顯示出來。同時，服務(wù)器會給客戶端一個編號，方便以后消息的發(fā)送和計算等。服務(wù)器端也同時記錄下連接到服務(wù)器的客戶端的IP地址，這個IP地址就是由客戶端通過遠程對象發(fā)送到服務(wù)器上的。服務(wù)器界面如圖52所示：圖52 服務(wù)器端上有成功連接的客戶端可以開啟任意數(shù)量的客戶端，服務(wù)器都會一一記錄下這些客戶端信息。選擇任意一個客戶端作為發(fā)起并行計算的客戶端，那么其它客戶端就作為參與并行計算的機器。點擊生成數(shù)據(jù)按鈕，會隨機生成一組數(shù)據(jù)，點擊發(fā)送數(shù)據(jù)，就可以像服務(wù)器端發(fā)送數(shù)據(jù)，服務(wù)器收到數(shù)據(jù)之后，會將數(shù)據(jù)廣播發(fā)送給各個客戶端，包括發(fā)起并行計算請求的客戶端。見圖53，54和55：圖53 客戶端生成數(shù)據(jù)圖54 服務(wù)器端收到客戶端發(fā)送的數(shù)據(jù)圖55 其他客戶端接收到服務(wù)器端發(fā)送的數(shù)據(jù)點擊并行計算，客戶端開始計時，同時客戶端向服務(wù)器端發(fā)出“開始計算”的信號，服務(wù)器端收到信號后，向各個客戶端分配旅行商問題的第一級子節(jié)點，節(jié)點的分配盡量滿足“平均分配”的原則，即第一級子節(jié)點最多的客戶端和第一級子節(jié)點最少的客戶端之間子節(jié)點數(shù)量差在1以內(nèi)?？蛻舳撕头?wù)器之間具體的信號傳遞如圖56所示：圖56 客戶端和服務(wù)器之間信號傳遞過程每發(fā)送一個子節(jié)點數(shù)據(jù)之后，收到數(shù)據(jù)的客戶端會向服務(wù)器回應(yīng)一個“已收到數(shù)據(jù)”的信號，服務(wù)器在收到此信號之后才開始發(fā)送第二個子節(jié)點數(shù)據(jù)。這樣做的目的，是為了防止線程阻塞、數(shù)據(jù)發(fā)送錯亂的現(xiàn)象出現(xiàn)，這種現(xiàn)象出現(xiàn)的原因是因為，當(dāng)數(shù)據(jù)在網(wǎng)絡(luò)中傳輸?shù)乃俣冗^慢，而服務(wù)器運行發(fā)送數(shù)據(jù)的速度過快，這種情況下，就可能存在客戶端沒有接收到第一個數(shù)據(jù)，而接收到第二個數(shù)據(jù)的情況。為了防止這種情況的出現(xiàn)，需要確保數(shù)據(jù)成功發(fā)送之后再開始第二個數(shù)據(jù)的發(fā)送。但其實這樣做還是有缺點的，由于需要等待消息成功發(fā)送，客戶端成功接收到消息并成功接收到客戶端返回的“成功接收數(shù)據(jù)”的信號，因此發(fā)送數(shù)據(jù)消耗的時間就會因此變長。服務(wù)器發(fā)送完所有的第一級子節(jié)點數(shù)據(jù)之后，就向各個客戶端廣播發(fā)送“開始計算”信號，客戶端收到信號后就開始利用分支限界法對服務(wù)器發(fā)送來的數(shù)據(jù)進行計算?？蛻舳擞嬎愕玫浇Y(jié)果之后，將結(jié)果返回給服務(wù)器，服務(wù)器統(tǒng)計所有參與并行計算的客戶端返回的結(jié)果之后，求出最優(yōu)解，并將結(jié)果返回給請求并行計算的客戶端?？蛻舳耸盏阶罱K結(jié)果之后，停止計時，顯示服務(wù)器給出的最終結(jié)果和客戶端自身的計時結(jié)果。如圖57：圖57 客戶端完成并行計算并得到最終結(jié)果 程序的正確性上面是6個城市的運行情況，經(jīng)過自己手動計算，每個參與并行計算的客戶端的本地計算結(jié)果是正確的，返回給服務(wù)器，服務(wù)器統(tǒng)計之后返回給客戶端的最優(yōu)解也是正確的；同時，還測試了4個城市，5個城市的情況，系統(tǒng)計算的結(jié)果和手動計算的結(jié)果是吻合的。由于當(dāng)城市過多時，手動計算十分困難，所以就不再做過多的計算。每次系統(tǒng)計算時，手動用秒表計時，秒表計時的結(jié)果也與客戶端顯示的耗時基本相同，這樣也不在累贅的說明計時操作過程了。通過上面的測試，可以基本認(rèn)為系統(tǒng)計算的結(jié)果是正確的，系統(tǒng)的正確性是可以相信的。 測試、記錄、分析與結(jié)論 測試、記錄與分析由于城市數(shù)量的不同，參與并行計算的客戶端的數(shù)量的不同，以及網(wǎng)絡(luò)傳輸速度等其他因素的影響，計算的時間長度是不同的。因此，需要用不同的數(shù)據(jù)進行測試。作為對比，首先需要給出不同數(shù)量城市的情況下，串行計算耗時的記錄，具體數(shù)據(jù)，見表51所示：表51 串行計算耗時（1個客戶端）城市數(shù)量5678910單個客戶端最多節(jié)點數(shù)156789第一次/ms71120208860779584970第二次/ms74182214856777185219第三次/ms68115215848774584898第四次/ms80106233877779885021第五次/ms6599245840780385107平均/ms72124223856778285043表51中記錄了串行計算時，不同城市數(shù)量對耗時的影響情況，由于城市數(shù)量少時，耗時比較短，時間數(shù)值比較小，所以進行了5次測算，求平均值，以減小誤差。結(jié)果分析：（1）由表中可以很顯然的看出，串行計算的耗時隨城市數(shù)量的增加而呈指數(shù)增長趨勢，這是因為單個節(jié)點下的計算任務(wù)也成倍的增長了，這是合理的現(xiàn)象。結(jié)論：（1）串行計算耗時隨城市數(shù)量的增加而呈指數(shù)增長的趨勢；（2）串行計算不會對計算效率產(chǎn)生任何影響。參與并行計算的客戶端數(shù)量相同（這里的測試使用4個客戶端），旅行商問題中城市數(shù)量不同時，運行計算的結(jié)果如下表52所示，其中，當(dāng)城市數(shù)量到達11個的時候，計算耗時就非常久了，這里沒能記錄下4個客戶端，11個城市時的計算耗時。表52 并行計算耗時（4個客戶端）城市數(shù)量5678910單個客戶端最多節(jié)點數(shù)122223第一次/ms201214271459233229365第二次/ms193222278469235029278第三次/ms198262284437234630102平均/ms197233278455234329582表52中記錄了4臺客戶端并行計算，分別解決不同旅行商城市數(shù)量情況下的最優(yōu)解，每種城市數(shù)量各計時3次，求平均值，以盡量減小結(jié)果誤差。結(jié)果分析：（1）從表中可以很直觀的發(fā)現(xiàn)，并行計算耗時隨城市數(shù)量的增加而增加，切呈指數(shù)增長趨勢；（2）單個客戶端最多節(jié)點數(shù)目的多少對計算耗時影響不大，影響大的還是城市數(shù)量；（3）和表51對比可以發(fā)現(xiàn)，當(dāng)城市數(shù)量小于等于6時，串行計算耗時小于并行計算耗時；當(dāng)城市數(shù)量大于等于7時，串行計算耗時大于并行計算耗時。結(jié)論：（1）并行計算耗時隨城市數(shù)量的增長而增長；（2）當(dāng)城市數(shù)量到達一定數(shù)目以后，并行計算耗時隨城市數(shù)量的增長呈現(xiàn)指數(shù)增長的趨勢；（3）當(dāng)城市數(shù)量較小時，串行計算計算效率更好；反之，當(dāng)城市數(shù)量較大時，并行計算效率更高。旅行商問題中的城市數(shù)量比較多（10個城市）且城市數(shù)量相同，參與并行計算的客戶端的數(shù)量不同時，進行多次測試，測試以及結(jié)果的記錄如下頁表53所示。表53中記錄了不同的參與并行計算的客戶端的數(shù)量，每個數(shù)量的客戶端都進行了3次實驗以及結(jié)果的記錄，并根據(jù)3次記錄求平均值，以保證結(jié)果的準(zhǔn)確度。可能會造成結(jié)果不準(zhǔn)確的因素：由于計算機進行了長時間的復(fù)雜計算，CPU的使用率長時間保持很高的水平，加上天氣溫度略高，計算機進行測算時，溫度逐漸升高，計算機的計算速度會隨之下降，這可能會對結(jié)果的準(zhǔn)確性產(chǎn)生影響。表53 城市數(shù)量較多（10個）不同數(shù)量客戶端并行計算耗時客戶端數(shù)量123456789單個客戶端最多節(jié)點數(shù)953322221第一次/ms870914986632045313462695425814279373035425107第二次/ms865545163733121323812760026115283993030025855第三次/ms853955311932580317102880726393289473149825894平均/ms8634751541325823181227787261072842830717256191個節(jié)點耗時/ms95941030810860106041389413054142141535925619結(jié)果分析：（1）客戶端數(shù)量為1個時，即整個旅行商問題的計算都是由1號客戶端完成的，也就是串行單獨計算，1個客戶端要計算9個節(jié)點，耗時是最多的；（2）總體來看，隨著客戶端數(shù)量的增長，計算耗時依次遞減，但是時間減少的幅度越來越少；（3）在并行計算的過程中，由于并非所有客戶端都計算同樣多的節(jié)點，有的多，有的少，所以單個客戶端計算的最多節(jié)點的數(shù)量相同時，整體的計算耗時變化不大，反而會有少幅的增長；（4）單個客戶端計算的最多節(jié)點數(shù)減少時，計算耗時是隨之減少的；（5）隨著參與并行計算的客戶端的數(shù)量的增加，計算1個節(jié)點的耗時越來越長。結(jié)論：（1）城市數(shù)量較多事，多個客戶端參與計算比單個客戶端計算耗時更短，計算相同問題的耗時更短，即并行計算比串行計算的計算效率更高；（2）單個客戶端需要計算的最多節(jié)點數(shù)相同時，計算耗時隨參與并行計算的客戶端數(shù)量的增加會有少幅的增長；（3）單個客戶端需要計算的最多節(jié)點數(shù)的遞減時，計算耗時也隨之遞減；（4）隨著參與并行計算的客戶端數(shù)量的增長，計算單位數(shù)量節(jié)點的耗時會逐漸遞增；旅行商問題中的城市數(shù)量比較少（6個城市）且城市數(shù)量相同，參與并行計算的客戶端的數(shù)量不同時，進行多次測試，測試以及結(jié)果的記錄如下表54所示：表54 城市數(shù)量較少（6個）不同數(shù)量客戶端并行計算耗時客戶端數(shù)量12345單個客戶端最多節(jié)點數(shù)53221第一次/ms114152161214271第二次/ms102147230198377第三次/ms146120178226303第四次/ms116145174226328第五次/ms124136183222289平均/ms1201401852173141個節(jié)點耗時/ms244793109314表54中記錄了6個城市，不同客戶端數(shù)量對并行計算耗時的影響，這和多個城市（如（2）中的10個城市）相比，明顯是有區(qū)別的。其中，由于城市數(shù)量只有6個，因此每次運行計算耗時都不長，記錄的結(jié)果可能會產(chǎn)生較大的誤差。所以在上面的測試中，每種情況進行了5次測試，再求平均值，以減小測試誤差。結(jié)果分析：(1)從表中可以看出，城市數(shù)量比較小時，客戶端數(shù)量的增加反而會導(dǎo)致計算時間的增長，這和3中計算的結(jié)果相反；(2)單個節(jié)點計算耗時隨客戶端數(shù)量的增加而增加，這和3中得出的結(jié)果是一致的。結(jié)論：(1)城市數(shù)量較少時，并行計算耗時隨客戶端數(shù)量的增加而增加；(2)城市數(shù)量較多時，并行計算的計算效率更高；城市數(shù)量較少時，串行計算的計算效率更高。 結(jié)論通過從上面4個方面進行測試，并對測試結(jié)果的記錄分析，可以得到一下幾點結(jié)論：（1）城市數(shù)量較少時，串行計算比并行計算更有優(yōu)勢，因為數(shù)據(jù)的傳遞也需要一定時間；（2）城市數(shù)量較多時，并行計算比串行計算更有優(yōu)勢；（3）對于TSP問題，并行計算的耗時隨城市數(shù)量的增長而呈指數(shù)增長趨勢；（4）在城市數(shù)量較多且城市數(shù)量不變的情況下，增加參與并行計算的客戶端的數(shù)量可以減少并行計算耗時，但耗時減少的效率會隨客戶端的增加而逐漸降低且趨向于0。 小結(jié)這一章以旅行商問題為例，利用并行計算解決這個實際問題。首先介紹旅行商問題的概念，再對旅行商問題做了一定的分析，利用分支界限算法思想，并結(jié)合并行計算，設(shè)計程序來解決這一問題。最后做了一系列的測試，結(jié)果的記錄和分析，最后得出結(jié)論。第6章 結(jié)語第6章 結(jié)語 總結(jié)隨著人類科學(xué)技術(shù)的日益進步，人們需要解決很多大型的、復(fù)雜的問題，這些問題的解決通常都需要非常巨大的計算量。 Framework Remoting技術(shù)為并行計算程序的編寫提供了簡單、靈活編程手段，大大降低了編程