算法設(shè)計與分析第4章

1、 設(shè)有設(shè)有n n個活動的集合個活動的集合E=1,2,nE=1,2,n，其中每個活動都，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內(nèi)只有要求使用同一資源，如演講會場等，而在同一時間內(nèi)只有一個活動能使用這一資源。每個活動一個活動能使用這一資源。每個活動i i都有一個要求使用都有一個要求使用該資源的起始時間該資源的起始時間sisi和一個結(jié)束時間和一個結(jié)束時間fi,fi,且且si fisi fi 。如果。如果選擇了活動選擇了活動i i，則它在半開時間區(qū)間，則它在半開時間區(qū)間si, fi)si, fi)內(nèi)占用資源。內(nèi)占用資源。若區(qū)間若區(qū)間si, fi)si, fi)與區(qū)間與區(qū)間sj, f

2、j)sj, fj)不相交，則稱活動不相交，則稱活動i i與活與活動動j j是相容的。也就是說，當(dāng)是相容的。也就是說，當(dāng)sifjsifj或或sjfisjfi時，活動時，活動i i與與活動活動j j相容。相容。下面給出解活動安排問題的貪心算法GreedySelectorGreedySelector 描述:各活動的起始時間和結(jié)各活動的起始時間和結(jié)束時間存儲于數(shù)組束時間存儲于數(shù)組s s和和f f中且按結(jié)束時間的非減中且按結(jié)束時間的非減序排列序排列 所謂所謂是是指所求問題的指所求問題的可以可以通過一系列通過一系列的選擇的選擇，即貪心選擇來達到。這是，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也

3、是貪心算法與動態(tài)貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。規(guī)劃算法的主要區(qū)別。 動態(tài)規(guī)劃算法通常以動態(tài)規(guī)劃算法通常以的方式解各子問題，的方式解各子問題，而貪心算法則通常以而貪心算法則通常以的方式進行，以迭代的方的方式進行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。題簡化為規(guī)模更小的子問題。 對于一個具體問題，要確定它是否具有貪心選擇性對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解

4、。體最優(yōu)解。3、貪心算法與動態(tài)規(guī)劃算法的差異 這這2 2類問題都具有類問題都具有性質(zhì)，極為相似，但性質(zhì)，極為相似，但背包問題可以用貪心算法求解，而背包問題可以用貪心算法求解，而0-10-1背包問題卻不能背包問題卻不能用貪心算法求解。用貪心算法求解。 用貪心算法解背包問題的基本步驟： 算法算法knapsackknapsack的的主要計算時間在于將主要計算時間在于將各種物品依其單位重各種物品依其單位重量的價值從大到小排量的價值從大到小排序。因此，算法的計序。因此，算法的計算時間上界為算時間上界為O O（nlognnlogn）。）。為了證明算法的正確為了證明算法的正確性，還必須證明背包性，還必須證明

5、背包問題具有貪心選擇性問題具有貪心選擇性質(zhì)質(zhì)。102030501.￥60 2.￥100 3.￥120 4.背包 =￥220=￥160=￥180=￥240100201203060101002060101203060101002080201202030 0-1背包問題 背包問題 11max011niiniiiixw xcxin=危，1min |1ii nki x=1111nnniikiiiiiiiw ywww xw xc=-+邋11nniiiiyx=邋( )( )( )Tc CB Tf c dc= DijkstraDijkstra算法的迭代過程：算法的迭代過程： 賦權(quán)圖的鄰接表賦權(quán)圖的鄰接表)(n

6、O)(2nO)(2nO 可以用反證法來證明這個MST性質(zhì)： 假設(shè)不存在這樣一棵包含邊（u , v）的最小生成樹。 任取一棵最小生成樹T，將（u , v）加入T中。根據(jù)樹的性質(zhì)，此時T中必形成一個包含（u , v）的回路， 且回路中必有一條邊（u, v）的權(quán)值大于或等于（u , v）的權(quán)值。 刪除（u, v），則得到一棵代價小于等于T的生成樹T，且T為一棵包含邊（u , v）的最小生成樹。 這與假設(shè)矛盾， 故該性質(zhì)得證。 uuvvV1V2V4V5V3V66555662134V1V2V4V5V3V61V1V2V4V5V3V614V1V2V4V5V3V6142V1V2V4V5V3V61425V1V2V4V5V3V614253)(2nOV1V2V4V5V3V66555662134V1V2V