您的位置:首頁 > PPT課件 > 其他PPT > 網絡流ppt

網絡流ppt下載

素材編號:
354023
素材軟件:
PowerPoint
素材格式:
.ppt
素材上傳:
yangyiner
上傳時間:
2019-05-28
素材大小:
1.43 MB
素材類別:
其他PPT
網友評分:

素材預覽

網絡流ppt

網絡流ppt免費下載是由PPT寶藏(m.cxonshanghai.com)會員yangyiner上傳推薦的其他PPT, 更新時間為2019-05-28,素材編號354023。

這是網絡流ppt,包括了最大流,最大流最小割定理,求最大流的標號法,Ford-Fulkerson方法,快速網絡流算法-Dinic算法,最小費用最大流,實例研究等內容,歡迎點擊下載。

第8次課 網絡流
主要內容
一、最大流
(一)最大流最小割定理
(二)求最大流的標號法
(三) Ford-Fulkerson方法
(四)快速網絡流算法-Dinic算法
(五)最小費用最大流
二、實例研究
問題引入
如下圖,經濟區域中城市s和城市t間的物流運輸網絡。記v1為s,v9為t,每一條有向邊(vi,vj)表示從vi到vj的運輸線,貨物經這條運輸線由vi運送到vj,線旁的數字表示線的最大運輸能力。貨物經過網絡從城市s運送到城市t。
現要求制定一個運輸方案,使從s運送到t的貨物最多。
一種運輸方案
運輸網絡的特點
(1)實際運輸量不能為負。
(2)每條有向邊上的實際運輸量不能大于該邊上的容量。
(3)除了起點s和終點t外,對于其他頂點來說,所有指向vi的線上的運輸量的和,應該等于所有從vi出發的有向邊上的運輸量的和。
一、最大流
1、最大流問題:設有向網絡G(V,A),在發點vs 有一批貨,要通過網絡上的弧運輸到收點vt 去,受運輸條件限制,每條弧aij在單位時間內通過的車輛數不能超過cij 輛,如何組織運輸才能使從vs到vt 在單位時間內通過的車輛達到最多?
例:工廠的產品由碼頭外運,vs和vt分別是工廠和碼頭,其它均為中轉站,弧上的數字為該段路每天的最大的運輸量。問從vs到vt每天運輸量最大的方案?
一、最大流
2、運輸網絡(網絡):在一個帶權的有向圖G中,若滿足以下條件:
G是弱連通的和無自環的;
每條弧(vi,vj)上的權都是非負實數C(vi,vj),簡記為ci,j,稱為弧的容量;
有向圖N中只有一個入度為0的頂點(發點),也只有一個出度為0的頂點(收點)。
  稱有向圖G為運輸網絡,仍記G=G(V,E,C)。
記f(vi,vj)是弧(vi,vj)上的流量,f是G的弧集E上的函數
注:將有向圖G的所有的有向邊替換為無向邊,所得到的無向圖是連通圖G',則有向圖是弱連通圖。
一、最大流
3、可行流:滿足下面條件的流
容量限制條件:對每弧
  (vi,vj)E,0≤f(vi,vj)≤C(vi,vj)
平衡條件:設vi為V中任一個頂點(每點的進出)
舉例
點①出發的車輛數應該與點⑦到達的車輛數相同,除①和⑦以外的各中間點,進的車輛數應該與離去的車輛數應該相同。
一、最大流
4、割:
 對于給定的網絡G=G(V,E,C),V劃分為子集U和U‘,(U,U')為U中頂點指向U'中頂點的所有弧的集合,即(U,U')={(u,v)| u U, vU'},則(U,U')為網絡G的一個分離vs、vt的割,vsU, vtU'。
例:設U={vs,v1},U'={v2,v3,vt}
   (U,U')={(vs,v2),(v1,v2),(v1,v3)}
5、割的容量:在一個割(U,U')中,所有弧的容量之和,C (U,U')
設f是一個流,則穿過割(U,U')的流用f(U,U') 表示
(一)最大流最小割定理
引理:設f是G中任一個可行流,(U,U')為G為中任一割,有v(f)≤C(U,U')
引理證明
證:對任一i,由平衡條件得:
(一)最大流最小割定理
最大流最小割定理:在任一網絡G中,從vs到vt的最大流的流量等于分離vs、vt的最小割的容量。
概念:
前向弧(向前邊):P為從vs到vt的有向路,前向弧是指弧的方向與有向路P的方向一致,前向弧的集合記P+.
反向弧(向后邊):指弧的方向與有向路P的方向相反,反向弧的集合記為P-.
      增加流量q= min{minP+(C(vi,vj)-f(vi,vj)),minP-(f (vj,vi))}
增廣路:f是G的一個可行流,P是從vs到vt的有向路,在前向弧(vi,vj)上f(vi,vj)<C(vi,vj);在反向弧(vj,vi)上,f(vi,vj)>0,稱P是vs到vt的關于f的增廣路。
找最大流的過程:尋求從vs到vt的增廣路,然后調整流量,再找新的增廣路,直到不存在增廣路為止。
增廣路算法思想
    對一條增廣路P,將可行流F改進成一個值更大的流f´,基本思想:
 (1)不屬于增廣路P的邊(vi,vj)上的流量一概不變,即f´ij= fij。
(2)增廣路P上的所有邊(vi,vj)上的流量按下述規則調整:
   在P+中的向前邊(vi,vj)上,f´ij = fij+θ;
   在P-中的向后邊(vi,vj)上,f´ij = fijθ;
增廣路示例
圖1.可行流及增廣路                                        圖2. 增廣路調整與最小割
最大流最小割定理
一個網中所有流中的最大值等于所有割中的最小容量。
可以證明以下三個條件等價:
 f是流網絡G的一個最大流;
殘留網Rf不包含增廣路徑;
G的某個割 (U,U'),滿足f(U,U') = C(U,U')
(二)求最大流的標號法
設初始可行流f 恒為0,V的頂點分為:A(未標號)、B(標號且已檢驗)、C(標號但未檢驗)
S1:進行標號
1.1)在發點vs上標上(-,+),并把vs加入C
1.2)若C非空,則取viC,在其鄰點中存在未標號vj:
1.2A)如存在有向弧(vi,vj)-向前弧,
若f(vi,vj)<C(vi,vj),在頂點vj上標上(vi+, ∆vj), 其中
                  ∆vj= min{∆vi,C(vi,vj)-f(vi,vj)},將vj加入C中
若f(vi,vj)=C(vi,vj),則vj不標號(滿流,無剩余能力了)
1.2B)如存在反向弧(vj,vi)----(vi已標記的,vj是未標記的)
若f(vj,vi)>0,則標上(vi-, ∆vj)
    ∆vj= min{△vi,f(vi,vj)}---剩余能力取上一剩余與當前流量小者
若f(vj,vi)=0,則vj不標號。
1.3)vi的鄰點處理后從C移入B,重復上述過程,直到C為空。
(二)求最大流的標號法
S2. 修改可行流
2.1)當收點vt在集合C中,得到一增廣路P,從vt的標號(y+, ∆z)上取∆z,在P的前向弧上增加∆z,在P后向弧減少∆z,得新的可行流f ',v(f ')=v(f)+∆z,接著對f '重新標號;
2.2)當收點vt沒有標上號,則G中不存在增廣路,(U,U' )是最小割(U表示所有標號的頂點,U'表示沒有標號的頂點),此時G中的可行流是最大流。
基于BFS的最大流Edmonds-Karp算法
Edmonds-Karp算法的偽代碼如下: 設隊列Q與path;  //Q存儲當前未檢查的標號點,隊首節點出隊后,
           //成為已檢查的標點;path存儲當前已標號可改進路經; repeat  path置空;  源點s標號并進入path和Q;  while  (Q非空  &&  匯點t未標號) do   移出Q的隊首頂點u;   for 每一條從u出發的弧(u,v) do
    if  (v未標號 && 弧(u,v)的流量可改進)    then v進入隊列Q和path;  end while  if (匯點已標號)  then 從匯點出發沿著path修正可改進路的流量θ; until 匯點未標號;
舉例:標號法求最大流
注:右圖紅色數字標記一個0可行流
標號法求最大流
從0流網開始
標號法求最大流
標號法求最大流
標號法求最大流
標號法求最大流
標號法求最大流
標號法求最大流
                             標號法求最大流
選擇vs或v2,以vs為例,看弧(vs, v1)。
標號法求最大流
標號法求最大流
標號法求最大流
標號法求最大流
最后的圖已無法繼續。無增廣路。
所有標號的頂點集合U={vs,v2,v4}, U'=V\U
得到最大流7.
或者選擇C中其它點開始也可以
如上圖中,在C中選擇v2,再取相鄰點v3.
跟前面得到的圖形一致了。以下略。
最小割構成
整數流定理:任一網絡中,若所有弧的容量都是整數,則必存在整數最大流
(三)Ford-Fulkerson方法求最大流
1、殘流網絡
    邊(vi,vj)E的殘流容量為cijfij,表示通過該邊能調整的最大流容量。
    給定網絡G=(V,E,C),及G的一個可行流F={ fij }。G的殘流網絡G´是通過下列方法得到的網絡G´=(V,E´,C´),設(vi,vj)E:
    當cij > fij時,G´中有對應的邊(vi,vj)E´,邊上的流量是c´ij =cij-fij;
    當fij >0時,G´中還有一條邊(vj,vi)E´,邊(vj,vi)上的流量是c´ij = fij。
(三)Ford-Fulkerson方法
2.增廣路
定義:設F是一個可行流,P是從s到t的一條路,若P滿足下列條件:
(1)在P的所有向前邊(vi,vj)上,0≤fijcij,即P+中的每一條邊是非飽和邊。
(2)在P的所有向后邊(vi,vj)上,0< fij cij,即P-中的每一條邊是非零流邊。
求最大流的一種想法
通過DFS搜索找到從源到匯的可行路徑,路徑上最小一段的容量即為該路徑的當前流量f,然后用該路徑上每一段的容量cij減去f,修正網絡容量圖。這樣通過每次DFS都可能增大流量,直到某處DFS找不到可行路徑為止。得到最大流。
該思想是否正確?
解決問題的思考
上述求解想法,一些邊“封鎖”了流量的進一步擴大。
改進思路:可以通過上述方法求得一個流量,但應允許修改,使不合理的流量能被修正。
實現思路:對DFS找到的可行路徑,構建“反向”邊,求容量是剛找到的流量f值。然后對具有反向邊的網絡尋找可行路徑,擴展流量值。
圖2:可行路徑S-B-A-T,又有流量100,總流量達200
圖3:無可行路徑
上述是基于DFS的Ford-Fulkerson方法。
增加反向邊的過程就是構建“殘流網絡”的過程。
(三)Ford-Fulkerson方法
Ford-Fulkerson算法是一種迭代算法。
首先對原始流圖建立初始0可行流圖,即網絡流大小為0。
在每次迭代中,通過尋找一條“增廣路徑”來增加流的值。增廣路徑可以看作是源點s到匯點t的一條路徑,并且沿著這條路徑可以增加更多的流。
迭代直至無法再找到增廣路徑位置,此時必然從源點到匯點的所有路徑中都至少有一條邊的滿邊(即邊的流的大小等于邊的容量大小)。
增廣路徑搜索方式
增廣路徑是殘留網中從源點s到匯點t的路徑,可以利用圖算法中的任意一種算法來獲取這條路徑,例如BFS,DFS等。所選的路徑尋找方法會直接影響算法的運行時間。
基于BFS的算法通常稱為Edmonds-Karp算法,該算法是“最短”擴充路徑,“最短”指路徑上的邊的數量來度量。已證明這種方法的復雜性為nm2。
優先隊列搜索:基于下標堆的優先隊列、PFS搜索增廣路徑   
Ford-Fulkerson方法
Ford-Fulkerson方法
Ford-Fulkerson方法
Ford-Fulkerson方法
殘流網R3中無增廣路,迭代結束,認為f3即為尋找到的最大流。
(四)快速網絡流算法-Dinic算法
前面的網絡流算法一次增廣,就需要一次BFS,比較費時。
網絡流最大流的優化算法之一,就是少做BFS。在一次增廣的過程中尋找多條增廣路。
Dinic算法基本思想:每一步利用BFS對殘流網圖進行分層,然后用DFS從前一層到下一層反復尋找求增廣路。
時間復雜度是O(n2*m) 。
Dinic 算法的基本思想
層數h[i] :定義 h[i] 為源 s到頂點 i 所經過的最小邊數。
計算殘余網絡的層次圖。求出所有頂點的 h 值,h[] 值相同的頂點屬于同一層,得到網絡的層次圖。
在層次圖上進行 BFS 增廣,直到不存在增廣路徑。這時求得的增廣路徑上頂點是分層的,即路徑上不可能存在兩個頂點屬于同一層(不存在 h[i]== h[j] (i j ))。同時,求得層次圖后,可以在層次圖上進行多次增廣。
重復 1 和 2。直到不存在增廣路徑。
分層圖示例
               圖1、原圖                                       圖2、分層初始化
圖3、分層
分層圖DFS
               圖1、原圖                                       圖2、DFS
圖3、構造殘流網,回退點v2             圖4、從v2繼續DFS
分層圖DFS
               圖1、原圖                        圖5、構造殘流網,回退點vs
圖6、對圖5重新分層                  圖7、從vs DFS,重復
分層圖DFS
               圖1、原圖                        圖8、構造殘流網,回退點vs
圖8已無法進行DFS到vt,搜索結束。
    最大流為1+3+3=7
練習-求分層圖
       圖1. 初始圖 
Dinic 算法
以原點s為根節點,將所有的節點按深度分層,直到將匯點t找到為止。如果直到最后都沒找到t,得到最大流,結束搜索,轉Step 4。
從s開始,一 層一層向下尋找t,找到之后,求出最小容量邊值作為流量f,以此為流量將各邊減去f,將各邊的反向邊加f。轉Step 3.
回溯到v點(v點是滿足離s最近,且以該點為端點的邊容量被減后是0);轉Step 2。如搜索不到t,轉Step 1。
結束。
關鍵代碼-變量說明
struct{
    int u, v, next;
    double c;
}bf[DeMax];//邊信息
int ne, head[nMax];//head[i]記錄最后一條以i為起點的邊的id,
//即以i為起點的最后一條邊為bf[head[i]],
//而bf[head[i]].next則為以i為起點的倒數第二條邊,以此類推 
int cur[nMax], ps[nMax], dep[nMax];//dep[i]記錄i點的層次 。
void addEdge(int u, int v, double c){ // dinic的加邊
     bf[ne].u = u; bf[ne].v = v; bf[ne].c = c; bf[ne].next = head[u];
 head[u] = ne ++;
     bf[ne].u = v; bf[ne].v = u; bf[ne].c = 0; bf[ne].next = head[v];
     head[v] = ne ++;
}
算法關鍵代碼-Dinic模板
double dinic(int s, int t) {  //源為s,匯點t
    double tr, res = 0;
    int i, j, k, f, r, top;
    while(1){
        memset(dep, -1, sizeof(dep));
        for(f = dep[ps[0]=s] = 0, r = 1; f != r;)
            for(i = ps[f ++], j = head[i]; j; j = bf[j].next)
                if(bf[j].c && dep[k=bf[j].v] == -1){
                    dep[k] = dep[i] + 1;
                    ps[r ++] = k;
                    if(k == t){
                        f = r; break;
                    }
                }
        if(dep[t] == -1) break;
memcpy(cur, head, sizeof(cur));
        i = s, top = 0;
        while(1){
            if(i == t){
                for(tr = inf, k = 0; k < top; k ++)
                    if(bf[ps[k]].c < tr)
                        tr = bf[ps[f=k]].c;
                for(k = 0; k < top; k ++){
                    bf[ps[k]].c -= tr;
                    bf[ps[k]^1].c += tr;
                }
                i = bf[ps[top=f]].u;
                res += tr;          // 當前的最大流,每次累積上去。   
            }
            for(j = cur[i]; cur[i]; j = cur[i] = bf[cur[i]].next)
if(bf[j].c && dep[i]+1 == dep[bf[j].v]) break;
            if(cur[i]){
                ps[top ++] = cur[i];
                i = bf[cur[i]].v;  
   // i=bf[cur[i]].v 不能寫為 bf[cur[i]].v=i
            }else{
                if(top == 0) break;
                dep[i] = -1;
                i = bf[ps[-- top]].u;
            }
        }
    }
    return res;
}
復雜性
注意到每增廣一次,層次圖中必定有一條邊會被刪除。層次圖中最多有m條邊,所以可以認為最多增廣m次。在最短路徑增廣中,我們用bfs來增廣。一次增廣的復雜度為O(n+m),其中O(m)為bfs的花費,O(n)為修改流量的花費。
所以在每一階段的復雜度為O(m*(m+n))=O(m2)。
這樣,得到找增廣路總的復雜度為O(m2n)。
(五)最小費用最大流
最小費用最大流:對于網絡G=(V,E,B,C), B={bij},C={cij},每條弧(vi,vj)上標有容量cij,及單位流量的費用bij。最小費用最大流是指一個最大流f,其總的運輸費用在所有流中最小:
實例
旅客從城市A坐飛機到城市I,經若干個機場,旅行社如何安排使運送的旅客最多又旅費最少?
屬于最小費用最大流問題:頂點表示機場,弧表示班機,弧的容量表示座位數,弧的費用表示機票價格
(五)最小費用最大流
增廣路的費用:f為可行流,P是關于f的一條增廣路,P+是P中前向弧集合,P-是P中后向弧集合,定義
(五)最小費用最大流
定理:設f是流量v(f)的最小費用流,P是關于f的所有增廣路中費用最小的增廣路,在P上作流量調整,得流f',v(f')=v(f)+q,f'是流量為v(f')的最小費用可行流。
q與最大流最小割定理定義一樣
 q= min{minP+{C(vi,vj)-f(vi,vj)},minP-{f(vj,vi)}}
最小費用最大流求解步驟
初始流:f0=0;
設fk-1是流量v(fk-1)的最小費用可行流,P是關于fk-1的最小費用增廣路,在P上對流fk-1作調整,得到流fk ,由上面定理得, fk是流量為v(fk)的最小費用可行流;
繼續在相應的費用最小的增廣路上調整,直至所得的流f*是最大流,f*是最小費用最大流。
最小費用可行流
費用最小增廣路:
T1. 給定可行流f,構造一個帶權(單價)的有向圖D(f)=(V,E',W)
(注:D(f)的頂點集是網絡G的頂點集V)
T2. 對網絡G的每條弧(vi,vj),在D(f)中存在兩條方向相反的弧(vi,vj)與(vj,vi),弧的權wij定義如下
舉例
圖6中無從vs到vt的最短路
構造結束,最大流為3
最大流最小費用為12+3 2+31+31=14
最小費用最大流程序
//求網絡最小費用最大流,鄰接陣形式
//返回最大流量,flow返回每條邊的流量,netcost返回總費用
//傳入網絡節點數n,容量mat,單位費用cost,源點source,匯點sink
#define MAXN 100
#define inf 1000000000
int min_cost_max_flow(int n,int mat[][MAXN],int cost[][MAXN],int source,int sink,int flow[][MAXN],int& netcost){
 int pre[MAXN],min[MAXN],
     d[MAXN],i,j,t,tag;
 if (source==sink) return inf;
 for (i=0;i<n;i++)
     for (j=0;j<n;flow[i][j++]=0);
 for (netcost=0;;){
     for (i=0;i<n;i++)
  pre[i]=0,min[i]=inf;
  //通過bellman_ford尋找最短路,即最小費用可改進路
  for (pre[source]=source+1,min[source]=0,d[source]=inf,tag=1;tag;)
        for (tag=t=0;t<n;t++)
if (d[t])
         for (i=0;i<n;i++)
             if (j=mat[t][i]-flow[t][i]&&min[t]+cost[t][i]<min[i])    tag=1,min[i]=min[t]+cost[t][i],pre[i]=t+1,d[i]=d[t]<j?d[t]:j;
             else if (j=flow[i][t]&&min[t]<inf&&min[t]-cost[i][t]<min[i])
   tag=1,min[i]=min[t]-cost[i][t],pre[i]=-t-1,d[i]=d[t]<j?d[t]:j;
      if (!pre[sink]) break;
      for (netcost+=min[sink]*d[i=sink];i!=source;)
          if (pre[i]>0)
               flow[pre[i]-1][i]+=d[sink],i=pre[i]-1;
          else
                flow[i][-pre[i]-1]-=d[sink],i=-pre[i]-1;
 }
 for (j=i=0;i<n;j+=flow[source][i++]);
 return j;
}
二、實例
練習題
3549 Flow Problem(入門)    [最大流]
1533 Going Home(入門題)    [費用流]
3572 Task Schedule(基礎)    [最大流]任務分配,判斷滿流
1565 方格取數(1)(基礎)    [最小割]黑白染色
2883 kebab(中等)    [最大流]判斷滿流
3605 Escape(中等,好題)
 

上一頁:通訊行業ppt 下一頁:返回列表

網絡流行語ppt:這是網絡流行語ppt,包括了定義,產生的原因,網絡流行語迅速傳播的個體心理因素,心理滿足,網絡流行語迅速傳播的社會心理因素等內容,歡迎點擊下載。

網絡流ppt

下載地址

網絡流ppt

優秀PPT

Copyright:2009-2019 pptbz.com Corporation,All Rights Reserved PPT寶藏 版權所有

免責聲明:本網站內容由用戶自行上傳,如權利人發現存在誤傳其他作品情形,請及時與本站聯系

PPT模板下載 粵ICP備13028522號

高手彩票软件下载 张掖市| 乐山市| 桂平市| 新余市| 万盛区| 庆云县| 涡阳县| 都昌县| 广德县| 北安市| 营口市| 华容县| 团风县| 呼图壁县| 台江县| 荆州市| 绍兴市| 满洲里市| 吴川市| 丰原市| 永平县| 五河县| 鄄城县| 沭阳县| 西盟| 申扎县| 肃北| 西和县| 黔东| 巩义市| 武夷山市| 玛沁县| 五河县| 株洲县| 黔西| 荣成市| 通海县| 祁门县|