《算法導(dǎo)論》學(xué)習(xí)筆記-v1.0

《算法導(dǎo)論》學(xué)習(xí)筆記Version1.0 第一部分：基礎(chǔ)知識第1章：算法在計(jì)算中的作用算法即是一系列的計(jì)算步驟，用來將一個(gè)有效的輸入轉(zhuǎn)換成一個(gè)有效的輸出。計(jì)算機(jī)的有限的資源必須被有效的利用，算法就是來解決這些問題的方法。第2章：算法入門循環(huán)不變式的三個(gè)性質(zhì)：（循環(huán)不變式通常用來證明遞歸的正確性）初始化：它在循環(huán)的第一輪迭代開始之前，應(yīng)該是正確的。保持：如果在循環(huán)的某一次迭代開始之前它是正確的，那么，在下一次迭代開始之前，它也應(yīng)該保持正確。終止：當(dāng)循環(huán)結(jié)束時(shí)，不變式給了我們一個(gè)有用的性質(zhì)，它有助于表明算法是正確的。分治策略：將原問題劃分成ｎ個(gè)規(guī)模較小而結(jié)構(gòu)與原問題相似的子問題；遞歸地解決這些小問題，然后再合并其結(jié)果，就得到原問題的解。分治模式在每一層遞歸上都有三個(gè)步驟：分解(Divde)：將原問題分解成一系列子問題；解決(Conquer)：遞歸地解答各子問題。若子問題足夠小，則直接求解；合并(Combine)：將子問題的結(jié)果合并成原問題的解。第3章：函數(shù)的增長1.對幾個(gè)記號的大意：o（非漸近緊確上界）≈<；O（漸近上界）≈≤；Θ（漸近緊界）≈=；Ω（漸近下界）≈≥；ω（非漸近緊確下界）≈>;這里的<,≤,=,≥,>指的是規(guī)模上的比較，即o(g(n))的規(guī)模比g(n)小。o(g(n))={f(n):對任意正常數(shù)c，存在常數(shù)n0>0，使對所有的n≧n0，有0≦f(n)<cg(n)}O(g(n))={f(n):存在正常數(shù)c和n0，使對所有n≧n0，有0≦f(n)≦cg(n)}Θ(g(n))={f(n):存在正常數(shù)c1，c2和n0，使對所有的n≧n0，有0≦c1g(n)≦f(n)≦c2g(n)}Ω(g(n))={f(n):存在正常數(shù)c和n0，使對所有n≧n0，有0≦cg(n)≦f(n)}ω(g(n))={f(n):對任意正常數(shù)c，存在常數(shù)n0>0，使對所有的n≧n0，有0≦cg(n)<f(n)}第4章：遞歸式遞歸式是一組等式或不等式，它所描述的函數(shù)是用在更小的輸入下該函數(shù)的值來定義的。例如Merge-Sort的最壞情況運(yùn)行時(shí)間T(n)可以用以下遞歸式來表示：解遞歸式的方法主要有三種：代換法、遞歸樹方法、擴(kuò)展法、主方法。代換法(Substitutionmethod)(P38~P40)定義：先猜測某個(gè)界的存在，再用數(shù)學(xué)歸納法去證明該猜測的正確性。遞歸樹方法(Recursion-treemethod)起因：代換法有時(shí)很難得到一個(gè)正確的好的猜測值。用途：畫出一個(gè)遞歸樹是一種得到好猜測的直接方法。分析(重點(diǎn))：在遞歸樹中，每一個(gè)結(jié)點(diǎn)都代表遞歸函數(shù)調(diào)用集合中一個(gè)子問題的代價(jià)。將遞歸樹中每一層內(nèi)的代價(jià)相加得到一個(gè)每層代價(jià)的集合，再將每層的代價(jià)相加得到遞歸式所有層次的總代價(jià)?？偨Y(jié)：遞歸樹最適合用來產(chǎn)生好的猜測，然后用代換法加以驗(yàn)證。遞歸樹的方法非常直觀，總的代價(jià)就是把所有層次的代價(jià)相加起來得到。但是分析這個(gè)總代價(jià)的規(guī)模卻不是件很容易的事情，有時(shí)需要用到很多數(shù)學(xué)的知識。主方法(Mastermethod)主方法是最好用的Cookbook方法，太神奇了，可以瞬間估計(jì)出遞歸算法的時(shí)間復(fù)雜度，主方法總結(jié)了常見的情況并給出了一個(gè)公式。優(yōu)點(diǎn)：針對形如T(n)=aT(n/b)+f(n)的遞歸式缺點(diǎn)：并不能解所有形如上式的遞歸式的解。因?yàn)橹鞣椒ㄔ诘?種情況與第2種情況之間、第2種情況與第3種情況之間都存在著一條溝，所以會存在著不能適用的情況。直覺上：實(shí)際上主方法一直在比較f(n)與NLogba的規(guī)模，然后選取規(guī)模大的作為最后的遞歸式的規(guī)模。主方法：設(shè)a≥1和b≥1是常數(shù)f(n)是定義在非負(fù)整數(shù)上的一個(gè)確定的非負(fù)函數(shù)。又設(shè)T(n)也是定義在非負(fù)整數(shù)上的一個(gè)非負(fù)函數(shù)，且滿足遞歸方程T(n)=aT(n/b)+f(n)。方程T(n)=aT(n/b)+f(n)中的n/b可以是[n/b]，也可以是n/b。那么，在f(n)的三類情況下，我們有T(n)的漸近估計(jì)式：若對于某常數(shù)ε>0，有；若，則；，則若對其常數(shù)ε>0，有且對于某常數(shù)c>1和所有充分大的正整數(shù)n有af(n/b)≤cf(n)，則T(n)=θ(f(n))。 第二部分：排序和順序統(tǒng)計(jì)學(xué)第6章：堆排序1：堆排序是一個(gè)時(shí)間復(fù)雜度為O(nlgn)、原地排序算法。第7章：快速排序1：快速排序的最壞運(yùn)行時(shí)間為O(n2)，期望運(yùn)行時(shí)間為O(nlgn)，且由于O(nlgn)中隱含的常數(shù)因子很小，所以快排通常是用于排序的最佳的實(shí)用選擇（因?yàn)槠淦骄阅芊浅：茫?。第四部分：高級設(shè)計(jì)和分析技術(shù)所有的最優(yōu)化問題都可以通過窮舉法來解決，但是這在時(shí)間上是不可接受的。所有的高效算法都是為了加快速度：動態(tài)規(guī)劃：保存子問題的解，以備重復(fù)使用貪心算法：用局部最優(yōu)解來求全局最優(yōu)解第15章：動態(tài)規(guī)劃動態(tài)規(guī)劃與分治法之間的區(qū)別：分治法是指將問題分成一些獨(dú)立的子問題，遞歸的求解各子問題動態(tài)規(guī)劃適用于這些子問題不是獨(dú)立的情況，也就是各子問題包含公共子問題動態(tài)規(guī)劃算法的設(shè)計(jì)可以分為4個(gè)步驟：描述最優(yōu)解的子結(jié)構(gòu)遞歸定義最優(yōu)解的值按自底向上的方法計(jì)算最優(yōu)解的值由計(jì)算出的結(jié)果反向構(gòu)造出一個(gè)最優(yōu)解動態(tài)規(guī)劃最最最重要的就是要找出最優(yōu)解的子結(jié)構(gòu)！最優(yōu)子結(jié)構(gòu)在問題域中以兩種方式變化（在找出這兩個(gè)問題的解之后，構(gòu)造出原問題的最優(yōu)子結(jié)構(gòu)往往就不是難事了）：有多少個(gè)子問題被用在原問題的一個(gè)最優(yōu)解中在決定一個(gè)最優(yōu)解中使用哪些子問題有多少個(gè)選擇動態(tài)規(guī)劃說白了就是一個(gè)遞歸的反向展開的過程：在滿足①最優(yōu)子結(jié)構(gòu)②重疊子問題這2個(gè)條件下，通過把遞歸從下至上的進(jìn)行展開以避免重復(fù)計(jì)算子問題從而加速了最終問題的求解的過程。再次強(qiáng)調(diào)“動態(tài)規(guī)劃最關(guān)鍵的一步就是：尋找最優(yōu)子結(jié)構(gòu)”動態(tài)規(guī)劃能夠消除重復(fù)計(jì)算子問題是因?yàn)樗c普通遞歸相反，它是通過自下而上的方式來進(jìn)行求解的。正確使用動態(tài)規(guī)劃方法的2個(gè)關(guān)鍵要素：最優(yōu)子結(jié)構(gòu)和重疊子問題。如果問題可以由遞歸來解決，并且在遞歸的過程中會不斷的出現(xiàn)重復(fù)的子問題需要解決，那毫不猶豫的采用動態(tài)規(guī)劃吧！如果問題的一個(gè)最優(yōu)解中包含了子問題的最優(yōu)解，則該問題具有最優(yōu)子結(jié)構(gòu)；而當(dāng)一個(gè)問題具有最優(yōu)子結(jié)構(gòu)時(shí)，提示我們動態(tài)規(guī)劃可能會適用。剪貼技術(shù)：用來證明在問題的一個(gè)最優(yōu)解中，使用的子問題的解本身也必須是最優(yōu)的為了描述子問題空間，可以遵循這樣一條有效的經(jīng)驗(yàn)規(guī)則，就是盡量保持這個(gè)空間簡單，然后在需要時(shí)再擴(kuò)充它非正式地：一個(gè)動態(tài)規(guī)劃算法的運(yùn)行時(shí)間依賴于兩個(gè)因素的乘積：子問題的總個(gè)數(shù)和每個(gè)子問題中有多少種選擇。問題解的代價(jià)通常是子問題的代價(jià)加上選擇本身帶來的開銷。貪心算法與動態(tài)規(guī)劃有一個(gè)顯著的區(qū)別：就是在貪心算法中，是以自頂向下的方式使用最優(yōu)子結(jié)構(gòu)的。貪心算法會先做選擇，在當(dāng)時(shí)看起來是最優(yōu)的選擇，然后再求解一個(gè)結(jié)果子問題，而不是先尋找子問題的最優(yōu)解，然后再選擇。要注意：在不能應(yīng)用最優(yōu)子結(jié)構(gòu)的時(shí)間，就一定不能假設(shè)它能夠應(yīng)用。警惕使用動態(tài)規(guī)劃去解決缺乏最優(yōu)子結(jié)構(gòu)的問題！使用動態(tài)規(guī)劃時(shí)：子問題必須是相互獨(dú)立的！可以這樣理解，N個(gè)子問題域互不相干，屬于完全不同的空間。子問題必須獨(dú)立！重疊子問題：不同的子問題的數(shù)目是輸入規(guī)模的一個(gè)多項(xiàng)式。這樣，動態(tài)規(guī)劃算法才能充分利用重疊的子問題，減少計(jì)算量。即通過每個(gè)子問題只解一次，把解保存在一個(gè)需要時(shí)就可以查看的表中，而每次查表只需要常數(shù)時(shí)間。從這段描述可以看出：動態(tài)規(guī)劃與遞歸時(shí)做備忘錄的本質(zhì)是完全相同的，所以說備忘錄方法與普通的動態(tài)遞歸本質(zhì)完全相同，沒有孰優(yōu)孰劣之分，哪個(gè)方便用哪個(gè)。由計(jì)算出的結(jié)果反向構(gòu)造一個(gè)最優(yōu)解：把動態(tài)規(guī)劃或者是遞歸過程中作出的每一次選擇（記?。罕４娴氖敲看巫鞒龅倪x擇）都保存下來，在最后就一定可以通過這些保存的選擇來反向構(gòu)造出最優(yōu)解。做備忘錄的遞歸方法：這種方法是動態(tài)規(guī)劃的一個(gè)變形，它本質(zhì)上與動態(tài)規(guī)劃是一樣的，但是比動態(tài)規(guī)劃更好理解！使用普通的遞歸結(jié)構(gòu)，自上而下的解決問題。當(dāng)在遞歸算法的執(zhí)行中每一次遇到一個(gè)子問題時(shí)，就計(jì)算它的解并填入一個(gè)表中。以后每次遇到該子問題時(shí)，只要查看并返回表中先前填入的值即可。備忘錄方法與動態(tài)遞歸方法的比較：如果所有的子問題都至少要被計(jì)算一次，則一個(gè)自底向上的動態(tài)規(guī)劃算法通常比一個(gè)自頂向下的做備忘錄算法好出一個(gè)常數(shù)因子。因?yàn)閯討B(tài)規(guī)劃沒有使用遞歸的代價(jià)，只用到了循環(huán)，所以常數(shù)因子肯定比遞歸要好一些。此外，在有些問題中，還可以用動態(tài)規(guī)劃算法中的表存取模式來進(jìn)一步的減少時(shí)間和空間上的需求；或者，如果子問題中的某些子問題根本沒有必須求解，做備忘錄的方法有著只解那些肯定要求解的子問題的優(yōu)點(diǎn)。（而且這點(diǎn)是自動獲得的，那些不必要計(jì)算的子問題在備忘錄方法中會被自動的拋棄）備忘錄方法總結(jié)：由“是否所有的子問題都至少需要被計(jì)算一次”來決定使用動態(tài)規(guī)劃還是備忘錄。再次下定義：這兩種方法沒孰優(yōu)孰劣之分，因?yàn)樗鼈兊谋举|(zhì)思想是完全一樣的；消除重復(fù)子問題。動態(tài)規(guī)劃：最重要最重要的就是找到最優(yōu)子結(jié)構(gòu)。在找到最優(yōu)子結(jié)構(gòu)之后的消除重復(fù)子問題，這點(diǎn)我太容易處理了，無論是動態(tài)規(guī)劃的自底向上的遞推，還是備忘錄，或者是備忘錄的變型，都可以輕松的應(yīng)付。關(guān)鍵就是最優(yōu)子結(jié)構(gòu)。第16章：貪心算法貪心算法使所作的選擇看起來都是當(dāng)前最佳的，期望通所做的局部最優(yōu)選擇來產(chǎn)生一個(gè)全局最優(yōu)解。對算法中的每一個(gè)決策點(diǎn)，做一個(gè)當(dāng)時(shí)看起來是最佳的選擇，這種啟發(fā)式策略并不是總能產(chǎn)生最優(yōu)解的。貪心算法對大多數(shù)優(yōu)化問題能產(chǎn)生最優(yōu)解，但很多問題也不能通過這樣的局部最優(yōu)解得到全局最優(yōu)解（0-1背包）。實(shí)際上，使用貪心算法最關(guān)鍵的就是在于如何證明貪心選擇性質(zhì)以證明當(dāng)前的問題可以由貪心算法得到最優(yōu)解在活動選擇問題中，非常關(guān)鍵的一點(diǎn)先決條件就是：活動要先按照結(jié)束時(shí)間的單調(diào)遞增順序排序，這樣才能貪心的選擇第一個(gè)。從直覺上來看，這種活動選擇方法是一種“貪婪的”選擇方法，它給后面剩下的待調(diào)度任務(wù)留下了盡可能多的機(jī)會。也就是說，此處的貪心選擇使得剩下的、未調(diào)度的時(shí)間最大化可以說：動態(tài)規(guī)劃其實(shí)是“安全的貪心算法”的基礎(chǔ)。無論如何，在每一個(gè)貪心算法的下面，幾乎總是會有一個(gè)更加復(fù)雜的動態(tài)規(guī)劃解。貪心算法實(shí)現(xiàn)簡單速度快，但是證明貪心的正確性往往是很困難的，所以說安全的（能夠取得最優(yōu)解的）貪心算法下面總有一個(gè)動態(tài)規(guī)劃算法來證明其正確性。所謂安全的貪心算法就是指一定能產(chǎn)生出全局最優(yōu)解的貪心算法貪心算法的一般步驟（定義）將優(yōu)化問題轉(zhuǎn)化成這樣的一個(gè)問題，即先做出選擇（對應(yīng)于動態(tài)規(guī)劃的先解決子問題再選擇），再解決剩下的一個(gè)子問題。證明原問題總是有一個(gè)最優(yōu)解是做貪心選擇得到的，從而說明貪心選擇的安全。說明在做出貪心選擇后，剩余的子問題具有這樣的一個(gè)性質(zhì)。即如果將子問題的最優(yōu)解和我們所做的貪心選擇聯(lián)合起來，就可以得出原問題的一個(gè)最優(yōu)解。正確使用貪心算法的2個(gè)關(guān)鍵要素：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)。貪心選擇性質(zhì)：一個(gè)全局最優(yōu)解可以通過局部最優(yōu)（貪心）選擇來達(dá)到；即當(dāng)考慮做何選擇時(shí)，我們只考慮對當(dāng)前問題最佳的選擇而不考慮子問題的結(jié)果。最優(yōu)子結(jié)構(gòu)：一個(gè)問題的最優(yōu)解包含了其子問題的最優(yōu)解。要使用貪心算法就必須先證明以下兩個(gè)性質(zhì)：每一步所做的貪心選擇最終能產(chǎn)生一個(gè)全局最優(yōu)解。在證明中先考察一個(gè)全局最優(yōu)解，然后證明對該解加以修改，使其采用貪心選擇，這個(gè)選擇將原問題變?yōu)橐粋€(gè)相似的、但更小的問題。子問題的最優(yōu)解與所做的貪心選擇合并后，的確可以得到原問題的一個(gè)最優(yōu)解。貪心算法所做的當(dāng)前選擇可能要依賴于已經(jīng)做出的所有選擇，但不依賴于有待于做出的選擇或子問題的解。前綴編碼：在所有的編碼方案中，沒有一個(gè)編碼是另一個(gè)編碼的前綴。一般地，就算證明不出來貪心算法能給出最優(yōu)解，但是它一般都至少能給出次優(yōu)解。所以貪心算法在實(shí)際的應(yīng)用中是非常的普及的。原有的元素……NewItem↑在原有的元素里還要再支付一個(gè)可能移動的代價(jià)↑支付自身以后可能的移動操作的代價(jià)第六部分：圖算法第22章：圖的基本算法圖的搜索技術(shù)是圖算法領(lǐng)域的核心兩種最普通的圖的表示方法：鄰接表法（節(jié)省空間）和鄰接矩陣法（查詢高效）稀疏圖多用鄰接表法來表示；而稠密圖則用鄰接矩陣法來表示比較好。不論是有向圖還是無向圖，鄰接表法都有一個(gè)很好的特性，即它所需要的存儲空間為O(V+E)；鄰接表表示法稍作修改就能支持其它多種圖的變體，因而有著很強(qiáng)的適應(yīng)性。無向圖的鄰接矩陣A就是它的轉(zhuǎn)置矩陣：A=AT。在某些應(yīng)用中，可以只存儲鄰接矩陣的對角線及對角線以上的部分，這樣一來，圖所占用的存儲空間幾乎可以減少一半鄰接表表示和鄰接矩陣表示在漸近意義上至少是一樣有效的，但由于鄰接矩陣簡單明了，因而當(dāng)圖較小時(shí)，更多多地采用鄰接矩陣來表示。另外，如果一個(gè)圖不是加權(quán)的，采用鄰接矩陣的存儲形式還有一個(gè)優(yōu)越性：在存儲鄰接矩陣的每個(gè)元素時(shí)，可以只用一個(gè)二進(jìn)位，而不必有一個(gè)字的空間。這樣，當(dāng)采用了二進(jìn)位以及表示無向圖的技巧時(shí)，鄰接矩陣法的占用空間大的缺點(diǎn)就可以得到一定程度上的改善！廣度優(yōu)先搜索能夠得到這種意義上的最短路徑：每條邊的權(quán)值都為1，即所有的邊都具有單位權(quán)值。廣度優(yōu)先所產(chǎn)生的廣度優(yōu)先樹是每個(gè)頂點(diǎn)到s的最短距離。深度優(yōu)先搜索除了創(chuàng)建一個(gè)深度優(yōu)先森林外，深度優(yōu)先搜索同時(shí)為每個(gè)頂點(diǎn)加蓋時(shí)間戳。每個(gè)頂點(diǎn)v有兩個(gè)時(shí)間戳：當(dāng)頂點(diǎn)v第一次被發(fā)現(xiàn)時(shí)，記錄下第一個(gè)時(shí)間戳d[v]，當(dāng)結(jié)束檢查v的鄰接表時(shí)，記錄下第二個(gè)時(shí)間戳f[v]。許多基于深度優(yōu)先搜索的圖算法都用到了時(shí)間戳，它們對推算深度優(yōu)先搜索的時(shí)行情況有很大的幫助。這次重新復(fù)習(xí)深度優(yōu)先算法，得到的最大的啟示就是使用了這2個(gè)時(shí)間戳，真的是很有用很好的創(chuàng)新啊。當(dāng)記錄下這2個(gè)時(shí)間戳之后，很多東西都可以由這對時(shí)間戳來推導(dǎo)出來了（比如拓?fù)渑判?、深度遍歷的次序等）。廣度搜索通常用于從某個(gè)源頂點(diǎn)開始，尋找最短路徑距離（以及相關(guān)的先輩子圖）。深度優(yōu)先搜索通常作為另一個(gè)算法中的一個(gè)子程序。后裔區(qū)間的嵌套：在一個(gè)（有向或無向）圖G中的深度優(yōu)先森林中，頂點(diǎn)v是頂點(diǎn)u的后裔，當(dāng)且僅當(dāng)d[u]<d[v]<f[v]<d[u]，由這關(guān)系可以推導(dǎo)出大部分的與時(shí)間戳相關(guān)的性質(zhì)。邊的分類：樹邊、反向邊、正向邊、交叉邊。拓?fù)渑判颍涸诤芏鄳?yīng)用中，有向無回路圖說明事件發(fā)生的先后次序。在深度優(yōu)先遍歷的基礎(chǔ)上，對有向無回路圖進(jìn)行拓?fù)渑判蚝喼笔切〔艘货蕖８鶕?jù)遍歷所得到的時(shí)間戳f[i]逆向排序就好了。拓?fù)渑判虻捻旤c(diǎn)以與其完成時(shí)間時(shí)間相反的順序出現(xiàn)。這種新方法真是長見識啊，比我以前使用的方法好多了，這種方法在遍歷完只需要一個(gè)簡單的sort就完成了拓?fù)渑判?，時(shí)間復(fù)雜度也降低為O(V+E)。這種新的拓?fù)渑判虻姆椒ǖ睦碚摶A(chǔ)是：對于任一對不同的頂點(diǎn)u,v，如果存在一條從u->v的邊，那么u在拓?fù)渑判虻慕Y(jié)果中一定在v的前面。而又根據(jù)后裔區(qū)間嵌套的定理：如果存在u->v，那么f[v]<f[u]，所以得證根據(jù)f逆向排序得到的順序一定為拓?fù)渑判?。?qiáng)連通分支：有向圖G=(V,E)的一個(gè)強(qiáng)連通分支就是一個(gè)最大的頂點(diǎn)集合C，對于C中的每一對頂點(diǎn)u,v，都有u->v及v->u；亦即頂點(diǎn)u和v是互相可達(dá)的。Output（代碼：Output（代碼：/p/introduction-ot-algorithms-notes/）:廣度優(yōu)先遍歷：srwvtxuy深度優(yōu)先遍歷：r[1,16]s[2,13]w[3,12]t[4,11]u[5,10]x[6,9]y[7,8]v[14,15]深度優(yōu)先遍歷：r[1,16]s[2,13]w[3,12]t[4,11]u[5,10]x[6,9]y[7,8]v[14,15]拓?fù)渑判颍簊hirt[15,18]tie[16,17]watch[13,14]socks[11,12]undershorts[1,10]pants[2,9]belt[5,8]jacket[6,7]shoes[3,4]強(qiáng)連接分支a[1,16]b[2,15]e[13,14]c[3,12]g[8,11]f[9,10]d[4,7]h[5,6]aebcdgf對G進(jìn)行深度優(yōu)先遍歷得到每個(gè)頂點(diǎn)的時(shí)間戳f[x]；求得G的返回圖GT；按照f[x]的逆向順序?yàn)轫旤c(diǎn)順序?qū)T進(jìn)行深度優(yōu)先遍歷，即按照G的拓?fù)渑判虻捻樞驅(qū)T再進(jìn)行深度優(yōu)先遍歷；d)步驟c得到的各棵子樹就是原圖G的各強(qiáng)連通分支。尋找強(qiáng)連通分支的算法的時(shí)間復(fù)雜度為O(V+E)。h請按任意鍵繼續(xù)...第23章：最小生成樹Kruskal算法和Prim算法：這兩種算法中都使用普通的二叉堆就可以很容易地達(dá)到O(ElgV)的運(yùn)行時(shí)間。通過采用斐波那契堆，Prim算法的運(yùn)行時(shí)間可以減少到O(E+VlgV)，這對于稠密圖來說是個(gè)很大的改進(jìn)。貪心策略可以在最小生成樹問題中得到最優(yōu)解，事實(shí)上這里的Kruskal、Prim方法都是貪心算法。它們也都是可以被證明的一定能夠得到最優(yōu)解！在Kruskal算法中，集合A是一個(gè)森林，加入集合A中的安全邊總是圖中連接兩個(gè)不同連通分支的最小權(quán)邊；在Prim算法中，集合A僅形成單棵樹，添入集合A中的安全邊總是連接樹與一個(gè)不在樹中的頂點(diǎn)的最小權(quán)邊。為什么說Prim算法有著更好的實(shí)際效率：Prim算法在執(zhí)行的過程中，將不在樹中的所有頂點(diǎn)都放在一個(gè)基于key域的最小優(yōu)先隊(duì)列Q中；每次在選取安全邊時(shí)，只需要從Q中彈出最小key值的頂點(diǎn)即可，而不需要像Kruskal一樣為對所有的邊的權(quán)值進(jìn)行一次排序；Prim算法使用了用于快速或者最小權(quán)值邊的技巧（二叉堆、二項(xiàng)堆、斐波那契堆）來加速算法的運(yùn)行。在最樸素的選取安全邊的算法中，需要遍歷剩下的所有的邊，所需要的時(shí)間復(fù)雜度為O(EV)，而采用堆來優(yōu)化后只需要O(ElgV)，大大地改善了算法的執(zhí)行時(shí)間（堆的好處）。不過Kruskal算法實(shí)現(xiàn)簡單，所以對于一般的應(yīng)用Kruskal算法很常見。Prim算法的性能取決于優(yōu)先隊(duì)列Q是如何實(shí)現(xiàn)的，因此如果使用斐波那契堆來實(shí)現(xiàn)最小優(yōu)先隊(duì)列，就可以將Prim算法的運(yùn)行時(shí)間改進(jìn)為O(E+VlgV)。OutputOutput（代碼：/p/introduction-to-algorithms-notes/）:6-->72--8>5--6>0-->12--5>2--3>0-->73-->4Prim最小生成樹&--aa--bb--cc--ic--ff--gg--hc--dd--e請按任意鍵繼續(xù)...第24章：單源最短路徑最短路徑：一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的最短權(quán)值路徑。廣度優(yōu)先搜索算法就是一種在無權(quán)（單位權(quán)值）圖上執(zhí)行的最短路徑算法。從漸近意義上來說，解決一對頂點(diǎn)的最短路徑問題的復(fù)雜度與單源最短路徑的復(fù)雜度相同。最短路徑算法通常依賴于一種性質(zhì)，也就是一條兩頂點(diǎn)間的最短路徑包含路徑上其它的最短路徑。這里動態(tài)規(guī)劃和貪心算法的特征之一：最優(yōu)子結(jié)構(gòu)。Dijkstra算法是一個(gè)貪心算法。DIJKSTRA算法假定輸入圖中的所有邊的權(quán)值都是非負(fù)的，而floyd算法允許輸入邊存在負(fù)權(quán)邊，只要不存在從源點(diǎn)可達(dá)的負(fù)權(quán)回路。而且如果存在著負(fù)權(quán)回路，它還能檢測出來。Bellman-Ford算法非常簡單：對所有的邊進(jìn)行|v|-1遍循環(huán)，在每次循環(huán)中對每一條邊進(jìn)行松弛的操作。按頂點(diǎn)的拓?fù)漤樞驅(qū)δ臣訖?quán)有向無回路圖的邊進(jìn)行松弛后，就可以在O(V+E)時(shí)間內(nèi)計(jì)算出單源最短路徑。在一個(gè)有向無回路圖中最短路徑總是存在的，因?yàn)榧词箞D中有權(quán)值為負(fù)的邊，也不可能存在負(fù)權(quán)回路（因?yàn)樗緵]有任何回路）。Dijkstra算法是一種貪心策略的算法，它的運(yùn)行時(shí)間一般比Bellman-Ford算法要好。DIJKSTRA(G,w,s)INITIALIZE-SINGLE-SOURCE(G,s)S←?Q←V[G]whileQ≠?dou←EXTRACT-MIN(Q)S←S∪{u}foreachvertexv∈Adj[u]doRELAX(u,v,w)Dijkstra算法在每次循環(huán)中，每次僅僅提取d值最小的頂點(diǎn)u是保證這個(gè)貪心策略正確性的關(guān)鍵核心所在。因?yàn)橥ㄟ^集合S中所有的元素都已經(jīng)去試著松弛過u了，而非S中的點(diǎn)由于本身它的d值都比u要大，所以即使用它們中的任何一個(gè)去松弛u，也不可能達(dá)到比現(xiàn)在更小的d值了。因此，在每次循環(huán)中選取當(dāng)前d值最小的頂點(diǎn)加入到S集合中去一定能保證最后得到全局最優(yōu)解。很多問題都可以轉(zhuǎn)換成圖的問題，使用最短路徑的算法來加以解決的。要善于把一些看似不相干的問題轉(zhuǎn)化為圖的問題。OutputOutput（代碼：/p/introduction-to-algorithms-notes/）:Bellman-Ford最短路徑s|0t|2x|4z|-2y|7Dijkstra最短路徑s|0t|8x|9z|7y|5請按任意鍵繼續(xù)...第25章：每對頂點(diǎn)間的最短路徑Folyd-Warshall是一個(gè)動態(tài)規(guī)劃算法，運(yùn)行時(shí)間為O(V3)；Johnson算法使用了幾種算法作為其子算法，運(yùn)行時(shí)間為O(V2lgV+VE)，尤其適合對大型稀疏圖。求每對頂點(diǎn)之間的最短路徑問題很適合于動態(tài)規(guī)劃算法來求解，因?yàn)樗鼭M足“最優(yōu)子問題的結(jié)構(gòu)”和“重疊子問題”兩個(gè)特征。一個(gè)樸素的思路就是使用Lij(m)來表示從頂點(diǎn)i到頂點(diǎn)j的，中間包含至多m條路徑的最短路徑。這種思路是樸素的動態(tài)規(guī)劃思想，效率比較好，時(shí)間復(fù)雜度為O(V3lgV)，但是后面提及的兩種算法都對這個(gè)“最優(yōu)子問題的結(jié)構(gòu)”進(jìn)行了更多的優(yōu)化。Folyd-Warshall算法的運(yùn)行時(shí)間為O(V3)，它允許權(quán)值為負(fù)的邊，但是假定了不存在權(quán)值為負(fù)的回路。而且它的代碼是緊湊的，而且不包含復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，隱含的常數(shù)因子很小。因此，即便對于中等規(guī)模的輸入圖來說Folyd-Warshall算法仍然相當(dāng)?shù)膶?shí)用。Folyd-Warshall的核心在于：它改進(jìn)了“最優(yōu)子問題結(jié)構(gòu)”，使用dij(k)來表示從頂點(diǎn)i到頂點(diǎn)j、且滿足所有中間頂點(diǎn)皆屬于集合{1,2,…,k}的一條最短路徑的權(quán)值。這種限定了起始點(diǎn)的技巧大大的減少了實(shí)現(xiàn)的計(jì)算量。有向圖的傳遞閉包：G的傳遞閉包定義為圖G*=(V,E*)，其中E*={(i,j):圖G中存在著一條從i到j(luò)的路徑}。對于一個(gè)大圖，即使是只需要確定是否存在路徑可達(dá)都不是一件很容易的事件。解決此問題的整體思路與Folyd-Warshall算法一樣，只是把Folyd-Warshall算法中的min和+操作替換為相應(yīng)的OR和AND邏輯運(yùn)算來加快速度，本質(zhì)并沒有區(qū)別。Johnson算法可在O(V2lgV+VE)時(shí)間內(nèi)，求出每對頂點(diǎn)間的最短路徑。Johnson算法使用Dijkstra和Bellman-Ford算法作為其子程序。Johnson算法是一個(gè)實(shí)際上非常好的算法，它使得所有的情況（可能存在負(fù)權(quán)值和負(fù)權(quán)回路）都可以使用最好的Dijkstra算法來達(dá)到最好的運(yùn)行效率。Johnson算法在所有的邊為非負(fù)時(shí)，把每對頂點(diǎn)依次作為源點(diǎn)來執(zhí)行Dijkstra算法，就可以找到每對頂點(diǎn)間的最短路徑；利用斐波那契最小優(yōu)先隊(duì)列，該算法的運(yùn)行時(shí)間為O(V2lgV+VE)。因此也可以總結(jié)出：對于確定無負(fù)權(quán)值的圖，直接循環(huán)調(diào)用Dijkstra算法就是求每對頂點(diǎn)間最短路徑的最佳算法。Johnson算法使用了重賦權(quán)技術(shù)，對每一條邊的權(quán)值w賦予一個(gè)新的權(quán)值w’，使用新的邊權(quán)值集合滿足以下兩個(gè)性質(zhì)：對所有的頂點(diǎn)u,v，如果路徑p是在權(quán)值函數(shù)w下從u到v的最短路徑，當(dāng)且僅當(dāng)p也是在權(quán)值函數(shù)w’下從u到v的最短路徑；對于所有的邊u,v，新的權(quán)值w’(u,v)是非負(fù)的（于是滿足Dijkstra算法的要求）。Johnson算法的簡明步驟：生成一個(gè)新圖G’，G’是在G上擴(kuò)展一個(gè)起始點(diǎn)后的結(jié)果；在G’上調(diào)用Bellman-Ford算法。由于Bellman-Ford算法能夠檢測負(fù)權(quán)回路，如果存在負(fù)權(quán)回路則報(bào)告存在負(fù)權(quán)回路并結(jié)束整個(gè)算法；否則得到在G’上調(diào)用Bellman-Ford算法得到的h(x)函數(shù)；根據(jù)h(x)函數(shù)對G中的每一條邊進(jìn)行重賦權(quán)，使得G中的每一條邊都是非負(fù)的；對重賦權(quán)后的G進(jìn)行循環(huán)調(diào)用Dijkstra算法，得到每對頂點(diǎn)間的最短路徑；對得到的每對頂點(diǎn)間的最短路徑再根據(jù)h(x)函數(shù)反向構(gòu)造出原來權(quán)值下的最短路徑值。第26章：最大流流守恒：物質(zhì)進(jìn)入到某頂點(diǎn)的速度必須等于離開該頂點(diǎn)的速度。tOutpu（代碼：tOutpu（代碼：httnp:///p/introductio-to-algorithms-notes/）:FloydWarshall最短路徑01-32-430-41-1740532-1-05-251608Johnson最短路徑01-32-403-41-1740532-1-50-285160請按任意鍵繼續(xù)...某個(gè)頂點(diǎn)處的總的凈流量：為離開該頂點(diǎn)的總的正流量，減去進(jìn)入該頂點(diǎn)的總的正流量。流守恒性的一種解釋是這要瓣，即進(jìn)行某個(gè)非源點(diǎn)非匯點(diǎn)頂點(diǎn)的正網(wǎng)絡(luò)流，必須等于離開該頂點(diǎn)的正網(wǎng)絡(luò)流。這個(gè)性質(zhì)（即一個(gè)頂點(diǎn)處總的凈流量必定為0）通常被非形式化地稱為“流進(jìn)等于流出”。抵消：利用了抵消處理，可以將兩城市間的運(yùn)輸用一個(gè)流來表示，該流在兩個(gè)頂點(diǎn)之間的至多一條邊上是正的。也就是說，任何在兩城市間相互運(yùn)輸球的情況，都可以通過抵消將其轉(zhuǎn)化成一個(gè)相等的情況，球只在一個(gè)方向上傳輸：沿正網(wǎng)絡(luò)流的方向。這樣：兩個(gè)頂點(diǎn)之間至多有兩條邊，而這兩條邊至多會有一條有正的流值，另一條相應(yīng)的邊的流值為0（明白這點(diǎn)在理解算法時(shí)是有用的）。具有多個(gè)源點(diǎn)和多個(gè)匯點(diǎn)的網(wǎng)絡(luò)最大流問題可以轉(zhuǎn)化成普通的單源點(diǎn)、單匯點(diǎn)的最大流問題（通過添加一個(gè)單一的源點(diǎn)和一個(gè)單一的匯點(diǎn)并置新添加的邊的容量為無窮大來達(dá)到）。Ford-Fulkerson算法是求最大流的一般方法，它利用了三點(diǎn)：殘留網(wǎng)絡(luò)、增廣路徑、最大流最小割定理。殘留網(wǎng)絡(luò)：Gf由可以容納更多網(wǎng)絡(luò)流的邊所組成；增廣路徑：為殘留網(wǎng)絡(luò)Gf上從s到t的一條簡單路徑p，其中p中所的邊的最小權(quán)值為