1. 問(wèn)題1：網(wǎng)絡(luò)流是模型而不是問(wèn)題近她，這是什么樣的模型？
1.1 模型
1.2 兩個(gè)約束：
- 容量約束:每條鏈路上的流量不超過(guò)容量;
- 流約束：中間節(jié)點(diǎn)不存儲(chǔ)流膳帕、從起點(diǎn)到達(dá)終點(diǎn);除了起點(diǎn)和終點(diǎn)粘捎，流入多少，流出多少危彩；
2. 最大流問(wèn)題
2.1 問(wèn)題描述
- 給定一個(gè)圖攒磨，一個(gè)起點(diǎn)，一個(gè)終點(diǎn)汤徽，找到一條從起點(diǎn)到終點(diǎn)的路徑娩缰，使得流的大小最大；
2.2 Ford-Fulkerson 算法
2.2.1 核心過(guò)程
- 找到一條路徑：從起點(diǎn)出發(fā)谒府，向前走拼坎，直到到達(dá)終點(diǎn)；
- 構(gòu)建 residual graph：根據(jù)最新找到的最大流完疫，更新 residual graph泰鸡，構(gòu)建反向路徑；
- 重復(fù)上述過(guò)程趋惨，直到無(wú)法找到一條可行路徑鸟顺；
2.2.2 算法分析
- 為什么輸出為最大流：一旦算法停止，節(jié)點(diǎn)被分為兩個(gè)集合器虾，也就是一個(gè)集合的割集讯嫂，算法停止的時(shí)候就是最小割的解，而最大流的上界和最小割的下界碰到一起就是最優(yōu)解兆沙；
3. 為什么這個(gè)算法是正確的欧芽，這是不是多項(xiàng)式算法？
問(wèn)題的正確性證明：對(duì)偶問(wèn)題 - “最小割集”
3.2關(guān)于復(fù)雜性的討論葛圃；
- 什么條件下千扔，循環(huán)會(huì)結(jié)束憎妙？答：節(jié)點(diǎn)被分為兩個(gè)集合；
- 每次循環(huán)向 “終點(diǎn)” 逼近多少曲楚？答：至少前進(jìn)一個(gè)整數(shù)厘唾；
- 終點(diǎn)有多遠(yuǎn)該如何理解？
- 算法是否為多項(xiàng)式取決于什么龙誊？
4. 癥結(jié)在哪里抚垃？如何克服？
- 癥結(jié)：每次增加的流的大小很刑舜蟆鹤树；
- 克服：每次選擇一個(gè)足夠的增量（不大于容量總和），循環(huán)找逊朽，直到找不到了罕伯；找不到了，則將增量除以2叽讳；
我的問(wèn)題：為什么是最小割追他？
問(wèn)題：最大流是一個(gè)P問(wèn)題，而不是一個(gè)NPC問(wèn)題绽榛；為什么湿酸？
問(wèn)題6：正確性沒有問(wèn)題，為什么灭美？如何能肯定效率改進(jìn)了推溃？
將外層循環(huán)，稱為 scaling phase届腐。
加入可以知道：
- 外循環(huán)次數(shù)：
-scaling phase 個(gè)數(shù)的上限（即用到的不同
- 內(nèi)循環(huán)的次數(shù)：任一phase 中執(zhí)行augment次數(shù)犁苏；
問(wèn)題7. 為什么知道最優(yōu)解多遠(yuǎn)最關(guān)鍵硬萍？
換句話說(shuō)：網(wǎng)絡(luò)中的最大流值不大于 v(f)+m
證明方法：最小割的最大值，不超過(guò)v(f)+m围详。
問(wèn)題8：這仍然不是傳統(tǒng)圖意義上的多項(xiàng)式算法朴乖。試圖實(shí)現(xiàn) “那種” 意義上多項(xiàng)式算法的思想完全不同于augment的思想。你能理解關(guān)鍵的差異嗎助赞？
- Prim：過(guò)程中間結(jié)果始終滿足 “可行解”的要求买羞，但未必滿足 “最小” 要求，在過(guò)程中不斷 “修正” 目標(biāo)值雹食，一旦找到 “終點(diǎn)”畜普，即最小可行解。
- Kruskal：過(guò)程中間結(jié)果不具備 “可行解”特征群叶，卻體現(xiàn) “最小” 的要求吃挑，一旦構(gòu)成可行解钝荡，即為最優(yōu)解。
