欧美人妻另类专区,佐山爱中文字幕AV

17. 1引言

首先通過對一個簡單理論的討論，初步理解貪婪思想。以下棋為例，每一步的決策都需要考慮對后續(xù)棋局的影響。而在網(wǎng)球(或排球)比賽中，選手的行為僅取決于當(dāng)前的狀況，選擇當(dāng)下最為正確的動作，而不關(guān)心后續(xù)的影響。這說明在某些情況下選擇當(dāng)下最佳行為的決策，可以得到一個最優(yōu)解(貪婪)，但并非所有情況都如此，貪婪策略適用于上述第二類問題。

17. 2貪婪策略的定義

貪婪算法將問題分為多個階段。在每一個階段，選取當(dāng)前狀態(tài)下的最優(yōu)決策，而不考慮對后續(xù)決策的影響。這意味著算法在執(zhí)行過程中會選取某些局部最優(yōu)解。貪婪法假.設(shè)通過局部最優(yōu)解可以獲得全局最優(yōu)解。

17.3貪婪算法的要素

最優(yōu)貪婪算法需要滿足兩個基本性質(zhì):

貪婪選擇性質(zhì)。

最優(yōu)子結(jié)構(gòu)。

貪婪選擇性質(zhì):全局最優(yōu)解可以通過尋找局部最優(yōu)解獲得(貪婪)，局部最優(yōu)解的選擇可能依賴于之前的決策，而不是后續(xù)的決策。通過迭代方式算法進(jìn)行一一個個貪婪選擇，將原問題簡化為規(guī)模更小的問題。

最優(yōu)子結(jié)構(gòu):如果原問題的最優(yōu)解包含子問題的最優(yōu)解，則認(rèn)為該問題具有最優(yōu)子結(jié)構(gòu)。這意味著可以對子問題求解并構(gòu)建規(guī)模更大問題的解。

17.4貪婪算法的適用范圍

選擇局部最優(yōu)解不是對于所有問題都適用，所以貪婪算法并不總是能得到最優(yōu)解。在17.8節(jié)和第19章將給出這樣的例子。

17.5貪婪算法的優(yōu)缺點

貪婪算法的優(yōu)點是直觀，易于理解，并易于編碼實現(xiàn)。當(dāng)前的決策不會對已經(jīng)計算出的結(jié)果有任何影響，因此不需要再對已有的局部解進(jìn)行檢查。缺點是，對于許多問題，無法用貪婪算法求解。即在許多情況下，無法保證局部最優(yōu)解能夠產(chǎn)生全局最優(yōu)解。

17.6 貪婪算法的應(yīng)用

排序問題:選擇排序、拓?fù)渑判颉?/p>

優(yōu)先隊列:堆排序。

赫夫曼編碼壓縮算法

Prim和Kruskal算法。

加權(quán)圖的最短路徑問題(Dijkstra算法)。

硬幣找零問題

分?jǐn)?shù)背包問題。

并查集的按大小或高度合并問題(或排名)。

任務(wù)調(diào)度算法。

貪婪算法可用于求解復(fù)雜問題的近似算法。

17.7貪婪思想

本節(jié)通過-一個例子來更好地理解貪婪思想，更多細(xì)節(jié)參見17.6節(jié)的相關(guān)主題。赫夫曼編碼算法

定義:給定來自字母表A的n個字符的集合(字符c∈A)，并已知每個字符出現(xiàn)的頻率freq(c)，為每-一個字符c∈A找到一個二進(jìn)制編碼，使得> freq(c) | binarycode(c) |c∈A的值最小，其中| binarycode(c) |表示字符c的二進(jìn)制編碼的長度。以上公式表明所有字符編碼長度之和(每個字符出現(xiàn)頻率與編碼的位數(shù)乘積之和)最小。

赫夫曼編碼算法的基本思想是，對于出現(xiàn)頻率較大的字符用更少的位來編碼。利用可變長度編碼，赫夫曼算法可以壓縮數(shù)據(jù)存儲所需的空間。計算機系統(tǒng)采用8位來表示每一個字符，但并非所有的位都被使用。此外，某些字符的使用更為頻繁。當(dāng)讀取一個文件時，系統(tǒng)通常每次讀取8位來確定-一個字符。但是這種8位編碼機制是低效的，因為相比而言，有些字符使用更為頻繁。例如，字符‘e'往往比字符‘q'的使用頻率高10倍。

因此，如果對于字符‘e'用7位編碼，而‘q'用9位編碼，這將減少整個消息的長度。平均而言，對于標(biāo)準(zhǔn)文件，使用赫夫曼編碼在長度上能夠減少10%~30%，具體的值取決于字符的頻率。這種編碼思想是，對于較少使用的字符或字符組采用較長的二進(jìn)制編碼。此外，赫夫曼編碼滿足任意兩個字符的編碼互不為前綴。

例子:假設(shè)掃描一個文件，得出以下字符頻率:

首先，為每一個字符創(chuàng)建- - 棵二叉樹，并將其出現(xiàn)頻率存儲在結(jié)點中(見下圖)。

赫夫曼算法的流程如下:在列表中尋找根結(jié)點中存有最小頻率值的兩棵二叉樹，創(chuàng)建一個不存儲任何字符的結(jié)點，將這兩棵二叉樹作為新建結(jié)點的左右子樹，并將其孩子結(jié)點的頻率值之和存儲到新建結(jié)點中。由此可以得出下圖:

重復(fù).上述過程直至僅剩下一棵樹。

當(dāng)樹構(gòu)造完后，每一個葉子結(jié)點對應(yīng)于一個字母及其編碼。從根結(jié)點遍歷到葉子結(jié)點，就可以得到每一一個結(jié)點的編碼。對于左分支，在編碼中添加0;對于右分支，添加1。對于.上述產(chǎn)生的樹，可以得到以下編碼:

計算減少的位數(shù):接下來對使用赫夫曼編碼減少的位數(shù)進(jìn)行統(tǒng)計，只需要用原始的數(shù)據(jù)存儲位數(shù)減去采用赫夫曼編碼后的存儲位數(shù)。

在本例中，由于僅有6個字母，所以假設(shè)每個字母用3位進(jìn)行編碼。因為共有133個字符(總頻率乘以3)，所以需要的總位數(shù)為3X133=399。使用赫夫曼編碼，所需要的位數(shù)是:

因此，減少了399-238=161位，將近減少40%的存儲空間。

HuffmanCodingAlgorithm(int A], int n) {

//在A中初始化一個包含n個元素的優(yōu)先隊列PQ;

Heap PQ = new Heap0;

BinaryTreeNode temp;

for (i= 1;i<n; i++) {

temp = new BinaryTreeNode);

temp.setLeft(PQ .deleteMin();

temp.setRight(PQ.DeleteMin();

temp.setData(temp.getLeft0.getData) + temp.getRight).getData0);

PQ.insert(temp);

}

return PQ;

}

時間復(fù)雜度為O(nlogn)，其中包含在不超過n個元素的優(yōu)先隊列上的--個建堆操作，2n-2次堆刪除操作和n-2次堆插入操作，詳見第7章。

17. 8貪婪算法的相關(guān)問題

問題1給定一個大小為n的數(shù)組F，數(shù)組元素F[i]表示第i個文件的長度?，F(xiàn)在需要將所有文件合并成一個文件，以下算法是否提供了該問題的最優(yōu)解?

算法:依次連續(xù)合并文件，即按照默認(rèn)順序選擇最前兩個文件進(jìn)行合并，然后將合并后的文件與第三個文件合并，以此類推。

注意:給定大小分別為m和n的兩個文件A和B，則合并的復(fù)雜度為O(m+n)。

解答:上述算法不是最優(yōu)的求解算法。下面給出反例，假設(shè)文件大小的數(shù)組F如下。

F= {10,5, 100,50,20,15}

根據(jù)上述算法，首先合并前兩個文件(大小分別為10和5)，合并后的文件列表如下，其中15表示合并大小為10和5兩個文件的代價。

{15,100 ,50 ,20,15}

同理，合并大小為15的文件和下一個大小為100 的文件，得到{115，50，20， 15}。以此類推，產(chǎn)生的文件列表如下:

{165,20,15}

{ 185,15}

最后為

{200}

合并的總代價=所有合并代價之和=15+115+ 165+ 185 + 200=680。為了確定上述結(jié)果是否是最優(yōu)解，考慮文件的另一種排列: {5，10，15，20，50，100}。對于該例，同樣按照上述過程，合并總代價=15+30+ 50+ 100+ 200=395。因此，該算法不能給出最優(yōu)的解決方法。

問題2與問題1類似，以下算法是否給出問題的最優(yōu)解?

算法:兩兩合并文件，即將文件依次兩兩分組合并。第一輪后，產(chǎn)生n/2個中間文件。接下來，將上一輪產(chǎn)生的中間文件兩兩分組合并，以此類推。

注意:有些文獻(xiàn)將上述算法稱為兩路歸并。若不是兩兩分組，而是一次合并K個文件，則稱為K路歸并。

解答:上述算法仍然不是最好的求解算法。仍然以上題中給出的例子作為反例進(jìn)行說明。根據(jù)算法思想，第-輪中對第- -組(文件大小為10和5)、第二組(文件大小100和50)、第三組(20和15)分別合并，得到以下文件列表。

{15,150,35}

同理，將以上文件列表兩兩分組合并，結(jié)果為(最后一個分組中僅包含一個元素，結(jié)果保持不變):

{165,35}

最后為

{ 185}

合并的總代價=所有合并代價之和=15+150+ 35+165+ 185=550。該代價高于395(見問題1)，因此上述算法不能給出最好的解決方法。

問題3對于問題1，將所有文件合并為一-個文件最好的方法是什么?

解答:使用貪婪算法降低文件合并的總時間。

算法:

1)按照文件的大小構(gòu)建一個優(yōu)先隊列，元素的關(guān)鍵值為文件長度。

2)重復(fù)以下步驟直至隊列中只有一個文件，

a. 選擇兩個最小的元素X和Y。

b. 將X和Y合并，并將合并后的新文件插入優(yōu)先隊列中。

同樣算法的變形:

1)將所有文件按照文件大小進(jìn)行升序排序。

2)重復(fù)以下步驟直至只有一個文件，

a.選擇有序表中最前的兩個元素(最小)X和Y。

b.合并X和Y，并將合并后的文件插入有序表中。

通過對前面例子的分析來分析上述算法的性能。已知數(shù)組

F= {10,5,100,50,20,15}

根據(jù)上述算法，對數(shù)組進(jìn)行排序得到{5，10， 15，20，50，100}。合并兩個最小的文件(大小分別為5和10)，結(jié)果如下所示，其中15表示合并大小為10和5兩個文件的代價。

{15,15,20,50, 100}

同理，繼續(xù)合并兩個最小的文件(大小為15 和15)，得到{20，30， 50，100}。接下來，依次得到以下文件列表:

{50,50,100} //合并20和30

{100,100} //.合并20和30

最后為

{200}

合并的總代價=所有合并代價之和=15+ 30+ 50+ 100+ 200= 395。因此，該算法得到該合并問題最好的解決方法。

時間復(fù)雜度:使用堆查找最佳合并模式的時間開銷O(nlogn)加上文件合并的最低代價。

問題4區(qū)間調(diào)度算法: 給定一個含n個區(qū)間的集合S={(start;，end;)| 1≤i≤n}，尋找S的一個最大子集S'，使得S'中任意- -對區(qū)間都不重合。分析以下算法是否可行?

算法:

while(S非空){

選擇與其他區(qū)間重合數(shù)最少的區(qū)間I;

將I添加到最終解集合S'中;

將所有與I有重合的區(qū)間從S中刪除;

}

解答:該算法不能找到非重合區(qū)間的最大子集?？紤]以下區(qū)間，其最優(yōu)解是{M, O,N，K}。然而，與其他區(qū)間重合數(shù)最小的是C,因此該算法首先選取C。

問題5對于問題 4，如果選擇最先出現(xiàn)的區(qū)間(并且與已經(jīng)選擇的區(qū)間不重合)，則該算法是否能給出最優(yōu)解?

解答:不能。該算法也不能給出最優(yōu)解。反例如下，最優(yōu)解為4，而該算法得到的解為1。

問題6對于問題4，如果選擇最短的區(qū)間(并且與已經(jīng)選擇的區(qū)間不重合)，此算法是否能給出最優(yōu)解?

解答:該算法同樣不能給出最優(yōu)解。反例如下，最優(yōu)解為2，而該算法得到的解為1。

問題7那么對于問題4，最優(yōu)解是什么?

解答:考慮使用貪婪算法尋找最優(yōu)解。

算法:

將所有區(qū)間按照最右端(結(jié)束時間)進(jìn)行排序

對每一個連續(xù)的區(qū)間{

如果其最左端在，上一一個選擇區(qū)間的最右端之后，則選取該區(qū)間否則，舍棄該區(qū)間，進(jìn) 入下一次迭代

}

時間復(fù)雜度=排序的時間+掃描的時間=O(nlogn+n)=O(nlogn)。

問題8考慮如下問題。

輸入:區(qū)間集合S= {(start;，end;) |1≤i≤n}。區(qū)間(start;，end;)表示在時間段start;到end;，某個課程在某個教室上的一一個使用申請。

輸出:尋找所有課程的教室安排方案，使得占用教室最少。

算法:安排盡可能多的課程到第一間教室，然后安排盡可能多的課程到第二間教室,然后安排盡可能多的課程到第三間教室，以此類推。這個算法能否給出最優(yōu)解?

注意:實際上，該問題與區(qū)間調(diào)度問題類似，只是應(yīng)用背景不一樣。

解答:.上述算法未解決區(qū)間著色問題，考慮如下例子:

最大化第一間教室安排的課程數(shù)，則{B, C, F, G}在同一間教室，課程A、D和E分別各占一-間教室，共需4間教室。最優(yōu)方案是將A安排在一間教室，{B, C，D}安排在一間教室，{E，F(xiàn), G}安排在一間教室，共3間。

問題9對于問題8，考慮如下算法。根據(jù)課程開始時間按遞增順序依次處理，假設(shè)當(dāng)前正在為課程C安排教室，如果教室R已經(jīng)安排了C之前的課程，且將C安排到R不會與之前安排的課程重疊，那么將課程C安排到教室R，否則將C安排到一個新教室。這個算法能否解決該問題呢?

解答:上述算法能夠解決區(qū)間著色問題。因為算法按照課程開始的時間順序進(jìn)行教室的安排，所以如果該貪婪算法為當(dāng)前課程c;安排了一間新教室，這意味著c;的開始時間與所有已使用教室的最后一門課程的時間沖突。因此貪婪算法安排最后--間教室n，因為當(dāng)前課程的開始時間與其他n-1間教室的課程相沖突。假設(shè)任何時刻，任何課程最多只與s門課程沖突，則必有n≤s，即s是所需教室總數(shù)的下界。綜上可知，貪婪算法是可行的，可以給出最優(yōu)解。

注意:求最優(yōu)解的算法參見問題7，代碼參見問題10。

問題10假設(shè)兩個數(shù)組Start[1..n]和Finish[1..n]分別給出每一個課程的開始時間和結(jié)束時間，現(xiàn)在需要尋找最大的子集X∈{1, 2，..，n}，使得其中任意兩個元素i, j∈X滿足Start[i]> Finish[j]或Start[i]> Finish[i]。

解答:目標(biāo)是盡可能早地完成第一門課，這樣為其他課程騰出更多的時間。按照結(jié)束時間的順序輪詢每一門課程，當(dāng)時間不與上一門已選課程相沖突時，選擇該門課程。

容易看出，該算法由于排序需要O(nlogn)的時間開銷。

問題11思考印度的貨幣找零問題。問題的輸入為整數(shù)M,輸出為兌換M盧比所需的最少硬幣數(shù)。在印度，假設(shè)可用的硬幣面額有1、5、10、20、25、50盧比，并且每--種面值的硬幣數(shù)量不限。

對于該問題，以下算法能否給出最優(yōu)解?

盡可能取用面額最高的硬幣，例如，兌換234盧比的零錢，貪婪算法將使用4個面額50盧比的硬幣，1個25盧布的硬幣，1個5盧比的硬幣和4個1盧比的硬幣。

解答:對于面額為1. 5、10、20、25、50盧比的硬幣找零問題，上述貪婪算法不能給出使硬幣數(shù)最少的最優(yōu)解。為了兌換40盧比的硬幣，貪婪算法的結(jié)果為3個硬幣，面額分別為25、10和5盧比，而最優(yōu)解則為使用兩個20先令的硬幣。

注意:對于該問題的最優(yōu)解，參見第19章。

問題12假設(shè)在城市 A和B進(jìn)行長途自駕之旅。在準(zhǔn)備旅行時，下載了一-份包含自駕路線上所有加油站之間距離(以英里為單位)的地圖。假設(shè)汽車的油箱能裝載使汽車行駛n英里的汽油(n為已知)。如果在每一個加油站都停車加油，是否是最優(yōu)解?

解答:_上述算法不能給出最優(yōu)解。原因很明顯，在每-一個加油站均加油不能產(chǎn)生最優(yōu)解。

問題13對于問題 12，當(dāng)且僅當(dāng)沒有足夠到下一個加油站的汽油時才停車，并且一旦停車，則將油箱加滿油。證明該算法能夠或不能解決上述問題。

解答:貪婪算法策略如下:將油箱裝滿油，從A開始旅行，根據(jù)地圖決定在旅行路線.上n英里以內(nèi)最遠(yuǎn)的加油站，在該加油站停車并加滿油，然后再次根據(jù)地圖決定從該停車點出發(fā)n英里以內(nèi)最遠(yuǎn)的加油站，重復(fù)該過程直至到達(dá)B。

注意:算法代碼參見第19章。

問題14分?jǐn)?shù)背包問題: 有t，t2， ..，t,件物品(希望放入背包的物品)，其重量分別為s]，S2，..，sn，同時每件物品的回報值為U，Vr，...，Vn，在物品凈重不超過C的前提下如何最大化回報值?

解答:

算法:

1)為每件物品計算單位重量的價值密度d;= v;/s;。

2)根據(jù)以上價值密度對物品進(jìn)行排序。

3)盡可能多地將價值密度大的物品放入背包中。

時間復(fù)雜度:排序為O(nlogn)，貪婪選擇為O(n)。

注意:將物品放入一個優(yōu)先隊列，然后一個一個拿出放入背包中直至背包裝滿或者所有的物品被取出。實際上，這將獲得一個更好的運行時間復(fù)雜度O(n+clogn)，其中c為被選取物品的實際數(shù)量。如果c=O(n)，則運行時間會繼續(xù)減少，否則復(fù)雜度不變。

問題15火車站臺數(shù): 一個火車站有一個所有火車到達(dá)和離開的時間表，需要找出最小的站臺數(shù)，使得按照此時間表調(diào)度時，可以容納所有的火車。例如，如下的時間表，最小站臺數(shù)為3，否則車站將無法容納所有的火車。

解答:從上面給出的例子可以看出，計算站臺的數(shù)目等同于確定車站在任一時刻容納的最大火車數(shù)。

首先，在一個數(shù)組中對到達(dá)時間(A)和離開時間(D)進(jìn)行排序，將相應(yīng)的到達(dá)或離開狀態(tài)也保存在數(shù)組中。排序后的數(shù)組如下表所示。

其次，將數(shù)組中的A替換為1，D換成一1，替換后的數(shù)組為:

最后，根據(jù)上述數(shù)組計算-一個累積值數(shù)組:

數(shù)組中的最大值即為問題的解，這里是3。

注意:如果一列火車的到達(dá)時間與另一列火車的離開時間相同，則在排序數(shù)組中離開時間優(yōu)先。

問題16假設(shè)某個國家有很長的馬路，居民的房子分散在馬路兩旁。居民使用移動電話，需要沿著馬路架設(shè)移動電話基站，每- - 個基站覆蓋范圍為7千米。設(shè)計一個有效算法，使得需要的基站數(shù)最少。

解答:該算法用于定位最少數(shù)量的基站。

1)從馬路起點處開始。

2)找到馬路上第-一個未被覆蓋的房子。

3)如果找不到這樣的房子，則算法終止，否則轉(zhuǎn)到下一步。

4)沿著馬路在距離步驟2中的房子7英里處架設(shè)基站。

5)轉(zhuǎn)到步驟2。

問題17準(zhǔn)備音樂磁帶: 假設(shè)有n首歌曲，需要將其存儲到一盤磁帶中。以后用戶需要從磁帶中讀取這些歌曲，但從磁帶中讀一首歌曲與從磁盤中讀取的方式不同。首先需要快進(jìn)越過其他歌曲，這需要花費大量的時間。假設(shè)數(shù)組A[1..n]列出了每一首歌曲的長度，例如歌曲i的長度為A[門。如果歌曲按照1~n的順序存儲，那么訪問第k首歌曲的開銷為:

這個開銷表明在訪問第k首歌曲之前需要越過磁帶前面的所有歌曲。如果改變磁帶上歌曲的順序，則訪問歌曲的開銷也隨之改變。有些歌曲的訪問變得非常耗時，而另一些則非常容易。不同的歌曲順序可能導(dǎo)致不同的期望開銷。如果假設(shè)每一首歌曲訪問的可能性是相等的，那么采用何種歌曲順序能夠使得期望開銷盡可能小?

解答:答案非常簡單，按照從最短歌曲到最長歌曲的順序存儲，將較短的歌曲存儲在靠前的位置減少了訪問剩余歌曲的快進(jìn)時間。

問題18考慮海德拉巴會議中心( Hyderabad Convention Center，HITEX)的一組活動安排，假設(shè)有n項活動，每項活動需要一個單位時長。如果活動i在時間T[i]或之前開始，則可以創(chuàng)收P[i]盧比(P[i]>0)，其中T[i]為-一個任意數(shù)字。如果直至T[i]活動還沒開始，則無任何收入。所有活動最早開始時間為時刻0。設(shè)計一個有效算法，找到一個收入最大的活動調(diào)度方案。

解答:算法

根據(jù)floor(T[i])對所有活動進(jìn)行排序(從大到小)。floor()表示下取整函數(shù)。

令t為當(dāng)前調(diào)度時刻(初始時t=floor(T[i]))。

所有floor(T[i])=t 的活動插入一一個優(yōu)先隊列，其收入g;作為關(guān)鍵字。

執(zhí)行DeleteMax操作選取--個在時刻t開始的活動。

然后t自減，重復(fù)上述過程。

顯然時間復(fù)雜度為O(nlogn)，其中排序花費O(nlogn)，算法中包含最多n次優(yōu)先隊列的插入和DeleteMax操作，每--個操作花費0(logn)。