《算法設計與分析》第06章.ppt

《《算法設計與分析》第06章.ppt》由會員分享，可在線閱讀，更多相關《《算法設計與分析》第06章.ppt（112頁珍藏版）》請在裝配圖網上搜索。

1、,第2部分 算法設計策略,6.1 一般方法 6.2 背包問題 6.3 帶時限的作業(yè)排序 6.4 最佳合并模式 6.5 最小代價生成樹 6.6 單源最短路徑 6.7 磁帶最優(yōu)存儲 6.8 貪心法的基本要素,第6章 貪心法,最優(yōu)化問題（optimization problems）是指這樣一類問題，問題給定某些約束條件（constraint），滿足這些約束條件的問題解稱為可行解（feasible solution）。通常滿足約束條件的解不是惟一的。為了衡量可行解的好壞，問題還給出了某個數值函數，稱為目標函數（objective function），使目標函數取最大（或最?。┲档目尚薪夥Q為最優(yōu)解（op

2、timal solution）。,6.1 一般方法,貪心法是通過分步決策（stepwise decision）的方法來求解問題的。 貪心法每一步上用作決策依據的選擇準則被稱為最優(yōu)量度標準（optimization criterion）。 在根據最優(yōu)量度標準選擇分量的過程中，還需要使用一個可行解判定函數。 貪心策略并不是從整體上加以考慮的，它所做出的選擇只是當前看似最佳選擇，必須進一步證明該算法最終導致問題的一個整體最優(yōu)解。,貪心技術(Greedy Technique),某一問題的n個輸入,該問題的一種解（可行解）,是A的一 個子集,滿足一定 的條件,約束條件,目標函數,取極值,最優(yōu)解,【程序6

3、1】貪心法 SolutionType Greedy(SType a,int n) SolutionType solution=; for(int i=0;in;i+) SType x=Select(a); if (Feasiable(solution,x) solution=Union(solution,x); return solution; ,7,找零錢問題(change-making problem),用當地面額為d1d2dm的最少數量的硬幣找出金額為n的零錢。 如d1=25,d2=10,d3=5,d4=1，n=48 該問題的一個解是： 1個25，2個10，3個1，且該解是最優(yōu)的。 這種

4、方法稱為貪心法，建議通過一系列步驟來構造問題的解，每一步對目前構造的部分解做一個擴展，直到獲得問題的完全解。 必須滿足：可行、局部最優(yōu)、不可取消,8,又如：d1=11,d2=5,d3=1,n=15 該問題的一個解是： 1個11，4個1，該解不是最優(yōu)的。 最優(yōu)解：3個5 本質上由硬幣面值種類決定（問題其本身固有的特點） 。,貪心策略最優(yōu)解的證明,基本思想 設X=x1,x2,.,xn為貪心策略得到的解 設Y=y1,y2,.,yn為該問題的最優(yōu)解 很明顯，XY，如果成立，則不用證明了。 證明過程： 依次比較X和Y中的每個元素，如果發(fā)現(xiàn)不一樣，則用X中的替換Y中相應元素，比較完后得到一個新的解Y=X

5、此時，如能證明Y的最優(yōu)值就是Y的最優(yōu)值或者比Y還好，則說明X就是最優(yōu)解。,問題 對容量為M的背包進行最佳裝載的問題。,6.2 背包問題,6.2.1 問題描述,已知一個載重為M的背包和n件物品，第i件物品的重量為 wi，如果將第i件物品全部裝入背包，將有收益pi，這里，wi0，pi0，0in。所謂背包問題是指求一種最佳裝載方案，使得收益最大。所以，背包問題是現(xiàn)實世界一個常見的最優(yōu)化問題。 兩類背包問題:如果每一件物品不能分割，只能作為整體或者裝入背包，或者不裝入，稱為 0/1背包問題；如果物品是可以分割的，也就是允許將其中的一部分裝入背包為一般背包問題或簡稱背包問題。,6.2.2 貪心法求解,背

6、包問題 背包問題的解可以表示成一個n-元組：X=(x0,x1,xn1)，0 xi1，0in，每個xi是第i件物品裝入背包中的部分。 判定可行解的約束條件是：,背包問題的最優(yōu)解必須使下列目標函數取最大值：,例61 設有載重能力M=20的背包，3件物品的重量為:（w0,w1,w2）=(18,15,10)，物品裝入背包的收益為：（p0,p1,p2）=(25,24,15)。,背包問題(Knapsack Problem),方案1：按物品價值降序裝包,方案2：按物品重量升序裝包,方案3：按物品價值與重量比值的降序裝包,【程序62】背包問題的貪心算法 template class Knapsack publ

7、ic: Knapsack(int mSize,float cap,float *wei,T *prof); void GreedyKnapsack(float* x); private: float m,*w; T *p; int n; ;,template void Knapsack:GreedyKnapsack(float* x) /前置條件：wi已按pi/wi的非增次序排列 float u=m; for (int i=0;iu) break; xi=1.0; u=u-wi; if (i=n) xi=u/wi; ,6.2.3 算法正確性,定理61 如果p0/w0p1/w1pn1/wn1，則

8、程序62求得的背包問題的解是最優(yōu)解。,證明： 設X=(x0, x1, , xn-1)， 0 xj 1 ,0in是貪心背包算法所生成的貪心解。 如果所有的xi都等于1,則顯然X就是問題的最優(yōu)解。否則， 設j是使xi1的最小下標。由算法的執(zhí)行過程可知， 解的形式為： X=(1, , 1,xj,0, , 0) 即xi=1 0ij, 0 xj 1,xi=0 jin-1,假設Y是問題的最優(yōu)解：Y=(y0, y1, , yn-1) 且有： 若X Y，則X就是最優(yōu)解。否則， X和Y至少在1個分量上存在不同。 設k是使得yk xk的最小下標，則有yk xk?？煞忠韵虑闆r說明： a) 若kj，則xk=1。因為y

9、k xk,從而有yk xk b) 若k=j，由于 ，且對1ij，有yi=xi=1,而對jin,有xi0；故此時若ykxk，則將有 ，與Y是可行解相矛盾。而yk xk,所以yk xk c) 若kj，則 ，不能成立,在Y中作以下調整：將yk 增加到xk ，因為ykxk,為保持解的可行性，必須從(yk+1,yn-1)中減去同樣多的量。設調整后的解為Z=(z0, z1, ,zk,zk+1, , zn-1)，其中zixi，0ik，且有： Z的效益值有：,差值0,由以上分析得， 若 ，則Y將不是最優(yōu)解； 若 ，則或者Z=X，則X就是最優(yōu)解； 或者ZX，則重復以上替代過程，或者證明Y不是最優(yōu)解，或者把Y轉換

10、成X，從而證明X是最優(yōu)解,最優(yōu)裝載,有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。 1.算法描述 最優(yōu)裝載問題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略，可產生最優(yōu)裝載問題的最優(yōu)解。具體算法描述如下頁。,template void Loading(int x, Type w, Type c, int n) int *t = new int n+1; Sort(w, t, n); for (int i = 1; i = n; i+) xi = 0; for (int i = 1; i = n

11、,2.貪心選擇性質 可以證明最優(yōu)裝載問題具有貪心選擇性質。 3.最優(yōu)子結構性質 最優(yōu)裝載問題具有最優(yōu)子結構性質。 由最優(yōu)裝載問題的貪心選擇性質和最優(yōu)子結構性質，容易證明算法loading的正確性。 算法loading的主要計算量在于將集裝箱依其重量從小到大排序，故算法所需的計算時間為 O(nlogn)。,活動安排問題,活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合，是可以用貪心算法有效求解的很好例子。該問題要求高效地安排一系列爭用某一公共資源的活動。貪心算法提供了一個簡單、漂亮的方法使得盡可能多的活動能兼容地使用公共資源。,設有n個活動的集合E=1,2,n，其中每個活動都要求使用

12、同一資源，如演講會場等，而在同一時間內只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結束時間fi,且si fi 。如果選擇了活動i，則它在半開時間區(qū)間si, fi)內占用資源。若區(qū)間si, fi)與區(qū)間sj, fj)不相交，則稱活動i與活動j是相容的。也就是說，當sifj或sjfi時，活動i與活動j相容。,template void GreedySelector(int n, Type s, Type f, bool A) A1=true; int j=1; for (int i=2;i=fj) Ai=true; j=i; else Ai=false; ,下面

13、給出解活動安排問題的貪心算法GreedySelector :,各活動的起始時間和結束時間存儲于數組s和f中且按結束時間的非減序排列,由于輸入的活動以其完成時間的非減序排列，所以算法greedySelector每次總是選擇具有最早完成時間的相容活動加入集合A中。直觀上，按這種方法選擇相容活動為未安排活動留下盡可能多的時間。也就是說，該算法的貪心選擇的意義是使剩余的可安排時間段極大化，以便安排盡可能多的相容活動。 算法greedySelector的效率極高。當輸入的活動已按結束時間的非減序排列，算法只需O(n)的時間安排n個活動，使最多的活動能相容地使用公共資源。如果所給出的活動未按非減序排列，可

14、以用O(nlogn)的時間重排。,例：設待安排的11個活動的開始時間和結束時間按結束時間的非減序排列如下：,算法greedySelector 的計算過程如左圖所示。圖中每行相應于算法的一次迭代。陰影長條表示的活動是已選入集合A的活動，而空白長條表示的活動是當前正在檢查相容性的活動。,若被檢查的活動i的開始時間Si小于最近選擇的活動j的結束時間fi，則不選擇活動i，否則選擇活動i加入集合A中。 貪心算法并不總能求得問題的整體最優(yōu)解。但對于活動安排問題，貪心算法greedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動集合A的規(guī)模最大。這個結論可以用數學歸納法證明。,6.3.1

15、問題描述,設有一個單機系統(tǒng)、無其它資源限制且每個作業(yè)運行相等時間，不妨假定每個作業(yè)運行1個單位時間?，F(xiàn)有n個作業(yè)，每個作業(yè)都有一個截止期限di0，di為整數。如果作業(yè)能夠在截止期限之內完成，可獲得pi0的收益。問題要求得到一種作業(yè)調度方案，該方案給出作業(yè)的一個子集和該作業(yè)子集的一種排列，使得若按照這種排列次序調度作業(yè)運行，該子集中的每個作業(yè)都能如期完成，并且能夠獲得最大收益。也就是說這種作業(yè)調度是最優(yōu)的。,6.3 帶時限的作業(yè)排序,6.3.2 貪心法求解,例62 設有4個作業(yè)，每個作業(yè)的時限為(d0,d1,d2,d3)=(2,1,2,1),收益為(p0,p1,p2,p3)=(100,10,15

16、,27)。,【程序63】帶時限作業(yè)排序的貪心算法 void GreedyJob(int d, Set X, int n) /前置條件：p0p1,pn-1 X=0; for (int i=1;in;i+) if ( 集合 Xi 中作業(yè)都能在給定時限內完成) X=Xi; ,6.3.3 算法正確性,定理62 程序62的貪心算法對于帶時限作業(yè)排序問題將得到最優(yōu)解。,證明： 設X =(x0, x1, , xK)是由貪心算法6-2所得的作業(yè)集合貪心解， Y =(y0, y1, , yr)是一個最優(yōu)解的作業(yè)集合。 若Y=X，則X就是最優(yōu)解；否則 ，則至少存在兩個作業(yè)a和b，使得aX且 ,bY且 。（為什么）

17、 并設a是這樣的一個具有最高效益值的作業(yè) (由算法的處理規(guī)則可得：對于在Y中而不在X中的作業(yè)所有b，有：papb),設和分別是X和Y的可行的調度表。因為X和Y都是可行解，故這樣的調度表一定存在； 設x是既屬于X又屬于Y的一個作業(yè)，并設x在調度表中的調度時刻是t，t+1，而在中的調度時刻是t，t+1。 在X和Y中作如下調整： 若tt，則將中在t，t+1時刻調度的那個作業(yè)（如果有的話）與x相交換。如果X中在t，t+1時刻沒有作業(yè)調度，則直接將x移到t，t+1調度。新的調度表也是可行的。, 若tt，則在中作類似的調換，即將中在t，t+1時刻調度的那個作業(yè)（如果有的話）與x相交換。如果Y中在t，t+1

18、時刻沒有作業(yè)調度，則直接將x移到t，t+1調度。同樣，新的調度表也是可行的。 對X和Y中共有的所有作業(yè)作上述的調整。設調整后得到的調度表為和，則在和中X和Y中所有的共有作業(yè)將在相同時間被調度。,設a在中的調度時刻是ta, ta+1， b是中該時刻調度的作業(yè)，則有papb（為什么？）。 在中，去掉作業(yè)b，而去調度作業(yè)a，得到的是作業(yè)集合Y=（Y-b）a的 一個可行的調度表，且Y的效益值不小于X的效益值。而Y中比Y少了一個與X不同的作業(yè)。 重復上述的轉換，可使Y在不減效益值的情況下轉換成X。從而X至少有和Y一樣的效益值。所以X也是最優(yōu)解。 證畢。,=（x z ） =（ z x ） =（y x ）

19、=（ y x ） (a) x與z交換前 (b) x與z交換后 =（y x ） =（ y x ） =（x z ） =（ z x ） (c) x與z交換前 (d) x與z交換后 圖6-1 使相同作業(yè)在相同時刻被調度,6.3.4 可行性判定,定理63 X=（x0,x1,xk）是k個作業(yè)的集合，=（0, 1,k）是X 的一種特定排列，它使得d 0 d1dk ，其中， dj是作業(yè)j的時限。X是一個可行解當且僅當X中的作業(yè)能夠按次序調度而不會有作業(yè)超期。,方法一：枚舉法，檢驗X中作業(yè)所有可能的排列，對于任一種次序排列的作業(yè)序列，判斷這些作業(yè)是否能夠在其期限前完成 若X中有k個作業(yè)，則將要檢查k!個序列 判

20、斷策略： 對于一個給定作業(yè)處理序列i1i2ik,由于作業(yè)ij完成的最早時間是j，因此只要判斷出排列中的每個作業(yè)的期限有dijj，就可得知是一個允許的調度序列，從而X是一可行解。 反之，如果排列中有一個作業(yè)有dijj,則將是一個行不通的調度序列，因為至少作業(yè)ij不能在其期限之前完成。,方法二：檢查X中作業(yè)的一個特定序列就可判斷X的可行性：這一特定序列是按照作業(yè)期限的非降次序排列的作業(yè)序列,證明： 如果X中的作業(yè)可以按照的次序而又不違反任何一個作業(yè)期限的情況來處理，則X是一個可行解 現(xiàn)證若X是一個可行解，是否代表一個可行的調度序列？ X是可行解 必存在一可行的調度序列 r1r2rk，使得drjj,

21、 1jk。 若 ，則即是可行的調度序列。否則， ，令a是使得raia的最小下標（如下圖）, i1 i2 ia ic ik r1 r2 ra rb rk,設rb=ia。則有： ba 且 dradrb 故，在中調換ra與rb，所得的新序列 s1s2sk的處理次序不違反任何一個期限，而中位置a及a之前的作業(yè)均與相同。 重復上述過程，則可將轉換成且不違反任何一個期限，故是一個可行的調度序列 故定理得證。,6.3.5 作業(yè)排序貪心算法,定理63提供了一種高效的可行解判定方法。使得在按最優(yōu)量度標準，即按作業(yè)收益的非增次序選擇下一個作業(yè)后，可以有效地判定是否可將該作業(yè)加入已生成的部分解向量X。,【程序64】

22、帶時限的作業(yè)排序程序 int JS(int *d, int *x, int n) /設p0p1pn-1 int k=0; x0=0; for (int j=1;j=0 ,6.3.6 一種改進算法,本小節(jié)將介紹一種帶時限作業(yè)排序的快速算法，它采用不同于前者的可行解判定方法，可使算法的時間從(n2)減少到接近O(n)。,例63 設n=5個作業(yè)， 作業(yè)的時限為:(d0,d1,d2,d3,d4)=(2,2,1,3,3), 收益為: (p0,p1,p2,p3,p4)=(20,15,10,5,1)。,【程序65】使用并查集的帶時限作業(yè)排序 int FJS(int *d,int *x,int n) UFSe

23、t s(n); int b,k=-1,*f=new intn+1; for (int i=0;i=n;i+) fi=i;,for (i=0;in;i+) if(ndi) b=n;else b=di; int r=s.Find(b); if (fr) x+k=i; int t=s.Find(fr-1); s.Union(t,r); fr=ft; delete f; return k; ,多機調度問題,多機調度問題要求給出一種作業(yè)調度方案，使所給的n個作業(yè)在盡可能短的時間內由m臺機器加工處理完成。 這個問題是NP完全問題，到目前為止還沒有有效的解法。對于這一類問題,用貪心選擇策略有時可以設計出較好

24、的近似算法。,約定，每個作業(yè)均可在任何一臺機器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。,采用最長處理時間作業(yè)優(yōu)先的貪心選擇策略可以設計出解多機調度問題的較好的近似算法。 按此策略，當 nm時，只要將機器i的0, ti時間區(qū)間分配給作業(yè)i即可，算法只需要O(1)時間。 當nm時，首先將n個作業(yè)依其所需的處理時間從大到小排序。然后依此順序將作業(yè)分配給空閑的處理機。算法所需的計算時間為O(nlogn)。,例如，設7個獨立作業(yè)1,2,3,4,5,6,7由3臺機器M1，M2和M3加工處理。各作業(yè)所需的處理時間分別為2,14,4,16,6,5,3。按算法greedy產生的作業(yè)調度

25、如下圖所示，所需的加工時間為17。,6.4.1 問題描述,兩路合并外排序算法通過反復執(zhí)行將兩個有序子文件合并成一個有序文件的操作，最終將n個長度不等的有序子文件合并成一個有序文件。 合并n個有序子文件成為一個有序文件的合并過程可以有多種方式，稱為合并模式。 在整個合并過程中，需從外存讀寫的記錄數最少的合并方案稱為最佳合并模式（optimal merge pattern）。,6.4 最佳合并模式,例64 設有5個有序子文件（F1,F2,F3,F4,F5），其長度分別為（20，30，30，10，5）。現(xiàn)通過兩兩合并將其合并成一個有序文件。,帶權外路徑長度是針對擴充二叉樹而言的。擴充二叉樹（exte

26、nded binary tree）中除葉子結點外，其余結點都必須有兩個孩子。擴充二叉樹的帶權外路徑長度（weighted external path length）定義為：,6.4.2貪心法求解,兩路合并最佳模式問題的最優(yōu)量度標準為帶權外路徑長度最小。,兩路合并最佳模式的貪心算法簡述如下： 設Ww0,w1 ,wn1是n個有序文件的長度；以每個權值作為根結點值，構造n棵只有根的二叉樹； 選擇兩棵根結點權值最小的樹，作為左右子樹構造一棵新二叉樹，新樹根的權值是兩棵子樹根的權值之和； 重復第2步，直到合并成一棵二叉樹為止。,【程序66】兩路合并最佳模式的貪心算法 template struct HN

27、ode /優(yōu)先權隊列中的元素的類型 operator T()const return weight; BTNode *ptr; T weight; ;,template BTNode* CreateHfmTree (T* w,int n) /w 為一維數組保存n個權值 PrioQueue pq(2*n-1); BTNode*p;HNode a,b; for (int i=0;i(wi); a.ptr=p;a.weight=wi; pq.Append(a); ,for (i=1;i(a.weight,a.ptr,b.ptr); a.ptr=p; pq.Append(a); pq.Serve(a)

28、; return a.ptr; ,6.4.3 算法正確性,定理64 設有n個權值W=w0,w1 ,wn1作為外結點的權值，構造兩路合并樹的貪心算法將生成一棵具有最小帶權外路徑長度的二叉樹。,6.5.1 問題描述,問題 一個無向連通圖的生成樹是一個極小連通子圖，它包括圖中全部結點，并且有盡可能少的邊。 一棵生成樹的代價是樹中各條邊上的代價之和。一個網絡的各生成樹中，具有最小代價的生成樹稱為該網絡的最小代價生成樹（minimum-cost spanning tree）。,6.5 最小代價生成樹,網絡的最小生成樹在實際中有廣泛應用。例如，在設計通信網絡時，用圖的頂點表示城市，用邊(v,w)的權cvw

29、表示建立城市v和城市w之間的通信線路所需的費用，則最小生成樹就給出了建立通信網絡的最經濟的方案。,6.5.2 貪心法求解,最優(yōu)量度標準 選擇使得迄今為止已入選S中邊的代價之和增量最小的邊 克魯斯卡爾算法的貪心準則是：按邊代價的非減次序考察E中的邊，從中選擇一條代價最小的邊e=(u,v)。 普里姆算法的貪心準則是：在保證S所代表的子圖是一棵樹的前提下選擇一條最小代價的邊e=(u,v)。,最小生成樹性質 用貪心算法設計策略可以設計出構造最小生成樹的有效算法。將介紹的構造最小生成樹的Prim算法和Kruskal算法都可以看作是應用貪心算法設計策略的例子。盡管這兩個算法做貪心選擇的方式不同，它們都利用

30、了下面的最小生成樹性質： 設G=(V,E)是連通帶權圖，U是V的真子集。如果(u,v)E，且uU，vV-U，且在所有這樣的邊中，(u,v)的權cuv最小，那么一定存在G的一棵最小生成樹，它以(u,v)為其中一條邊。這個性質有時也稱為MST性質。,【程序67】最小代價生成樹的貪心算法 ESetType SpanningTree(ESetType E, int n) /G=(V,E)為無向圖 ESetType S=; int u,v,k=0; EType e; while (kn-1 ,6.5.3Prim(普里姆)算法,【程序68】普里姆算法 template struct ENode /帶權圖的

31、邊結點 int adjVex; T w; ENode* nextArc; ;,template class Graph public: Graph (int mSize); void Prim(); protected: void Prim(int k,int* nearest,T* lowcost); ENode* a; int n; ;,template void Graph:Prim(int s) /公有成員函數 int* nearest=new intn,*lowcost=new intn; Prim(s,nearest,lowcost); for(int j=0;jn;j+) cou

32、t(nearestj,“ j,lowcostj) ; coutendl; delete nearest; delete lowcost; ,template void Graph:Prim(int k, int* nearest,T* lowcost) /私有成員函數 bool* mark=new booln; ENode *p; if (kn-1) throw OutofBounds; for (int i=0;in;i+) nearesti=-1;marki=false; lowcosti=INFTY; lowcostk=0; nearestk=k; markk=true;,for (i=

33、1;inextArc) int j= p-adjVex; if (!markj ) 普里姆算法的運行時間是O(n2)。,6.5.4 克魯斯卡爾算法,克魯斯卡爾算法從邊的集合E中，按照邊的權值從小到大的次序依次選取邊加以考察。 template struct eNode operator T ()const return w; int u,v; T w; ;,【程序69】克魯斯卡爾算法 template void Graph:Kruskal( PrioQueue ,while (kn-1 克魯斯卡爾算法的時間復雜度為 O（elog e）。,6.5.5 算法正確性,定理65 設圖G=（V，E）是一

34、個帶權連通圖，U是V的一個真子集。若邊(u,v)E是所有uU, vV-U的邊中權值最小者，那么一定存在G的一棵最小代價生成樹T=(V,S)，(u,v)S。這一性質稱為MST（minimum spanning tree）性質。,定理66 普里姆算法和克魯斯卡爾算法都將產生一個帶權無向連通圖的最小代價生成樹。,6.6.1 問題描述,單源最短路徑問題是：給定帶權的有向圖G=(V,E)和圖中結點sV，求從s到其余各結點的最短路徑，其中，s稱為源點。,6.6 單源最短路徑,6.6.2 貪心法求解,迪杰斯特拉（Dijkstra） 算法 首先求得長度最短的一條最短路徑，再求得長度次短的一條最短路徑，依此類推

35、，直到從源點到其它所有結點之間的最短路徑都已求得為止。,6.6.3 迪杰斯特拉算法,【程序610】迪杰斯特拉算法 template class MGraph public: MGraph(int mSize); void Dijkstra(int s,T* ,private: int Choose(int* d, bool* s); T*a; int n; ;,template int MGraph:Choose(int* d, bool* s) int i,minpos; T min; min=INFTY; minpos=-1; for (i=1;in;i+) if (dimin ,temp

36、late void MGraph:Dijkstra(int s, T* ,inSs=true; ds=0; for (i=1;in-1;i+) k=Choose(d,inS); inSk=true; for (j=0; jn; j+) if (!inSj ,6.6.4 算法正確性,定理67 已知帶權有向圖G=(V,E)，其源點為s，迪杰斯特拉算法使得對所有i，iV-s，di(s,i)，且一旦di= (s,i)，它將不再改變。 定理68 已知帶權有向圖G=(V,E)，其源點為s，迪杰斯特拉算法使得對所有結點i和j, iS，jV-S，必有didj。,定理69 已知帶非負權值的有向圖G=(V,E)，

37、路徑（s=v0, ,vi,vk=t）是從s到vk的一條最短路徑，viV，0ikn，則子路徑（s=v0, ,vi）和（vi,vk=t）必定分別是從s到vi 和vi到t的最短路徑。 定理610 已知帶非負權值的有向圖G=(V,E)，其源點為s，迪杰斯特拉算法結束時，對所有結點i，有di=(s,i)。,6.7.1 單帶最優(yōu)存儲,問題 設有n個程序編號為0,n-1，存放在長度為L的磁帶上，程序i在磁帶上的存儲長度為ai，0in。 假定每個程序被檢索地概率相等，則平均檢索時間（mean retrieval time MRT）定義為 單帶最優(yōu)存儲問題是求這n個程序的一種排列，使得MRT有最小值。,6.7

38、磁帶最優(yōu)存儲,例65 設n=3，(a0,a1,a2)=(5,10,3)。,貪心法求解 量度標準：計算迄今為止已選的那部分程序的D值，選擇下一個程序應使得該值增加最小。 定理611 設有n個程序0,1,n-1, 程序i的長度為ai，0in，且有a0a1an1，=(0,1,n1)是這n個作業(yè)的一種排列。那么只有當j=j，0in時，D()=有最小值。,6.7.2 多帶最優(yōu)存儲,問題 設有m1條磁帶T0,T1,Tm1和n個程序。要求將此n個程序分配到這m條磁帶上，令Ij,0jm 是存放在第j條磁帶上的程序子集的某種排列，D(Ij) 的定義如前面相同，那么，求m條磁帶上檢索一個程序的平均檢索時間的最小值

39、等價于求 的最小值。,【程序611】多帶最優(yōu)存儲 #include void Store(int n, int m) int j = 0; for (int i=0; in; i+) cout 將程序i 加到磁帶 jendl; j=(j+1)% m; coutendl; ,定理612 設有n個程序0,1,n-1, 程序i的長度為ai，0in，且有a0a1an1， 程序611 實現(xiàn)將n個程序分配到m條磁帶上，且有最小TD值。,6.8.1 最優(yōu)量度標準,選擇最優(yōu)量度標準是使用貪心法求解問題的核心問題。 貪心算法每一步作出的選擇可以依賴以前作出的選擇，但不依賴將來的選擇，也不依賴于子問題的解。 對于一個貪心算法，必須證明所采用的量度標準能夠導致一個整體最優(yōu)解。,6.8 貪心法的基本要素,6.8.2 最優(yōu)子結構,最優(yōu)子結構特性是關于問題最優(yōu)解的特性。當一個問題的最優(yōu)解中包含了子問題的最優(yōu)解，則稱該問題具有最優(yōu)子結構特性（optimal substructure）。 一般而言，如果一個最優(yōu)化問題的解結構具有元組形式，并具有最優(yōu)子結構特性，我們可以嘗試選擇量度標準。,