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

《算法分析報(bào)告與復(fù)雜性理論 實(shí)驗(yàn)報(bào)告材料 最大流問題》由會員分享，可在線閱讀，更多相關(guān)《算法分析報(bào)告與復(fù)雜性理論 實(shí)驗(yàn)報(bào)告材料 最大流問題（15頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、word 深 圳 大 學(xué) 實(shí) 驗(yàn) 報(bào) 告 課程名稱： 算法分析與復(fù)雜性理論 實(shí)驗(yàn)名稱： 實(shí)驗(yàn)五 最短增益路徑法求最大流問題 學(xué)院： 計(jì)算機(jī)與軟件學(xué)院 專業(yè)： 軟件工程 報(bào)告人： 文成 學(xué)號：2150230509 班級：學(xué)術(shù)型 同組人： 無 指導(dǎo)教師： 楊烜 實(shí)驗(yàn)時

2、間：2015/11/23——2015/11/30 實(shí)驗(yàn)報(bào)告提交時間：2015/11/28 教務(wù)處制 一． 實(shí)驗(yàn)?zāi)康呐c實(shí)驗(yàn)內(nèi)容 實(shí)驗(yàn)?zāi)康模? （1）?掌握最短增益路徑法思想。 （2）?學(xué)會最大流問題求解方法。 實(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ò)，輸出每次迭代過程中的最大流量及各路徑分配的流量。 3.?如果能利用圖形界面輸出動態(tài)求解過程（在網(wǎng)絡(luò)結(jié)構(gòu)的圖形顯示中，標(biāo)注每一次求得的

3、增益路徑，并顯示當(dāng)前流量分配），可獲加分。 算法思想提示： 1.??利用二維數(shù)組C[i,j]和F[i,j]分別存放容量和流量。 2.??構(gòu)建隊(duì)列類Queue，該類具有取隊(duì)首元素，加入隊(duì)尾元素等方法。 3.??具體算法過程參見教材 二．實(shí)驗(yàn)步驟 最大流問題的問題描述： 如上圖。s是源點(diǎn)，t為匯點(diǎn)，每條邊上數(shù)字的含義是邊能夠允許流過的最大流量。可以將邊看成管道，3代表該管道每秒最多能通過3個單位的流量。最大流問題即是說，從s點(diǎn)到t點(diǎn)，最大允許流量是多少？ 最大流問題的算法思想： 最短增益路徑法(先標(biāo)記先掃描算法)： 用兩個記號來標(biāo)記一個新的頂點(diǎn) 第一個

4、標(biāo)記指出從源點(diǎn)到被標(biāo)記頂點(diǎn)還能增加多少流量 第二個標(biāo)記指出另一個頂點(diǎn)的名字，可加上+或-來表示頂點(diǎn)時通過前向邊還是后向邊訪問到的 算法及其偽代碼： Maxflow (G) //最短增量路徑算法的實(shí)現(xiàn) //輸入：網(wǎng)絡(luò)G，具有一個源點(diǎn)1和一個匯點(diǎn)n，每條邊（i，j）的容量都是正整數(shù)Uij //輸出：最大流量x //對網(wǎng)絡(luò)中的每條邊（i，j），設(shè)xij=0 //把源點(diǎn)標(biāo)記為∞，-，再把源點(diǎn)加入到空隊(duì)列Q中 While not Empty(Q) do i←Front(Q);Dequeue(Q) for 從i到j(luò)的每條邊do//前向邊 if j 沒有被標(biāo)記 rij

5、← uij - xij if rij > 0 Lj min{Li,xji};用L，i-來標(biāo)記j Enqueue(Q,j) If 匯點(diǎn)被標(biāo)記了 //沿著找到的增益路徑進(jìn)行增量 j←n//從匯點(diǎn)開始，用第二個標(biāo)記反向移動 while j!=i//沒有到達(dá)源點(diǎn) if 頂點(diǎn)j的第二個標(biāo)記是i+ xij←xij+Ln else//頂點(diǎn)j的第二個標(biāo)記是i- xji←xji-Ln j←i；i←i的第二個標(biāo)記指出的頂點(diǎn) 除了源點(diǎn)，擦去所有頂點(diǎn)的標(biāo)記 用源點(diǎn)對Q重新初始化 return x//當(dāng)前流量是最大的 思路以及代碼解釋： （全部源代碼見附件） 先創(chuàng)建一個解決問

6、題的類，命名為G。 計(jì)算最大流作為這個類中的一個方法來實(shí)現(xiàn)。 利用二維數(shù)組Map[i,j]和Flow[i,j]分別存放容量和流量。 添加頭文件#include ，后面需要用到隊(duì)列，需要該類的取隊(duì)首元素，加入隊(duì)尾元素等方法。 class G { public: 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: in

7、t N; //頂點(diǎn)個數(shù) intStart; //源點(diǎn) intEnd, //匯點(diǎn) **Map, //網(wǎng)絡(luò)容量 **Flow, //通過流量 **Rest, //剩余流量 *Pre,

8、 //標(biāo)記流向,正為前向,負(fù)為后向 *Sign, //頂點(diǎn)是否標(biāo)記,0為未標(biāo)記,1為已標(biāo)記 *P; //過程變量,記錄流量 bool SignN(); //標(biāo)記頂點(diǎn) int Min(int a,int b); //計(jì)算最小值 void Update(); //更新網(wǎng)絡(luò) }; 構(gòu)造函數(shù)就先定義兩個 G

9、::G() {Pre=NULL;} //不帶參數(shù)的構(gòu)造函數(shù) G::G(int n,int start,int end) //帶三個參數(shù)的構(gòu)造函數(shù)，頂點(diǎn)個數(shù)，源點(diǎn)和匯點(diǎn) {初始化} 在類G中，實(shí)現(xiàn)了void Maxflow();方法，用來計(jì)算最大流， 其中標(biāo)記頂點(diǎn)的函數(shù)定義為bool SignN(); bool G::SignN()//標(biāo)記頂點(diǎn) { Update();//更新 queue que;//創(chuàng)建一個隊(duì)列的對象 que.push(Start);//把源點(diǎn)放進(jìn)隊(duì)列里面 Sign[Start]=1;//將源點(diǎn)標(biāo)記

10、P[Start]=1000; Pre[Start]=-1;//標(biāo)記流向?yàn)楹笙? while(!que.empty())//While not Empty(Q) do { int head=que.front();//不斷地取隊(duì)首為head que.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è)萘?，xij為當(dāng)前正容量，那么頂點(diǎn)j就標(biāo)記為lj，i+，其中l(wèi)j=min{li，rij} if(Rest[head][i]>0

11、&& Sign[i]==0)//如果從head出發(fā)到其它頂點(diǎn)，有剩余流量大于0，并且沒有被標(biāo)記 { P[i]=Min(P[head],Rest[head][i]); Pre[i]=head; Sign[i]=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=min{li，xji} if(Flow[i][head]>0 && S

12、ign[i]==0) { P[i]=Min(P[head],Flow[i][head]); Pre[i]=-head; Sign[i]=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+P[End]; for(int i=End;i>1;i=abs(Pre[i])) { if(Pre[i

13、]>0)//流向?yàn)榍跋? { Flow[Pre[i]][i]=Flow[Pre[i]][i]+P[End]; } if(Pre[i]<0)//流向?yàn)楹笙? { Flow[i][abs(Pre[i])]=Flow[i][abs(Pre[i])]-P[End]; } } } cout<<"最大流:"<2—>3—>6，一條4的通路。此時流量為4 此時流量為6。 此時流量為8。

14、 此時流量為10 下一次迭代之后，流量沒有增長，那么結(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ò)，輸出每次迭代過程中的最大流量及各路徑分配的流量。 四． 實(shí)驗(yàn)心得 在現(xiàn)實(shí)生活中，在實(shí)際的網(wǎng)絡(luò)中，網(wǎng)絡(luò)的結(jié)點(diǎn)和邊都是有容量限制的. 很多情況下我們需要知道在一個有容量限制的網(wǎng)絡(luò)中兩個指定結(jié)點(diǎn)（分別稱為源點(diǎn)和匯點(diǎn)）之間最多能傳輸多少流量，并確定達(dá)到這個最大流

15、量的傳輸策略. 網(wǎng)絡(luò)最大流問題（簡稱最大流問題）就是描述這個問題的數(shù)學(xué)模型. 求解最大流的算法有不少，在此次實(shí)驗(yàn)中，我學(xué)習(xí)到了最短增益路徑法，也明白了，最大流量值和最小割容量是相等的。本次實(shí)驗(yàn)挺有難度的，讓我明白了最大流問題的算法，對迭代改進(jìn)算法的認(rèn)識也更加深刻了。 這次實(shí)驗(yàn)結(jié)束后讓我感覺到好的算法是多么的重要，當(dāng)然合理利用算法也是不可忽視的。這次實(shí)驗(yàn)雖然花了很大精力，卻收獲累累。 指導(dǎo)教師批閱意見： 成績評定： 指導(dǎo)教師簽字： 年 月 日 備注： 注：1、報(bào)告內(nèi)的項(xiàng)目或內(nèi)容設(shè)置，可根據(jù)實(shí)際情況加以調(diào)整和補(bǔ)充。 2、教師批改學(xué)生實(shí)驗(yàn)報(bào)告時間應(yīng)在學(xué)生提交實(shí)驗(yàn)報(bào)告時間后10日內(nèi)。 15 / 15