算法分析報(bào)告與復(fù)雜性理論 實(shí)驗(yàn)報(bào)告材料 最大流問(wèn)題

word深 圳 大 學(xué) 實(shí) 驗(yàn) 報(bào) 告課程名稱(chēng)： 算法分析與復(fù)雜性理論 實(shí)驗(yàn)名稱(chēng)： 實(shí)驗(yàn)五 最短增益路徑法求最大流問(wèn)題 學(xué)院： 計(jì)算機(jī)與軟件學(xué)院 專(zhuān)業(yè)： 軟件工程 報(bào)告人： 文成 學(xué)號(hào)：2150230509 班級(jí)：學(xué)術(shù)型 同組人： 無(wú) 指導(dǎo)教師： 楊烜 實(shí)驗(yàn)時(shí)間：2015/11/232015/11/30 實(shí)驗(yàn)報(bào)告提交時(shí)間：2015/11/28 教務(wù)處制一 實(shí)驗(yàn)?zāi)康呐c實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)?zāi)康模海?） 掌握最短增益路徑法思想。（2） 學(xué)會(huì)最大流問(wèn)題求解方法。實(shí)驗(yàn)內(nèi)容：1. 給定下面的通信網(wǎng)絡(luò)，該網(wǎng)絡(luò)中各節(jié)點(diǎn)之間的路徑流量給定，使用最短增益路徑法求解該網(wǎng)絡(luò)的最大流量，并進(jìn)行流量分配。 2. 要求用加權(quán)矩陣輸入該網(wǎng)絡(luò)，輸出每次迭代過(guò)程中的最大流量及各路徑分配的流量。3. 如果能利用圖形界面輸出動(dòng)態(tài)求解過(guò)程（在網(wǎng)絡(luò)結(jié)構(gòu)的圖形顯示中，標(biāo)注每一次求得的增益路徑，并顯示當(dāng)前流量分配），可獲加分。算法思想提示：1.  利用二維數(shù)組Ci,j和Fi,j分別存放容量和流量。2.  構(gòu)建隊(duì)列類(lèi)Queue，該類(lèi)具有取隊(duì)首元素，加入隊(duì)尾元素等方法。3.  具體算法過(guò)程參見(jiàn)教材二實(shí)驗(yàn)步驟最大流問(wèn)題的問(wèn)題描述：如上圖。s是源點(diǎn)，t為匯點(diǎn)，每條邊上數(shù)字的含義是邊能夠允許流過(guò)的最大流量?？梢詫⑦吙闯晒艿溃?代表該管道每秒最多能通過(guò)3個(gè)單位的流量。最大流問(wèn)題即是說(shuō)，從s點(diǎn)到t點(diǎn)，最大允許流量是多少？最大流問(wèn)題的算法思想：最短增益路徑法(先標(biāo)記先掃描算法)：用兩個(gè)記號(hào)來(lái)標(biāo)記一個(gè)新的頂點(diǎn)第一個(gè)標(biāo)記指出從源點(diǎn)到被標(biāo)記頂點(diǎn)還能增加多少流量第二個(gè)標(biāo)記指出另一個(gè)頂點(diǎn)的名字，可加上+或-來(lái)表示頂點(diǎn)時(shí)通過(guò)前向邊還是后向邊訪問(wèn)到的算法及其偽代碼：Maxflow (G)/最短增量路徑算法的實(shí)現(xiàn)/輸入：網(wǎng)絡(luò)G，具有一個(gè)源點(diǎn)1和一個(gè)匯點(diǎn)n，每條邊（i，j）的容量都是正整數(shù)Uij/輸出：最大流量x/對(duì)網(wǎng)絡(luò)中的每條邊（i，j），設(shè)xij=0/把源點(diǎn)標(biāo)記為，-，再把源點(diǎn)加入到空隊(duì)列Q中While not Empty(Q) doiFront(Q);Dequeue(Q)for 從i到j(luò)的每條邊do/前向邊if j 沒(méi)有被標(biāo)記rij uij - xijif rij > 0Lj minLi,xji;用L，i-來(lái)標(biāo)記jEnqueue(Q,j)If 匯點(diǎn)被標(biāo)記了/沿著找到的增益路徑進(jìn)行增量jn/從匯點(diǎn)開(kāi)始，用第二個(gè)標(biāo)記反向移動(dòng)while j!=i/沒(méi)有到達(dá)源點(diǎn)if 頂點(diǎn)j的第二個(gè)標(biāo)記是i+xijxij+Lnelse/頂點(diǎn)j的第二個(gè)標(biāo)記是i-xjixji-Lnji；ii的第二個(gè)標(biāo)記指出的頂點(diǎn)除了源點(diǎn)，擦去所有頂點(diǎn)的標(biāo)記用源點(diǎn)對(duì)Q重新初始化return x/當(dāng)前流量是最大的思路以及代碼解釋?zhuān)海ㄈ吭创a見(jiàn)附件）先創(chuàng)建一個(gè)解決問(wèn)題的類(lèi)，命名為G。計(jì)算最大流作為這個(gè)類(lèi)中的一個(gè)方法來(lái)實(shí)現(xiàn)。利用二維數(shù)組Mapi,j和Flowi,j分別存放容量和流量。添加頭文件#include <queue>，后面需要用到隊(duì)列，需要該類(lèi)的取隊(duì)首元素，加入隊(duì)尾元素等方法。class Gpublic:G();G(int n,int start,int end);void Edge(int a,int b,int flow); /頂點(diǎn)a和頂點(diǎn)b之間的流量void Maxflow(); /計(jì)算最大流private:int N; /頂點(diǎn)個(gè)數(shù)intStart; /源點(diǎn)intEnd, /匯點(diǎn)*Map, /網(wǎng)絡(luò)容量*Flow, /通過(guò)流量*Rest, /剩余流量*Pre, /標(biāo)記流向,正為前向,負(fù)為后向*Sign, /頂點(diǎn)是否標(biāo)記,0為未標(biāo)記,1為已標(biāo)記*P; /過(guò)程變量,記錄流量bool SignN(); /標(biāo)記頂點(diǎn)int Min(int a,int b); /計(jì)算最小值void Update(); /更新網(wǎng)絡(luò);構(gòu)造函數(shù)就先定義兩個(gè)G:G() Pre=NULL; /不帶參數(shù)的構(gòu)造函數(shù)G:G(int n,int start,int end) /帶三個(gè)參數(shù)的構(gòu)造函數(shù)，頂點(diǎn)個(gè)數(shù)，源點(diǎn)和匯點(diǎn)初始化在類(lèi)G中，實(shí)現(xiàn)了void Maxflow();方法，用來(lái)計(jì)算最大流，其中標(biāo)記頂點(diǎn)的函數(shù)定義為bool SignN();bool G:SignN()/標(biāo)記頂點(diǎn)Update();/更新queue<int> que;/創(chuàng)建一個(gè)隊(duì)列的對(duì)象que.push(Start);/把源點(diǎn)放進(jìn)隊(duì)列里面SignStart=1;/將源點(diǎn)標(biāo)記PStart=1000;PreStart=-1;/標(biāo)記流向?yàn)楹笙騱hile(!que.empty()/While not Empty(Q) doint head=que.front();/不斷地取隊(duì)首為headque.pop();for(int i=1;i<=N;i+)/如果為標(biāo)記頂點(diǎn)j是由j到i的有向邊和遍歷隊(duì)列中的前面頂點(diǎn)i相連接的，而且j具有大于0的未使用容量rij=uij-xij，其中uij為邊的總?cè)萘浚瑇ij為當(dāng)前正容量，那么頂點(diǎn)j就標(biāo)記為lj，i+，其中l(wèi)j=minli，rijif(Restheadi>0 && Signi=0)/如果從head出發(fā)到其它頂點(diǎn)，有剩余流量大于0，并且沒(méi)有被標(biāo)記Pi=Min(Phead,Restheadi);Prei=head;Signi=1;if(i=End) return true;/當(dāng)掃描到匯點(diǎn)后返回que.push(i);for(i=1;i<=N;i+)/如果為標(biāo)記頂點(diǎn)j是由j到i的有向邊和遍歷隊(duì)列中的前面頂點(diǎn)i相連接的，而且j具有大于0的未使用容量xji，那么頂點(diǎn)j就標(biāo)記為lj，i-，其中l(wèi)j=minli，xjiif(Flowihead>0 && Signi=0)Pi=Min(Phead,Flowihead);Prei=-head;Signi=1;if(i=End) return true;/當(dāng)掃描到匯點(diǎn)后返回que.push(i); return false;void G:Maxflow()/計(jì)算最大流int maxflow=0;while(SignN()/迭代地去標(biāo)記頂點(diǎn)maxflow=maxflow+PEnd;for(int i=End;i>1;i=abs(Prei)if(Prei>0)/流向?yàn)榍跋騀lowPreii=FlowPreii+PEnd;if(Prei<0)/流向?yàn)楹笙騀lowiabs(Prei)=Flowiabs(Prei)-PEnd;cout<<"最大流:"<<maxflow<<endl;/輸出最大流量三實(shí)驗(yàn)結(jié)果與分析編寫(xiě)主函數(shù)，對(duì)于下圖的程序運(yùn)行結(jié)果以上就是每次迭代的過(guò)程，下面詳細(xì)解釋一下這些過(guò)程。1>2>3>6，一條4的通路。此時(shí)流量為4此時(shí)流量為6。此時(shí)流量為8。此時(shí)流量為10下一次迭代之后，流量沒(méi)有增長(zhǎng)，那么結(jié)束。最后的結(jié)果應(yīng)該是這樣的。最大流量為10由最大流最小割定理可以驗(yàn)證。該圖的最小割為(2,5) (3,6) (4,5)，最小割流量為2+4+4=10。因?yàn)榫W(wǎng)絡(luò)中的最大流量值等于它最小割的容量，可以驗(yàn)證上圖的正確性。后面，我也實(shí)現(xiàn)了用加權(quán)矩陣輸入該網(wǎng)絡(luò)，輸出每次迭代過(guò)程中的最大流量及各路徑分配的流量。四 實(shí)驗(yàn)心得在現(xiàn)實(shí)生活中，在實(shí)際的網(wǎng)絡(luò)中，網(wǎng)絡(luò)的結(jié)點(diǎn)和邊都是有容量限制的. 很多情況下我們需要知道在一個(gè)有容量限制的網(wǎng)絡(luò)中兩個(gè)指定結(jié)點(diǎn)（分別稱(chēng)為源點(diǎn)和匯點(diǎn)）之間最多能傳輸多少流量，并確定達(dá)到這個(gè)最大流量的傳輸策略. 網(wǎng)絡(luò)最大流問(wèn)題（簡(jiǎn)稱(chēng)最大流問(wèn)題）就是描述這個(gè)問(wèn)題的數(shù)學(xué)模型.求解最大流的算法有不少，在此次實(shí)驗(yàn)中，我學(xué)習(xí)到了最短增益路徑法，也明白了，最大流量值和最小割容量是相等的。本次實(shí)驗(yàn)挺有難度的，讓我明白了最大流問(wèn)題的算法，對(duì)迭代改進(jìn)算法的認(rèn)識(shí)也更加深刻了。這次實(shí)驗(yàn)結(jié)束后讓我感覺(jué)到好的算法是多么的重要，當(dāng)然合理利用算法也是不可忽視的。這次實(shí)驗(yàn)雖然花了很大精力，卻收獲累累。指導(dǎo)教師批閱意見(jiàn)：成績(jī)?cè)u(píng)定： 指導(dǎo)教師簽字： 年 月 日備注：注：1、報(bào)告內(nèi)的項(xiàng)目或內(nèi)容設(shè)置，可根據(jù)實(shí)際情況加以調(diào)整和補(bǔ)充。 2、教師批改學(xué)生實(shí)驗(yàn)報(bào)告時(shí)間應(yīng)在學(xué)生提交實(shí)驗(yàn)報(bào)告時(shí)間后10日內(nèi)。15 / 15