2023算法案例圖解

算法案例圖解2023目錄TOC\o"1-2"\h\u14790第1章一切從觀察開始 313891第2章分而治之法 2019884第3章動態(tài)規(guī)劃 556724第4章貪婪法 834023第5章修剪與搜索法 1188855第6章樹搜索法 13716760第7章問題轉(zhuǎn)換 1662756第8章圖算法 18130659第9章計算幾何 22726124第10章算法的難題 2562959第11章逼近算法 27922880第12章隨機算法 294第1章一切從觀察開始章節(jié)大綱什么是算法漢諾塔問題漢諾塔問題的非遞歸算法發(fā)現(xiàn)算法的技巧折紙飛機的過程隱含一個算法什么是算法什么是算法（algorithms）？簡而言之，算法是在符合問題的限制下，將輸入（input）轉(zhuǎn)換成輸出（output）的過程。過程也隱含一種算法。程序員（programmer）就是使用計算機執(zhí)行某一種算法，以解決特定問題的人，如表1.1所示。表1.1 算法存在于各行業(yè)中如何設計算法？設計算法的第一個好習慣就是觀察。我們認為觀察是一切發(fā)現(xiàn)的開始。本書開篇利用一個例子——漢諾塔（HanoiTower）問題說明觀察和設計算法的關(guān)系。漢諾塔問題漢諾塔問題是一個古老的游戲。游戲的目的是將左方柱子上的盤子搬到右方的柱子。游戲的規(guī)則有三條：一次搬一只盤子。每根柱子只有最上面的盤子可被搬動。大盤子不可置于小盤子的上方。圖1.1所示為三只盤子漢諾塔問題的一個解法。圖1.1 所示為三只盤子漢諾塔問題的一個解法。從上圖得知，三只盤子的漢諾塔問題共需要7個步驟完成。很自然地，我們提出第一個問題：n只盤子的漢諾塔問題，共需要幾個步驟完成？若這個問題無法立刻回答，則可先觀察一些范例。觀察一些小例子，并記錄其移動的次數(shù)。為記錄方便，我們使用數(shù)學符號Tn代表n只盤子漢諾塔問題所需要的搬運次數(shù)。嘗試算出n小于9之前的Tn，如表1.2所示。表1.2 觀察漢諾塔問題的搬運次數(shù)這個數(shù)列有什么規(guī)則？T9=？Tn好像是很靠近2的幾次方，Tn是2n-1嗎？如何證明Tn是2n-1？不知道。還有其他規(guī)則嗎？比較前后項的關(guān)系，好像后項是前項的兩倍？不，是兩倍加1?？梢允褂梅枌⒋岁P(guān)系寫下來嗎？可以，Tn=2Tn-1+1。為何前后項有這樣的關(guān)系？不知道。如果Tn=2Tn-1+1是正確的，有助于證明Tn=2n-1嗎？最常用的證明方法是什么？也許可以利用數(shù)學歸納法（mathematicalinduction）證明Tn=2n-1。證明過程如表1.3所示。表1.3 利用數(shù)學歸納法證明Tn=2n-1另一個簡單的證明如表1.4所示表1.4 Tn=2n-1的另一個證明我們只利用簡單的觀察便猜中了Tn=2n-1這個性質(zhì)。雖然不知道為什么Tn=2Tn-1+1，但此性質(zhì)有助于證明Tn=2n-1。接下來的一個問題是：給出一個有n只盤子的漢諾塔問題，如何（找出）搬動盤子（的算法）？若這個問題無法立刻回答，則可先嘗試找出一個小例子的解答，并觀察這個解答的規(guī)則。以下為有4只盤子的漢諾塔問題的一個解答。根據(jù)先前發(fā)現(xiàn)的性質(zhì)，我們得知共需要搬動24-1=15次，如圖1.2所示。好像有些成堆的盤子打散之后又成堆了?？梢越忉屍渲械牡览韱幔看蟾攀菫榱税釀幼畹撞壳易畲蟮谋P子，必須先將上面的3只盤子全部搬到中間的柱子。哪個步驟可以看出此特性？步驟7。圖1.2 有4只盤子的漢諾塔問題的搬動過一定需要這樣搬嗎？應該沒有其他可能。倘若上面的任意一只盤子散落于左邊的柱子，那么最底部且最大的盤子不能被搬動；若上面的任意一只盤子散落于右邊的柱子，那么最底部且最大的盤子無處可放?！睘槭裁词遣襟E7？因為前7個步驟是為了將上面的3只盤子全部搬到中間的柱子，第8個步驟將最大的盤子搬到了右邊的柱子，剩下的7個步驟是將先前置于中間柱子的3只盤子再全部搬到右邊的柱子?！盩4=2T3+1？倘若是n只盤子的漢諾塔問題，是否也可以利用搬n-1成？答案是可以的。為搬動n只盤子的漢諾塔，可以先搬n-1盤子搬到右邊的柱子，最后將中間的n-1只盤子搬到右邊的柱子。如此也說明先前發(fā)現(xiàn)的規(guī)律Tn=2Tn-1+1，因為搬動n只盤子需要搬動n-1只盤子兩次和最大的盤子一次，如圖1.3所示。圖1.3 解決5只盤子的漢諾塔問題需要搬動4只盤子兩次和最大的盤子一次根據(jù)上述道理，我們可以設計算法解決n只盤子的漢諾塔問題，如表1.5所示表1.5 漢諾塔的遞歸算法注意 以上子程序調(diào)用自己的概念是一個經(jīng)常使用的程序設計技巧——遞歸（recursion）。漢諾塔問題的非遞歸算法我們已經(jīng)找到一個解決漢諾塔問題的遞歸算法，另一個有趣的問題是：如果不用遞歸算法，可以解決漢諾塔問題嗎？好像不行？沒關(guān)系，先觀察幾個小例子。注意從輸入轉(zhuǎn)換成輸出的過程，并且用符號記錄整個移動過程。3只盤子漢諾塔問題的搬動過程如圖1.4所示。為了方便，利用1到3的整數(shù)代表從小到大的3只盤子，而ABC代表3根柱子的位置。圖1.4 記錄3只盤子漢諾塔問題的整個搬動過看起來沒有規(guī)律？不要放棄，嘗試另一種表示法。因為3只盤子的漢諾塔問題共需要23-1=7次搬動。我們需要記錄7次搬動中每次搬動的盤子號碼和搬動的方向（即從哪一根柱子搬到哪一根柱子），如圖1.5所示。圖1.5 換一種方式記錄3只盤子的漢諾塔搬動過還是看不出有什么規(guī)律？不要放棄，再嘗試另一種表示法。因為搬動的方向似乎不易觀察出規(guī)律，所以圖1.6將移動的方向標注得更簡潔一些。圖1.6 換一種方式記錄3只盤子的漢諾塔搬動過也許應該試試n大一點的例子？圖1.7是n=4的例子。圖1.7 記錄4只盤子的漢諾塔搬動過程注視搬運的盤子號碼，是否找得到規(guī)律好像1號盤子出現(xiàn)在奇數(shù)的搬動次數(shù)上？其他盤子也有這種現(xiàn)象嗎？2號盤子沒有這個現(xiàn)象。但是，好像每個2號盤子隔4次才搬動一次？專心觀察2號盤子被搬動的步驟，如圖1.8所示。圖1.8 觀察2號盤子被搬動的步還有其他盤子有類似的現(xiàn)象嗎？3號盤子隔8次出現(xiàn)一次。所有盤子有一致的規(guī)律嗎？啊，我知道了。k號盤子每隔2k次搬動一次。知道第i步驟搬動第幾號盤子嗎？不知道，但是第1，3，5，7，9，11，13，15步是搬動第1號盤子，而第2，6，10，14步是搬動第2號盤子，第4和12步是搬動第3號盤子，而第8步搬動第4號盤子。耶，我知道了?？赡芎瓦@些數(shù)字的因子為2的倍數(shù)有關(guān)?？梢杂梅枌懴聛韱幔康趇步搬動盤子的號碼與i最大的因子2k有關(guān)。我們終于知道，當進行第i步時，找出最大的k使得i=2k×z（z為正整數(shù)）。因此，在第i步時，需要搬動第k+1號盤子。每次盤子搬動的方向知道了嗎？也許我們該看看，1號盤子搬動方向的規(guī)律是什么？圖1.9標注了1號盤子在整個搬動過程中的搬動方向。圖1.9 觀察1號盤子的搬動方有規(guī)律嗎？先看看1號盤子搬動的方向，好像往上移動到頂后就掉下來？再看看2號盤子搬動的方向。有規(guī)律嗎？1號盤子和2號盤子搬動的方向有一些相像，但又不一樣。3號呢？啊，我知道了。3號盤子和1號盤子搬運的方式一致，也就是奇數(shù)號盤子搬動的方式一致。偶數(shù)號盤子搬動的方式一致？是的，偶數(shù)號盤子搬動的方式一致，只是方向正好相反。也就是往下移動到底后，就跳上去。圖1.10標注了偶數(shù)號盤子在整個搬動過程中的搬動方向。圖1.10 觀察偶數(shù)號盤子的搬動方向試一試其他例子，看看是否仍保留此規(guī)律呢？當漢諾塔問題的盤子數(shù)是奇數(shù)時，好像整個搬動的方向全部相反?？梢該Q個方式描述您的觀察嗎？當漢諾塔問題的盤子數(shù)是奇數(shù)時，奇數(shù)號盤子往下移動到底后，就跳上去；而偶數(shù)號盤子往上移動到頂后，就掉下來。這些性質(zhì)如何證明？前面不是說，這本書不會提及證明的嗎？根據(jù)以上討論，可設計一個解決漢諾塔問題的非遞歸算法，如表1.6所示。為了方便起見，將3根柱子編號命名為0（起始的柱子）、1（可暫放的柱子）、2（目標的柱子）。表1.6 漢諾塔問題的非遞歸算法發(fā)現(xiàn)算法的技巧我們只利用“觀察例子，尋找規(guī)律”就發(fā)現(xiàn)了解決漢諾塔問題的兩個算法，讀者也許會問下列問題：我感覺好像比以前靈光多了？你以前為什么不靈光呢？以前我只會努力記住別人教過的問題和方法?，F(xiàn)在不同了嗎？有一點感覺，但是怎樣才有機會發(fā)現(xiàn)更多算法呢？也許，波利亞先生（G.Polya）在《怎樣解題》（HowtoSolveIt）中的一段話，可回答發(fā)現(xiàn)算法的技巧。怎樣解題（HowtoSolveIt）（節(jié)錄并翻譯自波利亞的《怎樣解題》一書）首先，你必須弄清問題。是否充分？或者它是否不充分？或者是多余的？或者是矛盾的？畫張圖，引入適當?shù)姆?，把條件的各個部分分開，你能否把它們寫下來？其次，找出已知數(shù)與未知數(shù)之間的聯(lián)系。如果找不出直接的聯(lián)系，你可能不得不考慮輔助問題。你應該最終得出一個求解的計劃。你以前見過這個問題嗎？你是否見過相同的問題而形式稍有不同？你是否知道與此有關(guān)的問題？你是否知道一個可能用得上的定理？看著未知數(shù)！試想出一個具有相同未知數(shù)或相似未知數(shù)的熟悉的問題。這里有一個與你現(xiàn)在的問題有關(guān)，且早已解決的問題，你能應用它嗎？你能不能利用它？你能利用它的結(jié)果嗎？為了能利用它，你是否應該引入某些輔助元素？你能不能重新敘述這個問題？你能不能用不同的方法重新敘述它？出一個更容易著手的有關(guān)問題？一個更普遍的問題？一個更特殊的問題？一個類比的問否利用了所有條件？你是否考慮了包含在問題中的所有必要的概念？再次，實行你的計劃。實現(xiàn)你的求解計劃，檢驗每一個步驟。你能否清楚地看出這一步是正確的？你能否證明這一步是正確的？最后，驗算所得到的解。你能否檢驗這個論證？你能否用別的方法導出這個結(jié)果？你能否一下子看出它來？你能不能把這結(jié)果或方法用于其他問題？學習效果評測并寫下你的觀察與想法。老王開雜貨店想送N塊冬瓜糖磚給客戶，每塊冬瓜糖磚長、寬、高都是10望將這N塊冬瓜糖磚包裝成一大包（x×y×z的長方體），以方便運送，但為了響應環(huán)保，希望使用的包裝紙越少越好。編寫一個程序輸入N，輸出最少的包裝紙面積。輸入:9輸出:3000編寫一個程序，對一個正整數(shù)進行質(zhì)因子的分解。例如，3080=23×5×7×11。輸入:3080輸出:2^3×5×7×11第2章分而治之法章節(jié)大綱何謂分而治之法找出最大值時間復雜度二維極點問題快速排序法快速排序法的時間復雜度尋找第k小值問題分而治之法的技巧“鄧哀王沖，字倉舒。少聰察岐嶷，生五六歲，智意所及，有若成人之智。時孫權(quán)曾致巨象，太祖曹操欲知其斤重，訪之群下，咸莫能出其理。沖曰：‘置象大船之上，而刻其水痕所至，稱物以載之，則?？芍??！娲髳?，即施行焉。”三國志·魏書曹沖傳何謂分而治之法何謂分而治之法（divideandconquer）？簡而言之，就是將一個問題分割（divide）成一些小問題，并且遞歸地解決（conquer）后，再利用這些小問題的解合并（merge）成原來大問題的解。”古時候要直接秤大象的重量不易，于是利用等重且較小的物品取代量測，分次稱出所有取代的物品后，再計算總和即可得到大象的重量。古人曹沖稱象的典故，其實蘊藏分而治之法的精神。在本章我們將利用幾個例子介紹這個相當常見的算法技巧。找出最大值第一個問題是在一個整數(shù)的集合中找到最大值，如表2.1所示表2.1 找出最大值尋找最大值（findingthemaximum）使用一個循環(huán)便可輕易解決，如表2.2中的算法所示。表2.2 尋找最大值的算法我們以“尋找最大值”介紹第一個分而治之的算法。如果要在一堆數(shù)字中找到最大值，那么可以將這些數(shù)字分成平均的兩堆。分別從這兩堆數(shù)字中找到最大值后，再比較這兩個值，找出其中較大者即可，如圖2.1所示。圖2.1 將一堆整數(shù)分成兩堆后，再來找最大值若將100個數(shù)據(jù)存放在矩陣A[1：100]中，首先將此矩陣從中間分成兩個均等的小矩陣A[1：50]和A[51：100]（此為分割（divide）步驟）。若我們可以在A[1：50]中找到最大值，而且在A[51：100]中找到另一個最大值，則從這兩數(shù)中找出更大的值（此為conquer步驟），即可得到答案。利用這樣的概念，第一個分而治之的算法就可以被設計出來了，如表2.3所示。表2.3 尋找最大值的分而治之算法時間復雜度表2.2和表2.3中的兩個算法哪一個比較好？怎樣評判一個算法的好與壞？比如擁有較少的程序運行時間，也就是較小的時間復雜度（timecomplexity）。什么是算法的時間復雜度？簡而言之，就是一個算法要花多少時間執(zhí)行。以找出最大值的算法（見表2.2）為例，每條指令被執(zhí)行的次數(shù)如表2.4所示表2.4 尋找最大值的算法時間復雜度這個算法的時間復雜度為2n+1，此n是輸入數(shù)值的個數(shù)。因為2n+1是n的兩倍加1，當n夠大時，2n和3n、5n差不多和n成正比，因此我們常用O（n）（讀作bigOn）簡稱算法的時間復雜度。表2.5將介紹O的正式定義。表2.5 O的正式定義根據(jù)O的定義，表2.2上的尋找最大值的算法有2n+1=O（n）最大值的分而治之算法（表2.3）的時間復雜度為多少呢？執(zhí)行Proceduremax-divide-and-conquer（1，n，Vmax）所需的計算時間為T（n）。因為此算法將輸入的矩陣平均分割后，調(diào)用自己兩次，所以我們可以將T（n）用兩個T（n/2）取代后得T（1）=1；T（2）=2；T（n）=2T（n/2）+4，如表2.6所示。解開此數(shù)學式子即可知T（n）。如何知道此數(shù)學式子的解呢？最簡單的方法是用“猜”。表2.6 數(shù)學式子T（1）=1；T（2）=2；T（n）=2T（n/2）+4的值直觀上看起來，T（n）都小于n的常數(shù)倍數(shù)，故T（n）可能為O（n）。若以O的角度分類，則這兩個算法可歸類于O（n）這個時間復雜度等級的算法。二維極點問題若將2.2節(jié)尋找最大值的問題擴展到坐標平面上，則成為了二維極點問題（the2-dimensionalmaximafinding）。一個平面上的點的坐標可用兩個整數(shù)（x，y）表示。當x1>x2且y1>y2時，我們說一個平面上的點（x1，y1）支配（dominate）另一個點（x2，y2），即圖2.2中右上方的點支配左下方的點。圖2.2平面點(x1,y1)支配另一個平面點(x2,y2)二維極點問題就是在一些平面上的點中找到那些沒有被其他點支配的點，也就是極點（maxima）。直覺上，極點就是所有坐標點中那些位居右上方的一些坐標點，如表2.7和圖2.3所示。表2.7二維極點問題圖2.3 二維極點問題是找出所有極點（圖中深黑色的點）解決二維極點問題最簡單的方法是采用暴力法（bruteforcemethod）。想法很簡單，若某點A右上方有一點B，則A必不是極點。因為極點的右上方一定沒有其他點，如圖2.4所示。圖2.4 極點（深黑的點）右上方必沒有其他點此暴力法就是每一點A都和其他點B比較。若B在A的右上方，則排除A為極點的可能，最后留下（未被排除）的點即為極點。例如，在圖2.4中，比較（8，2）和（10，6）兩點后，舍棄（8，2）。（10，6）并非極點，因為（10，6）在和（15，7）比較后，也被舍棄。此方法的時間復雜度取決于兩點比較的總次數(shù)。若給定n個點，任意兩點需要比較一次，總共要比幾次？從n個點中任意選取兩點的所有組合，也就是C（n，2）或。這個暴力法雖然解決了二維極點問題，但是我們?nèi)韵胫朗欠裼衅渌斓姆椒?。這個問題可以利用分而治之法解決。但是什么是分而治之法？將一個問題分割成一些小問題并且遞歸地解決后，再利用這些小問題的解合并成原來問題的解。你認為設計分而治之法的第一步應該思考什么？如何將二維極點問題進行分割。怎樣分割呢？最簡單的分割方法是什么？從中間分割成兩半吧，如圖2.5所示。圖2.5 將平面的點分割成左右均等的兩半將平面的點分割成左右均等的兩半后，分別（遞歸地）找到左邊點的極點集合和右邊點的極點集合，再將兩組的極點合并成最后的解，如圖2.6所示。圖2.6 先找到左半邊的極點和右半邊的極點在圖2.6中欲合并左右兩邊的極點，只需要將兩個集合執(zhí)行并集操作就可以了。再多試幾個例子，將會發(fā)現(xiàn)將左半邊的極點和右半邊的極點直接并集后，不一定就是最后的解，如圖2.7所示。原因是在并集中出現(xiàn)了有問題的點（圖2.7中打×的點）。圖2.7 當左半邊的極點被右半邊的極點所支配時，必不是極點有趣的是，有問題的點都在左半邊，原因是有一些在左半邊找到的極點有可能被右半邊的極點所支配（圖2.7中A和B被C所支配）。注意右半邊點的x坐標必大于左半邊點的x坐標，故當右半邊點的y坐標也大于左半邊點的y坐標時，右半邊的點便支配左半邊的點，這些左半邊的點必不是極點。因此在右邊的極點集合中，最高（或最左）的極點為C。當合并時，左邊極點集合中高度小于C的點必不是極點（因為這些點必為C所支配）。如圖2.7中的A、B就必須被除去，因為這兩點被C所支配。最后合并的解答如圖2.8所示。此分而治之的算法如表2.8所示。圖2.8 合并后的極點表2.8 二維極點問題的分而治之算法二維極點問題分而治之算法的時間復雜度是多少？若T（n）為當輸入n點時所需的運行時間，則T（n）大約為2T（n/2）+O（n）。若解開此遞歸式，則可得T（n）=O（nlogn）。快速排序法快速排序法（Quicksort）是另一種典型的分而治之算法。什么是排序（sorting）問題？簡而言之，就是討論如何將數(shù)據(jù)從小到大排列的問題。表2.9將對排序問題進行基本描述。表2.9 排序問題下面舉一個例子說明快速排序法。快速排序法的基本技巧是什么？分割（partition）：用一個數(shù)將所有其他的數(shù)值分成左右兩邊，使得左邊的數(shù)都小于或等于此數(shù)，右邊的數(shù)都大于或等于此數(shù)。下面的例子中，先將9個整數(shù)存儲在數(shù)組中。取出矩陣中第一個數(shù)，當作分割元素（partitioningelement）（即圖2.9中的65）。從矩陣中第二個數(shù)開始向右尋找大于等于65的數(shù)，同時從矩陣最后一個數(shù)開始向左尋找小于等于65的數(shù)。交換這兩個數(shù)的位置，重復前述動作，直到左右兩方的尋找箭頭交叉，此時將分割元素，與所指向比它小的數(shù)交換位置。注意，圖2.9中數(shù)字下的箭頭代表當前尋找的方向和位置。圖2.9 分割為快速排序法的主要步驟分割算法在掃描整個矩陣后，有一處疑點需要簡單討論。為何要將分割元素與所指向比它小的數(shù)交換位置？如果將分割元素與所指向比它大的數(shù)交換位置，會怎樣呢？比分割元素大的數(shù)將會被置于矩陣第一個位置，這樣會造成比分割元素大的數(shù)被置于左于或等于此數(shù)，右邊的數(shù)都大于或等于此數(shù)?！北?.10所示為此分割算表2.10 分割算法利用分割算法可以設計出快速排序法的算法，如表2.11所示表2.11 快速排序法的算法快速排序法的時間復雜度快速排序法的時間復雜度是多少？當輸入n個數(shù)字時，快速排序法所需的運行時間為T（n）。利用分割元素會將整個矩陣（n個數(shù)據(jù)）分割為兩個未排序的小矩陣，之后再遞歸地調(diào)用兩次快速排序法，來處理剩下的排序工作。根據(jù)上述說明，可得T（n）=T（j）+T（n-j-1）+n+1。此處，T（j）和T（n-j-1）為兩個小矩陣，是被遞歸調(diào)用兩次快速排序法所需的時間，而n+1是分割算法掃描矩陣（直到箭頭交錯）所需的比較（comparison）時間（見圖2.9）。為了簡化這個分析，在此我們僅考慮所需的比較（comparison）時間，并不包含交換（exchange）所需的時間。若能解開此遞歸式，則可得快速排序法的時間復雜度T（n）。顯然，T（n）的值可能會因j值的不同而有所變化。下面我們將討論快速排序法的最佳、最差及平均時間復雜度?？焖倥判蚍ǖ淖罴褧r間復雜度在哪種情況下，快速排序法執(zhí)行得最快？先想想什么是快速排序法執(zhí)行所需的時間。即遞歸式T（n）=T（j）+T（n-j-1）+n+1的解。當j為何值時，T（n）最??？可能是j=1或n，或。顯然，上述討論的答案取決于以下兩式的解：（1）T（0）=0，T（1）=0，T（n）=T（（n-1）/2+T（（n-1）/2）+n+1（2）t（0）=0，t（1）=0，t（n）=t（1）+t（n-2）+n+1試著將這兩式T（n）和t（n）前幾項的值列出，如表2.12所示。觀察此表可知，這兩式的值隨n的變大而變大（遞增性質(zhì)）。另一個現(xiàn)象是，當n變得足夠大時（n≥6），t（n）的值總是大于T（n）的值。表2.12 遞歸式T（n）和t（n）前幾項的值最小值可能是T（n），最大值可能是t（n）。在j大約是n/2時，會有最小值的T（n）值，也就是快速排序法執(zhí)行最快的時候。這表示如何分割，快速排序法才會執(zhí)行得最快？平均分割，也就是分割元素位于正中間時。我們知道了快速排序法在平均分割時會有最佳的時間復雜度，但真正的理由是什么？你可以一眼看穿嗎？嗯……或者，如何知道快速排序法最佳的時間復雜度？可解開此遞歸式：T（0）=0，T（1）=0，T（n）=T（（n-1）/2+T（（n-1）/2）+n+1。但好像有點難。你可以想象一個類似的更容易的問題嗎？可以。遞歸式：T（0）=0，T（1）=0，T（n）=T（n/2）+T（n/2）+n+1=2T（n/2）+n+1比較簡單，尤其是當n=2k時。解開此簡單遞歸式的一個方法是利用重復展開?？焖倥判蚍ㄗ罴褧r間復雜度的近似解如下：T（0）=0，T（1）=0，T（n）=2T（n/2）+n+1，當n=2k。=2（2T（n/4）+n/2+1）+n+1（因為T（n/2）=2T（n/4）+n/2+1）=4T（n/4）+n+2+n+1=4（2T（n/8）+n/4+1）+n+2+n+1=8T（n/8）+n+4+n+2+n+1=16T（n/16）+n+8+n+4+n+2+n+1...=2k×0+log2n×n+（2k-1+...+4+2+1）=log2n×n+（2k-1+...+4+2+1）=log2n×n+n-1=O（nlogn）注意 才是快速排序法的真正最佳時間復雜度。然而其解可利用數(shù)學歸納法獲得，而且也正好是O（nlog2n）?？焖倥判蚍ǖ淖畈顣r間復雜度快速排序法的最差時間復雜度是多少？什么是快速排序法執(zhí)行所需的時間？即此遞歸式T（n）=T（j）+T（n-j-1）+n+1的解。何時T（n）會有最大值？應該是遞歸式T（n）=T（0）+T（n-1）+n+1的解。同樣地，迭代此遞歸式即可得到快速排序法的最差時間復雜度O（n2），過程如下：T（0）=0，T（1）=0，T（n）=T（0）+T（n-1）+n+1=0+T（n-1）+n+1=T（n-1）+n+1=（T（n-2）+n）+n+1，因為T（n-1）=T（n-2）+n=T（n-2）+n+n+1=（T（n-3）+n-1）+n+n+1=T（n-3）+（n-1）+（n）+（n+1）...=T（1）+3+4+…+（n-1）+（n）+（n+1）=0+（3+n+1）（n-1）/2=（n+4）（n-1）/2=n2/2+3n/2-2=O（n2）快速排序法的平均時間復雜度最壞和最好的情況不會常常出現(xiàn)，那么一般情況下，快速排序法的表現(xiàn)如何？快速排序法的平均時間復雜度又是多少？地說，當分割最平均時，快速排序法執(zhí)行得最快；相反，當分割最不平均時，執(zhí)行得最率都是相同的（如圖2.10到圖2.14中↓所示的位置），那么快速排序法所需平均（期望）行的時間是多少？首先，矩陣共存儲n個數(shù)值，當分割元素位于矩陣第一位時，其執(zhí)行時間為T（n）=T（0）+T（n-1）+n+1。圖2.10 分割元素落在矩陣的最左邊位置當分割元素位于矩陣第二位時，其運行時間為T（n）=T（1）+T（n-2）+n+1。圖2.11 分割元素落在矩陣左邊第二個位置當分割元素位于矩陣第三位時，其運行時間為T（n）=T（2）+T（n-3）+n+1。圖2.12 分割元素落在矩陣左邊第三個位置以此類推，當分割元素位于矩陣最后第二位時，其運行時間為T（n）=T（n-2）+T（1）+n+1。圖2.13 分割元素落在矩陣右邊第二個位置當分割元素位于矩陣倒數(shù)第一位時，其運行時間為T（n）=T（n-1）+T（0）+n+1。圖2.14 分割元素落在矩陣最右邊的位置假設每一種情況發(fā)生的概率都是一樣的（即1/n），那么快速排序法的平均時間復雜度可將每一種情況所需的運行時間加總后再除以n，得到以下遞歸式：T（n）=（（T（0）+T（n-1）+n+1）+（T（1）+T（n-2）+n+1）+…+（T（n-2）+T（1）+n+1）+（T（n-1）+T（0）+n+1））/n稍作整理可得：T（n）=n+1+2/n×（T（0）+T（1）+...+T（n-1））解開此遞歸式后，可得T（n）=O（nlogn）?？焖倥判蚍ǖ钠骄鶗r間復雜度詳細分析如下：T（0）=T（1）=0T（n）=n+1+2/n×（T（0）+T（1）+...+T（n-1））將上式等號的左右各乘上n可得：nT（n）=n（n+1）+2（T（0）+T（1）+...+T（n-1）） 將上式所有的n用n-1代入，得出另一等式：（n-1）T（n-1）=（n-1）n+2（T（0）+T（1）+...+T（n-2）） 將（A）-（B），可得一個較精簡的遞歸式：nT（n）-（n-1）T（n-1）=n（n+1）-n（n-1）+2（T（0）+T（1）+...+T（n-1）-（T（0）+T（1）+...+T（n-2）））=2n+2T（n-1）整理一下可得：nT（n）=（n+1）T（n-1）+2n再將上面的等式左右各除以n（n+1）可得：迭代此遞歸式可得：尋找第k小值問題最后一個例子是，在n個數(shù)中尋找第k小值問題，如表2.13所示。當k=1或n時，就是找最小值或最大值問題，在第2.2節(jié)中，我們利用一個循環(huán)便可輕易解決。但當k不固定時，如何有效地解決此問題呢？表2.13 尋找第k小值問題如何在n個數(shù)中尋找第k小值？可先將n個數(shù)從小到大排序（sort）后，再從矩陣第k個位置獲取。如此所需的時間復雜度為多少？若使用一般的排序法，則需要O（nlogn）。有可能更快嗎？比如O（n）。如何在O（n）時間內(nèi)，尋找第k小值？下面進行介紹。尋找第k小值的O（n）算法本節(jié)的重點是設計一個可以找到任意第k小值的O（n）算法。根據(jù)上述討論，顯然不可以利用排序法（否則所需的時間將達到O（nlogn））。此算法需要的技巧源自于快速排序法中的分割算法（參考第2.5節(jié)）。首先，利用快速排序法中的分割算法將整個矩陣分成“比分割元素大”和“比分割元素小”的兩個集合。然后，如圖2.15所示，分割元素65是第5小的數(shù)，若k=5，則此數(shù)為解；若k>5，則需在右邊集合中尋找，此時左邊集合可略過不必找；若k<5，則需在左邊集合中尋找，此時右邊集合可略過不必找。遞歸地使用以上步驟，即可找到第k小值。問題是，這樣的做法所需的最長時間等同于快速排序法在最差情況下的時間復雜度O（n2）。圖2.15 分割元素的位置決定尋找第k小值的范上述方法的缺點是什么？未平均分割的原因何在？最好的分割元素是什么？找中間的值當作分割元素。如何找中間的值？可先將n個數(shù)從小到大排序（sorting）后，再從矩陣中間位置獲取。這樣的算法可以在O（n）內(nèi)完成嗎？糟了，不行！排序就花掉了O（nlogn）的時間。有其他方法可以較快地找到中間的值嗎？如果你一時不能解決此問題，可先嘗試一些相關(guān)的問題?？梢韵胂蟮揭粋€更容易的相關(guān)問題嗎？找到接近中間的值不知道有沒有幫助？如何很快地找到接近中間的值？好像很難？要找到中間的值，難在哪里？好像這個值跟矩陣中每個數(shù)都有關(guān)？怎樣的中間值比較好找？如果從5個數(shù)中找中間值就容易多了。這樣可以幫助你找到中間的值或較接近中間的值嗎？n個數(shù)太多了，若是只有5個數(shù)就好找了。也許將n個數(shù)分成每5個數(shù)一組……然后呢？將每一組的中間值找到。大約n/5組，然后從這些值中找到其中間值。這樣的值拿來當作分割元素，不知道效果好不好？下面進行介紹。以下算法就是利用此想法快速獲取大致接近中間的值。例如，將n個數(shù)排列成每5個數(shù)一行，若最后一行不足，則自成一行，如圖2.16所示。圖2.16 將n個數(shù)排列成每5個數(shù)一行后，取其中間值的中間值每行5個數(shù)，分別找出其中間值（共有個數(shù)）后，再從這些中間值中取出其中間值mm。表2.14是利用mm當作分割元素，尋找第k小值的算法。表2.14 尋找第k小值的O（n）算法注意從中間值中取出中間值mm的步驟（即Step5）是遞歸地調(diào)用尋找第k小值的算法，只是此時的k值是中間值總數(shù)的一半。尋找第k小值算法的時間復雜度分析尋找第k小值的O（n）算法的關(guān)鍵是，所選的分割元素mm必須足夠靠近整個矩陣的中間值。如此在分割后，無論向右找（比mm大的值）或向左找（比mm小的值），都可保證至少有足夠多（至少大約n/4）的數(shù)不必尋找，如圖2.17所示。圖2.17分割元素mm為介于矩陣a等n/4到第3n/4小的數(shù)下面說明分割元素mm屬于矩陣a中“大約介于第n/4到第3n/4小的數(shù)”的理由。因為mm是m[i]（[n/5]列）中的中間值，所以m[i]中必有[[n/5]/2]的值大于或等于mm，如圖2.18中間的橢圓形所示。除了mm這行和可能未排滿的最后一行，在剩下的（[[n/5]/2]–2）行中，每行有[5/2]=3的值大于或等于m[i]，如圖2.18右下方的長方形所示。如此可知，至少有3×（[[n/5]/2]-2≥ 個數(shù)大于或等于mm。同理，也有多于的值小于或等于mm，如圖2.18左上方的長方形所示。因此在遞歸調(diào)用selection時的輸入矩陣a中，最多（即）（接近3n/4）個數(shù)字。圖2.18 至少有-6個數(shù)大于或等于mm（右下方的長方塊），同時至少有個小于或等于mm（左上方的長方塊）注意 圖2.18的數(shù)值排列是假設左上方的值都小于右下方的值。在算法中，我們并不需要真正進行這樣的排列，畢竟此圖只是用來說明的，分割元素mm的確足夠靠近整個矩陣的中間值。中的步驟，除了Step5和Step7外，都可在O（n）內(nèi)完成。Step5需要T（[n/5]）的時間，而Step7需要的時間。因此尋找第k小值算法的時間復雜度T（n）可用以下式子表示：此處的k為常數(shù)。利用數(shù)學歸納法可得，當n>80時，T（n）≤cn。利用數(shù)學歸納法證明尋找第k小值算法的時間復雜度T（n）=O（n）的過程如下：定理2.1因此T(n)<=cn當n>80證明：假設小于n時，本定理成立，那么：因為所以選擇c，使得當n>80時，為真因此，我們設計了一個尋找第k小值問題的線性（即O（n））時間復雜度的算法，此為理論上最佳的算法。分而治之法的技巧什么問題可利用分而治之法來解決呢？這個問題顯然不容易回答。不過，一旦一個問題可被分而治之法解決，也常隱含此問題可被并行處理。最后，提醒使用分而治之法時的注意事項?！し指睿╠ivide）：盡可能快速地將問題平均地分割。若能將問題平均地分割成幾個小問題，則可降低所需的運行時間?！た朔╟onquer）：利用遞歸解決分割后的小問題?！ず喜ⅲ╩erge）：間會影響整個算法所需的運行時間。還有什么問題可被分而治之法解決？下面列出一些可被分而治之法解決的常見問題，供讀者參考。合并排序（mergesort）：排列的方法。二分搜索法（binarysearch）：利用一組已從小到大（或從大到?。┡判蚝玫臄?shù)值進索。前綴和（prefixsum）：計算一維矩陣B，使得B[i]中存儲著從A矩陣中第一個值加到第i（1≤i≤n）個值的總和。此技巧常被用于設計并行處理的算法。矩陣相乘問題：將兩個矩陣快速相乘的問題。鄰近配對問題（closestpairproblem）：找出平面點中最靠近的兩點的距離。凸包問題（convexhullproblem）：問題。維諾圖（Voronoidiagrams）：將每一個平面點x分割落于單獨的一個區(qū)域，使得另一個新加的平面點y落于此區(qū)域時，其最近的點為x。此算法技巧可用于無線移動設備（y）快速地尋找最近的基站（x）。學習效果評測設計一個分而治之的程序解決二維極點問題。輸入：8 (平面點的個數(shù))24 (以下是每個點的x和y坐標310536882106135157輸出：31068157T（n）=T（n/2）+T（n/2）+1時，T（n）=O（n）。3.設計一個程序執(zhí)行快速排序法（quicksort）。輸入：657075808560555045輸出：455055606570758085第3章動態(tài)規(guī)劃章節(jié)大綱何謂動態(tài)規(guī)劃換零錢數(shù)字金字塔最長相同子字符串安排公司聚會動態(tài)規(guī)劃的技巧“岱宗如何”是泰山派劍法的絕藝，要旨不在右手劍招，而在左手的算數(shù)。左手不住屈指計算，算的是敵人所處方位、武功門派、身形長短、兵刃大小以及日光所照高低等，計算極為繁復，一經(jīng)算準，挺劍擊出，無不中的。金庸 笑傲江湖何謂動態(tài)規(guī)劃什么是動態(tài)規(guī)劃（dynamicprogramming）？簡而言之，就是計算并存儲小問題的解，并將這些解組合成大問題的解。當大問題的解可利用小問題的解組合計算得知時，若將可能用到的小問題的解先算出并存儲起來，則可縮短計算大問題的解的時間。乍看之下，動態(tài)規(guī)劃還蠻暴力的。使用動態(tài)規(guī)劃常經(jīng)過煩瑣的計算，最后一舉解決問題，有一點像金庸的武俠小說《笑傲江湖》中的絕招“岱宗如何”。但是需注意的是，小問題的解一旦被計算出并存儲后，就不會再被重復計算。當動態(tài)規(guī)劃運用得當時，可高效率地解決問題。換零錢第一個例子是換零錢問題，問題描述如表3.1所示表3.1 換零錢問題問題任意給定一個金額n，有時不一定能用有限種類的零錢湊齊。例如，硬幣種類為{33，24，12，5}時，就湊不出14元；而當硬幣種類為{33，24，12，5，1}時，就可以湊出14元，甚至所有正整數(shù)（因為有無限個一元的關(guān)系）。如果換零錢的策略為盡量先兌換大金額的零錢，那么會發(fā)現(xiàn)這個方法有時并不能換到最少的硬幣數(shù)目。如表3.1的例子，就會換成4個硬幣（36=33+1+1+1），而非最佳的兩個（36=24+12）。怎樣才可以使用最少的硬幣，組合出總和為n的金額呢？所需最少的硬幣數(shù)目是多少？不知道。假設我們知道最佳（少）的硬幣組合，猜想其中的任意一個硬幣的面額會是多少？應該是所有硬幣種類其中之一?？鄣舸擞矌?，剩下的金額為多少？剩下的金額應該是n扣掉此硬幣的面額?？鄣舸擞矌?，剩下所需的硬幣數(shù)為多少？不知道。好像是同一個問題，但金額小一點。若知道如何用最少的硬幣數(shù)組合出此金額就好了。最后一句話暗示：若知道較小問題的最優(yōu)解，則有助于解決大問題。按表3.1中換零錢問題的范例，36元的組成有以下5種可能：由一個33元硬幣和3元組成。由一個24元硬幣和12元組成。由一個12元硬幣和24元組成。由一個5元硬幣和31元組成。由一個1元硬幣和35元為什么是5種？因為共有5種硬幣。在5種組成方法中，哪一種需要的硬幣數(shù)最少？不知道。因為不清楚3、12、24、31、35這些金額需要的最少硬幣數(shù)?？梢允孪扔嬎愠?、12、24、31、35分別需要多少硬幣。從以上5種可能的兌換方法中挑選所需硬幣數(shù)最少的一種，即最佳換零錢的方式。但是需要事先計算出這5種金額的最少硬幣數(shù)。根據(jù)上述討論，若讓函數(shù)f（n）代表組合金額為n所需要最少的硬幣數(shù)，則下列等式是正確的。f(36)=min{1+f(3),1+f(12),1+f(24),1+f(31),1+f(35))此處，min是從一個集合中選取最小值（minimumvalue）之意。動態(tài)規(guī)劃的技巧是：為了計算f（36），需事先利用類似的方式計算f（3）、f（12）、f（24）、f（31）和f（35）。下面以f（31）和f（35）為例進行說明。因為31=24+7=12+19=5+26=1+30，所以f（31）=min{1+f（7），1+f（19），1+f（26），1+f（30）}。為了計算f（31），需利用類似的式子，事先計算出f（7）、f（19）、f（26）和f（30）。同樣，因為35=33+2=24+11=12+23=5+30=1+34，所以f（35）=min{1+f（2），1+f（11），1+f（23），1+f（30），1+f（34）}。為了計算f（35），需使用類似的式子，事先計算出f（2）、f（11）、f（23）、f（30）和f（34）?？偠灾旅娴膬蓚€式子顯然是正確的。（1）f（0）=0。（2）f（n）=1+min{f（n-c1），f（n-c2），…，f（n-ck）}。當n>ci（1<i<k）且硬幣面額為c1或c2…或ck時，動態(tài)規(guī)劃的技巧會將f（n-c1），f（n-c2），…，f（n-ck）先行計算后存儲起來，再按照上述式子計算出f（n）的值（即找出f（n-c1），f（n-c2），…，f（n-ck）中的最小值后，再加上1）。表3.2將列出換零錢問題的算法。表3.2 換零錢問題的算法換零錢問題的算法在于利用一個循環(huán)和前頁中間的式子（2）先計算比n小的所有金額的解（即該金額所需的最少硬幣數(shù)）。最后利用這些解再計算出金額n的解。數(shù)字金字塔第二個例子是數(shù)字金字塔，如表3.3所示表3.3 數(shù)字金字塔這一題可用動態(tài)規(guī)劃來解嗎？怎樣判斷一個問題可不可以用動態(tài)規(guī)劃來解？為何換零錢問題可以被成功地解決？利用較小問題的最優(yōu)解組成大問題的最優(yōu)解。找出小問題的最優(yōu)解和大問題的最優(yōu)解之間的關(guān)系。找出大問題和小問題之間的關(guān)系弄清楚大問題和小問題之間的關(guān)系，顯然是解決本題的關(guān)鍵。如圖3.1所示，抵達金字塔頂點45的路徑只有兩種可能：（A）經(jīng)過20；（B）經(jīng)過33。圖3.1 左右數(shù)字金字塔的解有助于找到大數(shù)字金字塔（以45為頂）的解如果從底部走到20和從底部走到33的最快路徑都事先被找到，只要從中選一條最快的路，直接登上頂端45就是最佳答案了。如果事先計算得知，經(jīng)過20的最快路徑9→18→20所費的時間為47，而經(jīng)過33的最快路徑9→18→33所費的時間為60，顯然經(jīng)過20的路徑是兩條中的較小者。也就是抵達金字塔頂點45最快的路徑是一條先經(jīng)過20的路徑。因此，抵達大金字塔頂點45最快的路是從左邊小金字塔頂點20最快的路和右邊小金字塔頂點33最快的路中選最短的。這就是大問題的最優(yōu)解和小問題的最優(yōu)解之間的關(guān)系。如何知道小一些的數(shù)字金字塔的最優(yōu)解？知道更小一些的數(shù)字金字塔的最優(yōu)解，將有助于解決這個問題。圖3.2 左右更小數(shù)字金字塔的解有助于找到數(shù)字金字塔（以20為頂）的解如圖3.2所示，左右更小數(shù)字金字塔的解有助于找到數(shù)字金字塔（以20為頂）的解。顯然，左邊小數(shù)字金字塔的解是14→34這條路徑的和48，而右邊小數(shù)字金字塔的解是這條路徑的和27。比較大小之后，抵達金字塔頂點20的最快路徑是9→18→20。因此，解決數(shù)字金字塔的方法可系統(tǒng)地計算并存儲所有小問題的解，并將這些解組合成大問題的解。數(shù)字金字塔問題的數(shù)據(jù)結(jié)構(gòu)下面討論所需要的兩個數(shù)據(jù)結(jié)構(gòu)。矩陣變量val（x，y）存儲數(shù)字金字塔第x層、第y個元素的值（value）例如，圖3.3中val（3，2）存儲了數(shù)字18。圖3.3 矩陣val（x，y）存儲數(shù)字金字塔第x層、第y個元素的值矩陣變量sum（x，y）存儲從底層走到以第x層、第y個元素為金字塔頂端的最快路徑值。例如，在圖3.4中，sum（3，2）存儲以18=val（3，2）、45=val（4，2）及9=val（4，3）三個數(shù)形成的金字塔（即圖3.2中的右三角形）的最快路徑的值（即sum（3，2）=18+9=27）。換句話說，sum（x，y）存儲所有大小金字塔問題的最優(yōu)解。圖3.4 矩陣sum（x，y）代表從底層走到以第x層、第y個元素為金字塔頂端的最快路徑值根據(jù)以上討論，下列式子顯然是正確的。這里，子程序min（a，b）返回a、b中的較小值。sum（x，y）=val（x，y）+min（sum（x+1，y），sum（x+1，y+1））ifx不是底層。sum（x，y）=val（x，y）ifx是底層。注意 上面這個式子準確地描述了大問題和小問題之間的關(guān)系。最后，注意在計算sum（x，y）值時，可以從底層開始向上計算，即采取自下而上（bottom-up）的方式。理由很簡單，因為上一層的值sum（x，y）需要利用下一層的值sum（x+1，y）和sum（x+1，y+1）計算得出，所以下一層的值要先被計算并存儲。如此，利用動態(tài)規(guī)劃求解數(shù)字金字塔的算法就可被設計出來了，如表3.4所示。表3.4數(shù)字金字塔的算法最長相同子字符串利用動態(tài)規(guī)劃的算法技巧解決了前兩個問題。但是這個算法技巧的主要精神是什么呢？下面這句話非常關(guān)鍵。利用小問題的最優(yōu)解組成大問題的最優(yōu)解。動態(tài)規(guī)劃解決問題的3個步驟應該是：此問題的“大問題的最優(yōu)解”可以利用“小問題的最優(yōu)解”求取。利用一個數(shù)學式子將“大問題的最優(yōu)解”和“小問題的最優(yōu)解”出來。先將“小問題的最優(yōu)解”計算出后存儲下來，再利用它們算出“大問題的最優(yōu)解”。接下來介紹一個可應用于生命科學上的有趣問題：最長相同子字符串（thelongestcommonsubsequence），如表3.5所示。并展現(xiàn)如何遵循這3個步驟設計出一個動態(tài)規(guī)劃的算法。表3.5 最長相同子字符串下面將遵循上述3個步驟設計算法。步驟1：檢查大問題的最優(yōu)解是否可以利用小問題的最優(yōu)解求取。若用表3.5中的范例說明步驟1，則是問：X=<A，T，C，T，G，A，T>和Y=<T，G，C，A，T，A>的最長相同子字符串可否通過小一些的最長相同子字符串獲得？答案可以從下面兩個稍小問題的解中選擇一個獲取。X*=<A，T，C，T，G，A>和Y=<T，G，C，A，T，A>的最長相同子字符串（即<T，C，T，A>）。X=<A，T，C，T，G，A，T>和Y*=<T，G，C，A，T>的最長相同子字串（即<T，C，A，T>）。X=<A，T，C，T，G，A，T>和Y=<T，G，C，A，T，A>的最長相同子字符串只有兩種可能：（1）X最后沒有字母T；（2）Y最后沒有字母A（見圖3.5）。理由是最長相同子字符串必須同時出現(xiàn)在兩個字符串中。而此范例中的X和Y尾部的字母不同（即T≠A），故X和Y的最長相同子字符串不可能同時擁有X和Y的尾部。若事先計算出上述兩個（（1）和（2））最長相同子字符串的答案，則其中較長的相同子字符串為X和Y的最長相同子字符串。此大問題的最優(yōu)解包含小問題的最優(yōu)解的性質(zhì)，稱為最優(yōu)子結(jié)構(gòu)（optimalsubstructure）。圖3.5 最長相同子字符串問題的最佳子結(jié)構(gòu)性質(zhì)（當字尾不相同時）另一方面，當兩字符串的字尾相同時，可通過短一些的最長相同子字符串獲取。例如，當X=<A，T，C，T，G，A>和Y=<T，G，C，A，T，A>時，因為X和Y尾部的字母相同，所以可先找出X*=<A，T，C，T，G>和Y*=<T，G，C，A，T>的最長相同子字符串<T，C，T>，再于尾部加上共同擁有的A，就可以得到其最長相同子字符串為<T，C，T，A>，如圖3.6所示。此時大問題的最優(yōu)解（即<T，C，T，A>）一樣包含小問題的最優(yōu)解（即<T，C，T>）。圖3.6 最長相同子字符串問題的最佳子結(jié)構(gòu)性質(zhì)（當字尾相同時）注意 此最佳子結(jié)構(gòu)的性質(zhì)確認了動態(tài)規(guī)劃可以解決最長相同子字符串問題。步驟2：利用數(shù)學式子描述大問題的最優(yōu)解和小問題的最優(yōu)解的關(guān)系步驟1確認了大問題的最優(yōu)解包含小問題的最優(yōu)解，如此才有機會利用小問題的最優(yōu)解組合拼湊出大問題的最優(yōu)解。接下來，步驟2利用數(shù)學式子將此關(guān)系表達清楚。此式子也將在步驟3引導最后解的計算。當考慮兩個字符串X和Y的最長相同子字符串問題時，我們利用c[i，j]代表并存儲其相關(guān)小問題的最優(yōu)解的長度。準確地說，c[i，j]代表字串X中前面i個字符（即<x1，x2，…，xi>）和字串Y中前面j個字符（即<y1，y2，…，yj>）所形成的最長相同子字符串的長度。例如，當X=<A，T，C，T，G，A>和Y=<T，G，C，A，T，A>時，c[2，2]記錄<A，T>和<T，G>的最長相同子字符串的長度（即c[2，2]=1）；而c[3，4]記錄<A，T，C>和<T，G，C，A>的最長相同子字符串的長度（即c[3，4]=2）。當然，很容易可得c[i，0]=c[0，j]=0，因為其中的一個字符串是空的。當X和Y的字符串字尾相同時，我們可得c[i，j]=c[i-1，j-1]+1（圖3.6就是一個例子）。相對地，當X和Y的字符串字尾不相同時，c[i，j]=max（c[i-1，j]，c[i，j-1]）（見圖3.5）。以上關(guān)系可以整理如下：這個數(shù)學式子再次指出c[i，j]的值是可以利用3個小問題的值c[i-1，j-1]、c[i，j-1]和c[i-1，j]計算出來。這個關(guān)系可協(xié)助最后一個步驟的設計。步驟3：設計算法，使得在計算大問題的最優(yōu)解之前，所需要的所有小問題的最優(yōu)解都事先被計算并存儲了最后，在設計動態(tài)規(guī)劃算法時，需小心安排計算最優(yōu)解的順序，即當計算c[i，j]時，其可能需要的3個值c[i-1，j-1]、c[i，j-1]和c[i-1，j]已事先被計算并存儲起來了。如圖3.7所示，當填寫每個矩陣中的某一格時，需將其上方、左方和左上方的值先填好。圖3.7 計算c[i，j]時，其所需的3個值c[i-1，j-1]（左上方）、c[i，j-1]（左方）和c[i-1，j]（上方）需被事先計算出來。此圖中的箭頭指示出了計算最優(yōu)解的順序因此，此算法可以按照從左到右和從上而下的順序計算出所有的c[i，j]，如圖3.8所示。圖3.8 動態(tài)規(guī)劃算法須安排計算最優(yōu)值的順序按照這個方法，當X=<A，T，C，T，G，A，T>和Y=<T，G，C，A，T，A>時的所有c[i，j]的值也可計算得出，如圖3.9所示。圖3.9 和Y=<T，G，C，A，T，A>時所有c[i，j]的值表3.6列出了最長相同子字符串的動態(tài)規(guī)劃算法算法。表3.6 最長相同子字符串的動態(tài)規(guī)劃算法安排公司聚會一個問題是否可用動態(tài)規(guī)劃來解，有時不是一眼就能看出的。從表3.7來看如何進行此類的判斷。表3.7 安排公司聚會問題安排公司聚會問題可用動態(tài)規(guī)劃來解嗎？應該如何判斷？應該先判斷此問題是否有最優(yōu)子結(jié)構(gòu)性質(zhì)。什么是最優(yōu)子結(jié)構(gòu)性質(zhì)？檢查是否大問題的最優(yōu)解可以利用小問題的最優(yōu)解組合得到。若在公司找出n位員工是大問題，則小問題應該是什么？怎樣的小問題的最優(yōu)解對解大問題有幫助？已知n-1位員工的小問題的最優(yōu)解，好像對找到n位員工大問題的解幫助不大。為什么？因為公司的組織架構(gòu)未被考慮，即員工和其直屬上司不會同時參加聚會的特性。公司的組織架構(gòu)是什么？就像一棵樹（tree）。一棵樹的小問題可能是什么？應該是小樹或子樹（subtree）吧！哪些子樹的解對找到大樹的最優(yōu)解有幫助？嗯……大樹和子樹的關(guān)系是什么？樹的定義是什么？由一個樹根（root）和其子女（children）為樹根的子樹所組合而成。安排公司聚會問題的最優(yōu)子結(jié)構(gòu)判斷以表3.7的公司組織為例，1號員工（即董事長）有兩種可能，即“參加”和“不參加”聚會。如果1號員工不參加，那么以2號員工為首的部門（即以2為樹根的小樹）的最優(yōu)解（即2號員工的部門中最大快樂的聚會名單），配合以3號員工為首的部門（即以3為樹根的小樹）的最優(yōu)解，再配合4號員工所帶頭的部門（即以4為樹根的小樹）的最優(yōu)解，就是整個公司的最優(yōu)解（最優(yōu)聚會名單），如圖3.10中3個虛線方塊所示。圖3.10 當1號員工不參加聚會時的公司聚會問題若1號員工參加，則2、3、4號員工不可以參加。但是此時1號可配合5號、6號和7號員工所帶頭的下屬（即以5、6、7為樹根的小樹）的最優(yōu)解，得到最優(yōu)聚會名單，如圖3.11所示。圖3.11 當1號員工參加聚會時的公司聚會問題從這兩種（即1號員工參加或不參加）聚會名單的快樂分數(shù)中取分數(shù)高的，即可決定最優(yōu)的聚會名單。如此，我們就可以用小問題（以2、3、4、5、6、7為樹根的小樹）的最優(yōu)聚會名單找到大問題（以1為樹根的大樹）的最優(yōu)聚會名單了。因此，安排公司聚會問題具備最佳子結(jié)構(gòu)性質(zhì)，適合動態(tài)規(guī)劃法求解。安排公司聚會問題的遞歸關(guān)系接下來進行下一個步驟：使用一個數(shù)學式子描述大問題的最優(yōu)解和小問題的最優(yōu)解的關(guān)系。倘若以v為根的部門的最大快樂分數(shù)存儲于sumofhappy（v）中。當v是樹葉（leaf）時，顯然sumofhappy（v）=happy（v）。當v不是樹葉時，必有一個以上的兒子。令其所有兒子為{j1，j2，…，jc}，并令v的所有孫子（即其所有兒子的兒子）為{g1，g2，…，gd}。根據(jù)之前的討論，下列式子可以描述大問題的最優(yōu)解和小問題的最優(yōu)解的關(guān)系。上面的式子也可改寫成：安排公司聚會問題的計算順序進行最后的步驟：設計算法，使得在計算出大問題的最優(yōu)解之前，其所需要的所有小問題的最優(yōu)解都已被事先計算出。首先，因為安排公司聚會問題考慮樹狀組織架構(gòu)，需要一些變量存儲樹（公司的組織架構(gòu)）的數(shù)據(jù)。令v為此公司的樹狀組織的內(nèi)部節(jié)點（internalnode），則Tv代表以v為樹根的樹。以圖3.10為例，節(jié)點1是整棵樹的根（root），T1代表整個公司的大樹。節(jié)點2、3、4是節(jié)點1的3個兒子，而T2T3T4分別代表以2、3、4為樹根的3棵小樹。用來描述這個算法的若干變量，說明如下：·happy[v]每一個節(jié)點v將其快樂指數(shù)存于happy[v]中?！umofhappy[v]以v為根的部門（小樹）的最大快樂指數(shù)?！hildren[v，j]若children[v，j]返回true，則代表節(jié)點v為節(jié)點j的父節(jié)點。表3.8中的算法可以計算出最優(yōu)聚會名單的快樂指數(shù)總和，并存入sumofhappy[1]稍加修改，即可找出最優(yōu)聚會名單。表3.8 安排公司聚會的動態(tài)規(guī)劃算法萬一董事長不可以參加公司聚會，這樣好嗎？請人事部門調(diào)高董事長（帶給員工）的快樂分數(shù)就好了。這樣會不會太假了！太棒了，就這么辦。動態(tài)規(guī)劃的技巧如何判斷一個問題是否可用動態(tài)規(guī)劃來解？本章的4個范例指示我們使用下列步驟思考，以及使用動態(tài)規(guī)劃的技巧。判斷大問題的最優(yōu)解是否可以利用（多個）小問題的最優(yōu)解組合并解出。若可以，則嘗試寫出大問題最優(yōu)解和小問題最優(yōu)解之間的遞歸關(guān)系。哪種問題使用動態(tài)規(guī)劃特別有效率？動態(tài)規(guī)劃有什么優(yōu)點？什么是動態(tài)規(guī)劃？計算并存儲小問題的解，并將這些解組合成大問題的解。什么是動態(tài)規(guī)劃的特色？尤其是在加速計算方面的優(yōu)點。計算過的小問題不會重復計算。如此有什么好處？可以避免無謂的重復計算，以加快算法求解時所需的時間。怎樣可充分發(fā)揮動態(tài)規(guī)劃的優(yōu)點？如果計算過小問題可被很多大問題利用來求解，也許更可以發(fā)揮出動態(tài)規(guī)劃的優(yōu)點。怎樣可以知道一個小問題的解可用于組合多少個大問題的解？我好像寫過兩者之間的關(guān)系。對了，大問題最優(yōu)解和小問題最優(yōu)解之間的遞歸關(guān)系式子。最后列出一些可以被動態(tài)規(guī)劃解的問題，以供讀者參考。矩陣鏈相乘（matrix-chainmultiplication）：多于3個矩陣連乘時，不同順序的矩陣相乘所得的結(jié)果相同，但需要的乘法運算總次數(shù)不同（一般加減法較省時間，故在此不計算）。此問題要找到最少乘法運算的矩陣相乘順序。最優(yōu)多邊形三角分割（optimalpolygontriangulation）：將一個多邊形分割成多個三角形（分割點需在頂點上，且分割線不可相交），使其所需的分割線段長度總和最小。任意兩點間的最短路徑（all-pairsshortest-paths）：計算一個圖中任意兩個頂點（vertex）之間的最短路徑，此圖中不含有總和為負值的回路（cycle）。最優(yōu)二叉搜索樹（optimalbinarysearchtree）：將被搜索的值置于二叉樹（binarytree）的樹葉（leaf）索樹，使得其所需的平均搜索時間最短。資源分配問題（resourceallocationproblem）：考慮m項資源和n個計劃，當某項資源整體的利益最大。學習效果評測最長嚴格遞增子字符串：編寫一個程序，從一串整數(shù)中找出最長嚴格遞增子字符串（longeststrictlyincreasingsubsequence），即從一串整數(shù)中找到一個子集合；按照原來的順序排列時，下一個數(shù)比上一個數(shù)值大，并且此子集合個數(shù)最大（即排出來的子字符串最長）。輸入：出：-1723810（sub-rectangle），該矩陣內(nèi)所有數(shù)字的總和最大。例如，下列矩陣的解是下方的子矩陣：-10-9-2314-2420314420而且其總和為41。輸入：33 (矩陣的行數(shù)和列數(shù))-10-9 (以下是矩陣的數(shù)據(jù))-2314-2420輸出：41 (子矩陣最大總和)一臺文件服務器（fileserver）希望被布置于一個連通（connected）網(wǎng)絡的中心，使得網(wǎng)絡上其他設備可以用最少的步數(shù)（hop）得以連接此服務器。例如，當此服務器被置于A時，最遠的G最少需要花4步連接到A。但是當此服務器被置于D時，最遠的F只需要兩步即可抵達D。那么點D就是網(wǎng)絡的中心點。輸入：6 (網(wǎng)絡上點的個數(shù)，并且以1,2,3……編號)9 (網(wǎng)絡上線的條數(shù))12(以下為每一條網(wǎng)絡線的數(shù)據(jù))1423242534454656輸出：(網(wǎng)絡中心點的編號)第4章貪婪法章節(jié)大綱何謂貪婪法最小成本生成樹霍夫曼編碼樹貪婪法的陷阱：0-1背包問題單位時間工作調(diào)度問題證明貪婪法并介紹Matroid理論貪婪法的技巧何謂貪婪法什么是貪婪法（greedymethod）？簡而言之，就是重復地（或貪婪地）根據(jù)一個法則挑選解的一部分。當挑選完畢時，最優(yōu)解也就出現(xiàn)了。印度有一位農(nóng)夫在田地的河邊撿到一顆很漂亮的石頭。他將石頭帶回家給小孩玩，小孩玩膩后，就將那顆石頭隨手丟到雜物堆的角落。有一天，一位珠寶商路過他家，告訴農(nóng)夫在此附近有一條河，河里盛產(chǎn)鉆石。農(nóng)夫心想，種了一輩子的田太辛苦又賺不到錢，就決心把田地賣掉，去尋找那條產(chǎn)鉆石的河。農(nóng)夫找了好多年，無功而返。有天閑來無事整理家里時，在雜物堆里發(fā)現(xiàn)了那顆以前在河邊撿來的石頭，這才發(fā)現(xiàn)那竟是顆價值連城的大鉆石。而他多年來苦心尋找的鉆石河，正好位于他賣掉的田地內(nèi)。農(nóng)夫?qū)ふ覍毷墓适掳凳荆貉矍暗臇|西有時是最珍貴的。貪婪法一旦使用得當，會是一個有效率的策略，即便貪婪法也許無法解決所有問題。最小成本生成樹第一個例子是使用最小成本架設網(wǎng)絡的問題，如表4.1所示表4.1 最小成本網(wǎng)絡架設問題這個問題是在輸入的圖（graph）應該是尋找此圖的一部分，即子圖（sub-graph）。任意子圖都可以嗎？不！需要將所有頂點連接在一起的子圖。還有其他條件嗎？這個子圖的成本總和（sum）還必須最小。上面描述了最小成本生成樹（minimumcostspanningtree）問題：在一個有權(quán)重（weight）的圖中，尋找一個子圖（即此圖的子集合）符合下列條件：連接在一起。 [此為樹（tree）的性質(zhì)]經(jīng)過每一個頂點。 [此為生成（spanning）的性質(zhì)]連線的成本總和最小。 [此為最小成本（minimumcost）的性質(zhì)]如圖4.1所示，粗線的子圖為整個圖中一個最小成本生成樹。圖4.1 一個最小成本生成樹（粗線的子圖）在任意一個連通圖（connectedgraph）中找出其最小成本生成樹后，會發(fā)現(xiàn)此樹不含回路，而且任意地額外加入一條新的連線于此樹上，就會產(chǎn)生一個唯一的回路。如圖4.1所示，加入線（e，h）即可產(chǎn)生回路{dehi}。相反地，一旦從這棵生成樹上任意地刪除一條連線，就會造成整棵樹不連通。用構(gòu)建一個連通網(wǎng)路的問題打比方，每一棵最小成本生成樹是將網(wǎng)絡連在一起的最精簡（最省線材）的方式。如何在一個圖中找到一棵最小成本生成樹？嗯！不知道。觀察最小成本生成樹的例子（見圖4.1），試著找這些最優(yōu)解的特點？一棵生成樹是通過每一個頂點且擁有連接、成本最小及無回路的特點。利用這些特色可以找到最小成本生成樹嗎？嗯！好像不行。試著比較落在最小成本生成樹中的連線和不在其中的連線的差別？看不出來有什么差別，除了任意地額外加入一條連線在生成樹上就會產(chǎn)生唯一的回路。注意此回路，試著找出生成樹上的連線和新加入的連線之間有什么差別？似乎在此回路中新加入（即不在最小成本生成樹上）連線的成本都比回路中其他（即在最小成本生成樹上）連線的成本高。這個發(fā)現(xiàn)有助于找到一棵最小成本生成樹？也許可以先不考慮成本較大的連線，或按照連線的成本從小到大的順序構(gòu)建一個連通網(wǎng)絡。試幾個例子看看，可否找到一棵最小成本生成樹？有些例子在連接的過程中會發(fā)生回路。這種情況需要避免，因為目標是要找到一棵樹，而樹是無回路的。目前你有什么想法？按照連線的成本從小到大的順序連通整個網(wǎng)絡，同時需要避免發(fā)生回路。Kruskal的最小成本生成樹的算法是：按照連線的成本，從小到大按序選擇連線連通整個網(wǎng)絡，但是在此過程中需避免發(fā)生回路。以圖4.1為例，此算法的執(zhí)行過程如圖4.2所示。圖4.2 Kruskal最小成本生成樹算法的執(zhí)行范例圖4.2 Kruskal最小成本生成樹算法的執(zhí)行范例（續(xù)）圖4.2 Kruskal最小成本生成樹算法的執(zhí)行范例（續(xù)詳細的Kruskal最小成本生成樹算法如表4.2所示。表4.2 Kruskal最小成本生成樹的算法Kruskal最小成本生成樹算法還有一個步驟需要進一步討論，如圖4.3所示。圖4.3 當線（e，h）加入時會造成回路當一連線（e，h）加入時，如何判斷T∪{（e，h）}會不會形成回路？試著觀察一個例子。好像是判斷兩個欲選的連線的兩端點是否已經(jīng)相連了。如何判斷兩頂點已經(jīng)相連了？只要檢查兩頂點是否已經(jīng)有一條路連通即可。如何檢查兩頂點間是否有一條路連通？嗯……所有連通的點有什么共同性質(zhì)？所有連通的頂點彼此互相連接。如何記錄這種關(guān)系？將所有相連的頂點用一個集合記錄。這個關(guān)系什么時候會被改變？當加入的新連線連通兩個不同的集合時。此時關(guān)系會有怎樣的改變？這兩個原來是不同的集合，因為新加入的連線，導致這兩個集合的所有頂點都彼此可以連通在一起，因此可以將這兩個集合并集成一個大的集合?？梢杂镁仃嚧鎯?。嗯……為何選中|V|-1條連線后，此算法即可停止？因為已經(jīng)找到一棵生成樹了。|V|個頂點的生成樹有多少條連線？好像是|V|-1。這個算法是對的嗎？其時間復雜度為多少？嗯……Kruskal最小成本生成樹算法的時間復雜度為O（|E|log|E|），如表4.3所示。注意Step3需運用較有效率的集合并集（union）和查找（find）的數(shù)據(jù)結(jié)構(gòu)。表4.3 Kruskal最小成本生成樹算法的時間復雜度霍夫曼編碼樹若將一份文本文件進行數(shù)據(jù)壓縮（datacompression）后，再上傳到網(wǎng)絡上，可以減少傳輸時間和成本。編碼樹用一棵二叉樹（binarytree）表示編碼的方法。如圖4.4所示，每個被編碼的符號被置于此二叉樹的樹葉（leaf）上，而且樹上的每一條連線被標上一個二進制位（bit）的0（向左的連線）或1（向右的連線）。圖4.4 編碼樹在一棵編碼樹上，從樹根（root）走到一個特定的樹葉（leaf）會形成一條唯一的路徑。收集這條路徑各個連線上的0與1數(shù)字串，也就是此樹葉上的符號所對應的編碼。例如，圖4.4中的F對應1001，而D對應101。不同的編碼樹會有不同的編碼方式，也會產(chǎn)生不同的數(shù)據(jù)壓縮效果。如果知道每個符號在傳送數(shù)據(jù)中出現(xiàn)的次數(shù)，如何構(gòu)造出一棵最優(yōu)的編碼樹將傳送的數(shù)據(jù)壓縮成最少的位，就成為一個值得探討的問題，如表4.4所示?；舴蚵幋a（Huffmancode）就是其中一種方法。表4.4 構(gòu)造最優(yōu)的編碼樹編碼樹的數(shù)據(jù)壓縮效果與什么有關(guān)系？符號出現(xiàn)的次數(shù)對此符號在最優(yōu)編碼樹上出現(xiàn)的位置有何影響？嗯……出現(xiàn)最多次數(shù)的符號應該放在編碼樹的什么地方？當然是越靠近樹根（root）越好！因為這樣對應的位數(shù)總和會越少。出現(xiàn)最少次數(shù)的符號應該放在編碼樹的什么地方？越靠近樹葉（leaf）越好，這樣可把靠近樹根的位置留給出現(xiàn)較多次數(shù)的符號。按此想法，如何構(gòu)造一棵最優(yōu)的編碼樹？根據(jù)符號出現(xiàn)的頻率安排出現(xiàn)在樹上的位置：即在樹的上層放置常出現(xiàn)的符號，在樹的下層放置較少出現(xiàn)的符號。一開始要怎么做？也許可以將最少出現(xiàn)的兩個符號放在樹的最下層?；舴蚵幋a樹就是貪婪地以“出現(xiàn)最少次數(shù)的兩個符號放在樹的最下層”的方法所構(gòu)造出的一棵最優(yōu)的編碼樹。下面使用一個范例說明。步驟1 一開始整個集合包含所有符號，將每個符號的權(quán)重設置成其出現(xiàn)的次數(shù)，并且照權(quán)重從小到大排列，如圖4.5所示。圖4.5 構(gòu)造霍夫曼編碼樹算法的過程之一步驟2 將集合中出現(xiàn)最小權(quán)重的兩個符號E（權(quán)重1）和F（權(quán)重2）取出，合并成一棵叉樹（binarytree）后，將此樹的權(quán)重設為E和F權(quán)重的和（即1+2=3），并按照權(quán)重從小到大的順序插入原順序中，如圖4.6所示。圖4.6 構(gòu)造霍夫曼編碼樹算法的過程之二步驟3 將集合中出現(xiàn)最小權(quán)重的樹（權(quán)重3）和D（權(quán)重5）取出，合并成一棵二叉樹將此新樹的權(quán)重設為8（=3+5），并按照權(quán)重從小到大插入原順序中，如圖4.7所示。圖4.7 構(gòu)造霍夫曼編碼樹算法的過程之三步驟4 將集合中出現(xiàn)最小權(quán)重的B（權(quán)重6）和C（權(quán)重7）取出，合并成一棵樹后，并此新樹的權(quán)重設為13（=6+7），再次放回原順序中，如圖4.8所示。圖4.8 構(gòu)造霍夫曼編碼樹算法的過程之四步驟5 將集合中出現(xiàn)最小權(quán)重的樹（權(quán)重8和權(quán)重13）取出，合并成一棵樹（其權(quán)重設為21）后，依次放回原集合，如圖4.9所示。圖4.9 構(gòu)造霍夫曼編碼樹算法的過程之五步驟6 將集合中剩下的兩個字符合并成一棵樹后，放回原集合。此新樹的權(quán)重為35（=14+21），如圖4.10所示。圖4.10 構(gòu)造霍夫曼編碼樹算法的構(gòu)造結(jié)果構(gòu)造霍夫曼編碼樹的貪婪算法如表4.5所示表4.5 構(gòu)造霍夫曼編碼樹的算法構(gòu)造霍夫曼編碼樹的時間復雜度分析如表4.6所示表4.6 構(gòu)造霍夫曼編碼樹的時間復雜度分析貪婪法的陷阱：0-1背包問題當貪婪法使用得當（如前兩節(jié)所述）時，會是一個有效率的策略。但是，目前并非所有問題都可用貪婪法解決。下面介紹的0-1背包問題（0-1Knapsackproblem）就是一個例子，如表4.7所示。表4.7 0-1背包問題直覺上，貪婪地挑選當前最有價值且輕的商品，會有最優(yōu)解，也就是從大到小按照{(diào)價值/重量}的值挑選。表4.8就是一個0-1背包問題的例子，表4.8的解析如圖4.11所示。圖4.11 表4.8的解析表4.8 0-1背包問題的一個范例令袋子的重量限制W=50。若按照從大到小{價值/重量}的值挑選，則選入袋子的商品為d1和d2，而總價值為60+100=160。注意，此刻d3不可同時納入，否則總重量為60，就超過袋子的負荷（W=50）了。但可惜的是，此解并非最優(yōu)。若取d2和d3，則總價值為100+120=220，且總重量為20+30=50，并未超過袋子的負荷。從上例可知，使用貪婪法未能成功地解答0-1背包問題。當每件商品可任意被取走一部分時（如取走商品d1的35%），這類背包問題被稱為部分背包問題（fractionalknapsackproblem）。有趣的是，部分背包問題可以使用上述貪婪法找到最優(yōu)解。注意，當最后取一件完整商品會超過袋子的負荷限制時，此法只取這種商品的一部分，使得整個袋子裝滿即可。單位時間工作調(diào)度問題當前知道的貪婪法可解的問題有最小成本生成樹、構(gòu)造最優(yōu)的編碼樹，而貪婪法尚未成功解決的問題有0-1背包問題。本節(jié)再介紹一個貪婪法可解的問題——單位時間工作調(diào)度問題，以突顯判斷一個問題是否可用貪婪法來解是一個極需思考的議題，如表4.9所示。表4.9 單位時間工作調(diào)度問題首先，我們通過下列討論，希望可以構(gòu)思這個問題的解決方法。若要繳納最少罰金，怎樣的工作需要先安排？應該是期限早到期的工作或罰金較多的工作。這兩類工作哪一種需要先安排？嗯……如果期限早到期的工作先安排，會有什么缺點？應該是當罰金較多的工作想要先安排時，卻被期限早到期的工作占用了機器?！毕喾吹?，如果罰金較多的工作先安排，會有什么缺點？應該是當期限早到期的工作想要先安排時，卻被罰金較多的工作占用了機器。回到原來的問題，這兩類的工作哪一種需要先安排？嗯……調(diào)度的目的是什么？找到繳納罰金最少的調(diào)度。哪一種調(diào)度最有可能繳納較少罰金？嗯……每一種調(diào)度下，被處罰的工作罰金的情況是怎樣的？我想一下。第一種調(diào)度當罰金較多的工作想要先安排時，卻被期限早到期的工作占用了機器，罰的是罰金較多的工作；相對地，第二種調(diào)度當期限早到期的工作想要先安排時，卻被罰金較多的工作占用了機器，罰的是期限早到期的工作。哪一種調(diào)度最有可能繳納較少罰金？嗯，也許應該先不用第一種調(diào)度。不必先承受罰金較多的處罰，如果使用第二種調(diào)度，罰的就是期限早到期的工作，也許繳的罰金比較少。將罰金較多的工作先安排的方法可以設計出一個貪婪算法。下面使用一個范例說明步驟1 將所有工作按照罰金的大小排列好。步驟2 按照Step1所得的順序，將每件工作一一運用下列步驟判斷是否加入當前的工作度中。步驟2.1 將工作1排入排程日期。步驟2.2 試著將工作2排入排程日期，因其期限為2（比工作1的期限4早），故將工作2于工作1之前。步驟2.3 工作3和工作4排入排程日期時，也按其期限先后排入。步驟2.4 若要將工作5排入排程日期，則因其期限為1，需將前面的工作2、4、1及3的排程日期都向后推一日，但會造成