【導(dǎo)讀】解決通常都需要非常巨大的計(jì)算量。的編寫提供了簡(jiǎn)單、靈活編程手段，大大降低了編程難度。術(shù)實(shí)現(xiàn)并行運(yùn)算，提高計(jì)算能力，具有重要意義。網(wǎng)絡(luò)環(huán)境下并行計(jì)算程序的基本編程方法。同時(shí)，通過串行計(jì)算和并行計(jì)算的時(shí)間和性能。這里主要是使用VS20xx軟件中的.NETRemoting技術(shù)實(shí)現(xiàn)客戶端和服務(wù)器的通信，并聯(lián)合多臺(tái)客戶端服務(wù)器，利用分支限界法并行計(jì)算解決旅行商問題。

　　

【正文】 發(fā)事件 public void TriggerAtServer(string msg) { if (SubscribeAtClient != null) SubscribeAtClient(msg)。 } //獲取委托列表 計(jì)算機(jī)信息工程學(xué)院畢業(yè)設(shè)計(jì)論文 16 public Delegate[] GetServerEventList() { return ()。 } } 服務(wù)器端 確定使用的信道 .NET Remoting 提供了三種預(yù)定義的信道： TCP、 HTTP、 IPC，他們各有自己的特點(diǎn)，根據(jù)自己需要進(jìn)行選擇。對(duì)于每個(gè)信道，都有一些可以配置的信息。 注冊(cè)信道 注冊(cè)信道就是把已經(jīng)創(chuàng)建的信道，使用 ChannelServices 類的 RegisterChannel方法來“向信道服務(wù)注冊(cè)信道”。 //信道端口 IDictionary idic = new Dictionarystring, int()。 idic[port] = 8080。 //注冊(cè)信道 TcpChannel tcpchannel = new TcpChannel(idic, clientProvider, serverProvider)。 (tcpchannel, false)。 注冊(cè)遠(yuǎn)程對(duì)象 服務(wù)器端打算發(fā)布一個(gè)可以被客戶端調(diào)用的遠(yuǎn)程對(duì)象，那它必須以某種方式“告訴”系統(tǒng)：我這里有一個(gè)這樣的服務(wù)可供你使用。這里的“告訴”的過程，就是注冊(cè)遠(yuǎn)程對(duì)象。 CityObject marshal_city_obj。 NetRmtObject marshal_obj。 //服務(wù)器獲取遠(yuǎn)程對(duì)象 marshal_obj = new NetRmtObject()。//傳輸 string 類型變量的對(duì)象 ObjRef objRef = (marshal_obj, url)。 marshal_city_obj = new CityObject()。//傳輸 DataTable 類型變量的對(duì)象 ObjRef cityObjRef = (marshal_city_obj, url1)。 注銷信道 在程序關(guān)閉時(shí)，或者清理資源時(shí)，要關(guān)閉調(diào)已經(jīng) 注冊(cè)的信道，這樣好讓出服務(wù)所使用的計(jì)算機(jī)端口，方法就是調(diào)用 即可實(shí)現(xiàn)。 客戶端 第 4 章 .NET Remoting 框架的構(gòu)建 17 創(chuàng)建、注冊(cè)信道 客戶端的信道注冊(cè)，跟服務(wù)器端的注冊(cè)基本相同，差別在于它不必指定端口，和服務(wù)器端對(duì)應(yīng)的，則使用 TcpClientChannel、 HttpClientChannel 類等，當(dāng)然也可以使用TcpChannel、 HttpChannel 類來注冊(cè)。 在創(chuàng)建了信道后，也是使用 ChannelServices 類的 RegisterChannel 方法來完成信道的注冊(cè)。 //信道端口 IDictionary idic = new Dictionarystring, int()。 idic[port] = 0。 //注冊(cè)信道 TcpChannel tcpchannel = new TcpChannel(idic, clientProvider, serverProvider)。 (tcpchannel, false)。 客戶端的端口號(hào)不能與服務(wù)器一致，否則將出現(xiàn) 通常每個(gè)套接字地址 (協(xié)議 /網(wǎng)絡(luò)地址 /端口 )只允許使用一次 的異常，將其設(shè)置為 0，則客戶端自動(dòng)選擇可用的端口。 發(fā)現(xiàn) URL 客戶端要激活服務(wù)器上的遠(yuǎn)程對(duì)象，也就是說要獲得一個(gè)遠(yuǎn)程對(duì)象的本地代理，則必須首先獲得遠(yuǎn)程對(duì)象的 URL。該 URL 和 Web 瀏覽器的 URL 具有一樣的含義，具有如下的格式： 這里的協(xié)議，也就是信道的格式，如 tcp、 、 ipc。不過，由于 IPC 機(jī)制只能 使用在單個(gè)機(jī)器上，因此，不需要使用服務(wù)器地址。 創(chuàng)建對(duì)象與獲取遠(yuǎn)程對(duì)象代理 創(chuàng)建對(duì)象，也就是在客戶端激活服務(wù)器上的對(duì)象，并獲得這個(gè)遠(yuǎn)程對(duì)象的一個(gè)本地代理（透明代理）。 在客戶端創(chuàng)建遠(yuǎn)程對(duì)象，有兩種方法，一種是使用 new 方法來創(chuàng)建，另外一種方法則是使用激活類的 Activator 的創(chuàng)建方法。 //獲取代理 try { obj = (NetRmtObject)(typeof(NetRmtObject), t + + :8080/url)。 city_obj = (CityObject)(typeof(CityObject), + + :8080/url1)。 計(jì)算機(jī)信息工程學(xué)院畢業(yè)設(shè)計(jì)論文 18 if (obj == null || city_obj == null) { (連接失敗 !!)。 return。 } } catch (Exception ex) { ()。 } 注銷信道 客戶端的信道注銷和服務(wù)器端是一樣的，這里就不再做過多說明。 事件調(diào)用 服務(wù)器注冊(cè)客戶端事件 服務(wù)器注冊(cè)客戶端事件，相對(duì)客戶端注冊(cè)服務(wù)器事件來說，是比較簡(jiǎn)單的。因?yàn)椋蛻舳嗽谡{(diào)用服務(wù)器上的遠(yuǎn)程對(duì)象時(shí)，代 碼都在服務(wù)器上執(zhí)行，服務(wù)器很容易截獲這一事件，從而進(jìn)行自己的處理。 具體的實(shí)現(xiàn)思路是，在遠(yuǎn)程對(duì)象中定義一個(gè)事件，然后在某方法內(nèi)部，調(diào)用該事件的處理函數(shù)，這樣，在客戶端調(diào)用該方法時(shí)，就觸發(fā)了事件。 //服務(wù)器綁定客戶端觸發(fā)的事件 += new MyDelegate(marshal_obj_SubscribeAtServer)。 客戶端注冊(cè)服務(wù)器事件 客戶端注冊(cè)服務(wù)器上的事件，是個(gè)畢竟復(fù)雜的過程。 剛開始的時(shí)候，以為和服務(wù)器注冊(cè)客戶端事件是 一樣的，但是實(shí)踐的時(shí)候發(fā)生錯(cuò)誤，再仔細(xì)思考一下，發(fā)現(xiàn)客戶端注冊(cè)服務(wù)器事件和服務(wù)器端注冊(cè)客戶端事件是完全不同的。 在服務(wù)器注冊(cè)客戶端事件時(shí)，只要客戶端激活了遠(yuǎn)程對(duì)象，就可以發(fā)送消息，而只要服務(wù)器訂閱了此事件，就可以處理客戶端的消息了。 在激活遠(yuǎn)程對(duì)象前，服務(wù)所做必須做的是“注冊(cè)”該遠(yuǎn)程對(duì)象類以給客戶端提供服務(wù)，然后由客戶端決定何時(shí)來創(chuàng)建一個(gè)遠(yuǎn)程對(duì)象，也就是說，服務(wù)器端沒有顯式的創(chuàng)建過遠(yuǎn)程對(duì)象，這樣，既然服務(wù)器端沒有顯式的對(duì)象，那么又如何來顯式的操作之以傳遞消息呢？ 客戶端的使用的遠(yuǎn)程對(duì)象只是一個(gè)代理，和服務(wù)器 上的遠(yuǎn)程對(duì)象處于完全不同的應(yīng)用程序域，或者說，服務(wù)器上的對(duì)象和客戶端的對(duì)象是具有相似性但完全不同的兩個(gè)“物體”，因此，在服務(wù)器端，或者是在客戶端對(duì)各自對(duì)象所做的操作，是不會(huì)互相影響的。這同樣也說明了在服務(wù)器端注冊(cè)對(duì)象后顯式創(chuàng)建一個(gè)對(duì)象的思路也并不可行。 第 4 章 .NET Remoting 框架的構(gòu)建 19 客戶端要訂閱服務(wù)器事件，那么事件處理程序向?qū)ο蟮淖?cè)動(dòng)作，也就應(yīng)該在客戶端完成，而服務(wù)器端還需逐個(gè)調(diào)用各個(gè)客戶端注冊(cè)的處理程序，這就要求客戶端和服務(wù)器端所操作的對(duì)象是“同一個(gè)”。 這樣，為了實(shí)現(xiàn)客戶端注冊(cè)客戶端事件，必須讓遠(yuǎn)程對(duì)象具有的特征也就很明顯了：客戶 端得到的遠(yuǎn)程對(duì)象實(shí)際上是服務(wù)器上對(duì)象的代理。也就是說：客戶端獲取的那個(gè)代理對(duì)象，用它來訂閱服務(wù)器的事件是訂閱不到的。服務(wù)器端觸發(fā)事件是遠(yuǎn)程對(duì)象里的事件，遠(yuǎn)程對(duì)象想要被客戶端訪問就必須被序列化，原因就在于事件是基于委托的，而 . 的委托一般是不能被序列化的。 查閱資料 ,這就需要換一種方式注冊(cè)信道 ,在注冊(cè)信道的時(shí)候強(qiáng)制設(shè)置可序列化級(jí)別為 所有類型 ，這樣就可以將事件序列化。如下所示： //設(shè)置反序列化級(jí)別 BinaryServerFormatterSinkProvider serverProvider = new BinaryServerFormatterSinkProvider()。 BinaryClientFormatterSinkProvider clientProvider = new BinaryClientFormatterSinkProvider()。 = 。//支持所有類型的反序列化，級(jí)別很高 同時(shí)創(chuàng)建新的 SwapObject 類，部分代碼如下所示： public class SwapObject : MarshalByRefObject { public event MyDelegate SwapSubscribeAtClient。//在服務(wù)器觸發(fā) ,在客戶端訂閱的事件 //服務(wù)器觸發(fā)事件 public void TriggerAtServerSwapEvent(string msg) { if (SwapSubscribeAtClient != null) SwapSubscribeAtClient(msg)。 } //無限生命周期 public override object InitializeLifetimeService() { return null。 } } } 客戶端在注冊(cè)服務(wù)器事件的時(shí)候， //訂閱服務(wù)器事件 SwapObject swap = new SwapObject()。 計(jì)算機(jī)信息工程學(xué)院畢業(yè)設(shè)計(jì)論文 20 += new MyDelegate()。 += new MyDelegate(obj_SubscribeAtClient)。 小結(jié) 這一章是對(duì) .NET Remoting技術(shù)框架構(gòu)建中各個(gè)重點(diǎn)模塊的描述。對(duì)需要?jiǎng)?chuàng)建的對(duì)象、事件，遠(yuǎn)程對(duì)象類進(jìn)行了說明，同時(shí)還給出了服務(wù)器端、客戶端信道從創(chuàng)建到注銷的流程介紹，并使用部分示例代碼來進(jìn)行說明。 第 5 章 解決實(shí)際問題 21 第 5 章 解決實(shí)際問題 ．旅行商問題簡(jiǎn)介 “旅行商問題”常被稱為“ 旅行推銷員問題 ”，是指一名推銷員要拜訪多個(gè)地點(diǎn)時(shí)，如何找到在拜訪每個(gè)地點(diǎn)一次后再回到起點(diǎn)的最短路徑。規(guī)則雖然簡(jiǎn)單，但在地點(diǎn)數(shù)目增多后求解卻極為復(fù)雜。以 42 個(gè)地點(diǎn)為例，如果要列舉所有路徑后再確定最佳行程，那么總路徑數(shù)量之大，幾乎難以計(jì)算出來。多年來全球數(shù)學(xué)家絞盡腦汁，試圖找到一個(gè)高效的算法 TSP 問題在物流中 的描述是對(duì)應(yīng)一個(gè)物流配送公司，欲將 n個(gè)客戶的訂貨沿最短路線全部送到。如何確定最短路線。 TSP 問題最簡(jiǎn)單的求解方法是 枚舉法 。它的解是多維的、多局部極值的、趨于無窮大的復(fù)雜解的空間，搜索空間是 n個(gè)點(diǎn)的所有排列的集合，大小為（ n1）！?？梢孕蜗蟮匕呀饪臻g 看成是一個(gè)無窮大的丘陵地帶，各山峰或山谷的高度即是問題的極值。求解 TSP，則是在此不能窮盡的丘陵地帶中攀登以達(dá)到山頂或谷底的過程。 ．旅行商問題研究歷史 旅行商問題字面上的理解是：有一個(gè)推銷員，要到 n個(gè)城市推銷商品，他要找出一個(gè)包含所有 n 個(gè)城市的具有最短路程的環(huán)路。 TSP 的歷史很久，最早的描述是 1759 年歐拉研究的騎士周游問題，即對(duì)于 國(guó)際象棋棋盤中的 64 個(gè)方格 ，走訪 64個(gè)方格一次且僅一次，并且最終返回到起始點(diǎn)。 TSP 由 美國(guó) RAND 公司于 1948 年引入，該公司的聲譽(yù)以及線性規(guī)劃這一新方法的出現(xiàn)使得 TSP 成為一個(gè)知名且流行的問題。 ．旅行商問題問題分析 旅行商問題要從圖 G的所有周游路線中求取最小成本的周游路線，而從初始點(diǎn)出發(fā)的周游路線一共有 (n1)!條，即等于除初始結(jié)點(diǎn)外的 n1 個(gè)結(jié)點(diǎn)的排列數(shù)，因此旅行商問題是一個(gè) 排列 問題。排列問題比子集合的選擇問題通常要難于求解得多，這是因?yàn)?n 個(gè)物體有 n!種排列，只有 n個(gè)子集合 (n!O( ))。通過枚舉 (n1)!條周游路線，從中找出一條具有最小成本的周游路線的 算法 ，其計(jì)算時(shí)間顯然為 O(n!)。 本系統(tǒng)采用 FIFO 分支限界法。 如前所 述， 分支 限界法是在生成當(dāng)前 E結(jié)點(diǎn)全部?jī)鹤又笤偕善渌罱Y(jié)點(diǎn)的兒子，且用限界函數(shù)幫助避免生成不包含答案結(jié)點(diǎn)子樹的 狀態(tài)空間 的檢索方法。在總的原則下，根據(jù)對(duì)狀態(tài)空間樹中結(jié)點(diǎn)檢索的次序的不同又將分支限界設(shè)計(jì)策路分為數(shù)種不同的檢索方法。在求解旅行商 問題時(shí)，程序中采用 FIFO 檢索（ First In First Out），它的活結(jié)點(diǎn)表采用一張先進(jìn)先出表（即隊(duì)列）。可以看出， 分支限界法 在兩個(gè)方面加速了算法的搜索速度，一是選擇要擴(kuò)展的節(jié)點(diǎn)時(shí)，總是選擇選擇一個(gè)最小成本的結(jié)點(diǎn)，盡可能早的進(jìn)入最計(jì)算機(jī)信息工程學(xué)院畢業(yè)設(shè)計(jì)論文 22 有可能成為最優(yōu)解的分支；二是擴(kuò)展節(jié)點(diǎn)的過程中，舍棄導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的子結(jié)點(diǎn)。 分支限界法常以廣度優(yōu)先或以最 小耗費(fèi)（最大效益）優(yōu)先的方式搜索問題的解空間樹。 在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)?；罱Y(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中。 此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過程。這個(gè)過程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為