計算機(jī)算法設(shè)計與分析--第8章線性規(guī)劃與網(wǎng)絡(luò)流-資料下載頁
2025-10-07 14:35本頁面
【正文】 滿足條件 的中間頂點(diǎn) v稱為 活頂點(diǎn) 。 ? 量 稱為頂點(diǎn) v的存流。 ? 對網(wǎng)絡(luò) G上的一個預(yù)流，如果存在活頂點(diǎn)，則說明該預(yù)流不是可行流。 ? 預(yù)流推進(jìn)算法就是要選擇活頂點(diǎn)，并通過把一定的流量推進(jìn)到它的鄰點(diǎn)，盡可能地將當(dāng)前活頂點(diǎn)處正的存流減少為 0，直至網(wǎng)絡(luò)中不再有活頂點(diǎn)，從而使預(yù)流成為可行流。 ?? ?? ? EvwEwv vwf lo wwvf lo w ),(),( ),(),(?? ?? ? EvwEwv vwf lo wwvf lo w ),(),( ),(),(?? ?? ? EwvEvw wvf lo wvwf lo w ),(),( ),(),(2021年 11月 12日 48 預(yù)流推進(jìn)算法 ? 如果當(dāng)前活頂點(diǎn)有多個鄰點(diǎn)，那么首先推進(jìn)到哪個鄰點(diǎn)呢 ? ? 由于算法最后的目的是盡可能將流推進(jìn)到匯點(diǎn) t，因此算法應(yīng)尋求把流量推進(jìn)到它的鄰點(diǎn)中距頂點(diǎn) t最近的頂點(diǎn)。 ? 預(yù)流推進(jìn)算法中用一個高度函數(shù) h來確定推流邊。 ? 一般的預(yù)流推進(jìn)算法并未給出如何選擇活頂點(diǎn)和可推流邊。 ? 不同的選擇策略導(dǎo)致不同的預(yù)流推進(jìn)算法。 ? 在基于頂點(diǎn)的預(yù)流推進(jìn)算法中，選定一個活頂點(diǎn)后，算法沿該活頂點(diǎn)的所有推流邊進(jìn)行推流運(yùn)算，直至無可推流邊或該頂點(diǎn)的存流變成 0時為止。 2021年 11月 12日 49 一般網(wǎng)絡(luò)的最大流問題 ? 一般網(wǎng)絡(luò)可能有多個源點(diǎn)和多個匯點(diǎn)。將多源點(diǎn)多匯點(diǎn)網(wǎng)絡(luò)的最大流問題轉(zhuǎn)化為等價的單源單網(wǎng)絡(luò)的最大流問題的方法： ? 在原網(wǎng)絡(luò)的基礎(chǔ)上，增加一個虛源 s和一個虛匯 t。如果原網(wǎng)絡(luò)有 p個源 s1,s2,… ,sp和 q個匯 t1,t2,… ,tq，則在原網(wǎng)絡(luò)中增加 p條以 s為起點(diǎn)以 s1,s2,… ,sp為終點(diǎn)的邊，并增加 q條以 t1,t2,… ,tq為起點(diǎn)以 t為終點(diǎn)的邊，新增各邊的容量分別定義為頂點(diǎn) s1,s2,… ,sp的流出量和頂點(diǎn) t1,t2,… ,tq的流入量。 ? 新網(wǎng)絡(luò)的最大流對應(yīng)于原網(wǎng)絡(luò)的最大流。 2021年 11月 12日 50 ?二分圖的最大匹配問題 ?設(shè) G=(V,E)是一個無向圖。如果頂點(diǎn)集合 V可分割為兩個互不相交的子集 X和 Y，并且圖中每條邊（ i , j）所關(guān)聯(lián)的兩個頂點(diǎn) i和 j分屬于這兩個不同的頂點(diǎn)集，則稱圖 G為一個二分圖。 ?圖匹配問題描述：設(shè) G=(V,E)是一個圖。如果 M E，且 M中任何兩條邊都不與同一個頂點(diǎn)相關(guān)聯(lián)，則稱 M是 G的一個匹配。 G的邊數(shù)最多的匹配稱為G的最大匹配。 ?二分圖的最大匹配問題就是在已知圖 G是一個二分圖的前提下，求 G的最大匹配。 2021年 11月 12日 51 ? 二分圖的最大匹配問題規(guī)約到最大流問題： 設(shè) G是二分圖，它的頂點(diǎn)被分成兩個集合 X和 Y。如下構(gòu)造一個流網(wǎng)絡(luò) F，使得 F中的一個最大流可以直接轉(zhuǎn)換為 G中的一個最大匹配。 （ 1）首先把 G中的所有頂點(diǎn)包含在 F中，再增加一個新的源點(diǎn) s和一個新的匯點(diǎn) t。 （ 2）把 G中的每一條邊添加到 F中，但是使得邊的方向從 X中的頂點(diǎn)指向 Y中的頂點(diǎn)。 （ 3）接下來，從 s向 X中的每一個頂點(diǎn)都增加一條有向邊，從 Y的每一個頂點(diǎn)都向 t增加一條有向邊。 （ 4）臵 F中所有邊的容量都為 1。 求網(wǎng)絡(luò) F的最大流。在從 X指向 Y的邊集中，流量為 1的邊對應(yīng)于二分圖中的匹配邊。最大流值對應(yīng)于二分圖 G的最大匹配邊數(shù)。 2021年 11月 12日 52 提綱 一、線性規(guī)劃問題和單純形算法 二、最大網(wǎng)絡(luò)流問題 三、最小費(fèi)用流問題 2021年 11月 12日 53 問題描述 ?網(wǎng)絡(luò)流的費(fèi)用 ?對于網(wǎng)絡(luò)的每一條邊 (v,w) ，定義一個單位流量費(fèi)用cost(v,w)。對于網(wǎng)絡(luò)中一個給定的流 flow，其費(fèi)用定義為： ?最小費(fèi)用流問題：在所有最大流中找出具有最小代價的最大流。 ????Ewvwvf l o wwvtf l o wt),(),(),(c o s)(c o s2021年 11月 12日 54 消圈算法 ?基本思想：首先找到網(wǎng)絡(luò)中的一個最大流，然后通過消去負(fù)費(fèi)用圈使費(fèi)用降低。 ?增大回路（圈）： 一條關(guān)于 f的增大回路是一個頂點(diǎn)為 v0,v1,… vk=v0的有向回路 p，滿足路 p上所有邊的剩余容量大于 0。 ?增大回路中剩余容量的定義與殘流網(wǎng)絡(luò)中剩余容量的定義一致；其上代價或費(fèi)用定義為 p中前向邊上的費(fèi)用之和減去 p中后向邊上的費(fèi)用之和，用 w(p)表示。 2021年 11月 12日 55 消圈算法 ?因為增大回路 p是一個回路，所以可以把增大回路上的流添加到一個現(xiàn)有流中，而不會改變它的流值。 ?最小費(fèi)用流問題的最優(yōu)性條件： 網(wǎng)絡(luò) G的最大流 flow是 G的一個最小費(fèi)用流的充分且必要條件是 flow所相應(yīng)的殘流網(wǎng)絡(luò)中沒有負(fù)費(fèi)用圈。 2021年 11月 12日 56 消圈算法 ?求最小費(fèi)用流的消圈算法步驟： 步驟 0：首先利用某種最大流算法找出一個最大流； 步驟 1：接下來，確定流 flow是否允許一條負(fù)費(fèi)用的增大回路，即判定殘流網(wǎng)絡(luò)中是否存在負(fù)費(fèi)用圈。如果不存在負(fù)費(fèi)用圈，則計算結(jié)束，已經(jīng)找到最小費(fèi)用流。否則，轉(zhuǎn)步驟 2； 步驟 2：沿找到的負(fù)費(fèi)用圈增流，并轉(zhuǎn)步驟 1。 2021年 11月 12日 57 最小費(fèi)用路算法 ?最小費(fèi)用路算法類似于求最大流的增廣路算法的思想。 ?基本思想是，從一個空流開始，不斷在殘流網(wǎng)絡(luò)中尋找從源 s到匯 t的最小費(fèi)用路，然后沿最小費(fèi)用路增流，通過一系列增流過程構(gòu)造出一個最大流，即為最小費(fèi)用流。 ?殘流網(wǎng)絡(luò)中從源 s到匯 t的最小費(fèi)用路是殘流網(wǎng)絡(luò)中從 s到 t的以費(fèi)用為權(quán)的最短路。 2021年 11月 12日 58 最小費(fèi)用路算法 ?殘流網(wǎng)絡(luò)中邊的費(fèi)用定義為： ?當(dāng)殘流網(wǎng)絡(luò)中邊 (v,w)是向前邊時，其費(fèi)用為cost(v,w)； ?當(dāng) (v,w)是向后邊時，其費(fèi)用為 cost(w,v)。 ?????????PwvvwtPwvwvtwvwt),(),(c o s),(),(c o s),(2021年 11月 12日 59 最小費(fèi)用路算法 ?求最小費(fèi)用流的最小費(fèi)用路算法步驟： 步驟 0： 初始可行 0流。 步驟 1： 如果不存在最小費(fèi)用路，則計算結(jié)束，已經(jīng)找到最小費(fèi)用流； 否則用最短路算法在殘流網(wǎng)絡(luò)中找從 s到 t的最小費(fèi)用可增廣路，轉(zhuǎn)步驟 2。 步驟 2： 沿找到的最小費(fèi)用可增廣路增流，并轉(zhuǎn)步驟 1。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1