算法設(shè)計(jì)（第6章貪心法）

1、算法設(shè)計(jì)（第算法設(shè)計(jì)（第6 6章貪心法章貪心法）貪心法簡介找零錢問題10元3元=7元: 5 + 2100元3元=97元: 50 + 20 + 20 + 5 + 2100元14元=86元: 50 + 20 + 10 + 5 + 1沒有更優(yōu)的找錢方案每次盡可能地選取最大面額的鈔票貪心法簡介找零錢問題每次盡可能地選取最大面額的鈔票貪心算法Algorithm Change(int x)begin let a1 = a2 = a3 = 0; if (x 5) then a3 1; x x 5; while (x 2) do a2 a2 + 1; x x 2; a1 x; return (a1, a2,

2、a3);end貪心法簡介找零錢問題最優(yōu)性證明：1假設(shè)x的值為1, 2, 5，那么所需的零錢為1張，這顯然是最少的。2否那么，所需的錢數(shù)至少為2張。算法對(duì)3, 4, 6, 7生成的找錢方案分別為2+1, 2+2, 5+1, 5+2，這顯然也是最少的。3假設(shè)x的值為8和9，算法生成的找錢方案分別為5+2+1和5+2+2；而用2張鈔票不能找出8元或9元的零錢，因此算法的結(jié)果也是最少的。 如果將x的值擴(kuò)大到100以內(nèi)，并增加面值為50, 20和10元的鈔票，那么使用貪心算法仍然能夠得到最優(yōu)的找錢方案， 即每次盡可能地選取最大面額的零鈔。每次盡可能地選取最大面額的鈔票貪心法簡介貪心算法：在問題求解的過程

3、中采用“貪婪的策略來構(gòu)造目標(biāo)解。實(shí)現(xiàn)起來較為簡單難點(diǎn)通常在于算法的正確性證明貪心法簡介最大裝載問題輸入：總重量限制W，以及n個(gè)物品的重量A = a0, a1, ,an1輸出：A的一個(gè)子集A*，其和不大于W，且元素?cái)?shù)量盡可能大W = 1000, A = 400, 350, 300, 250, 240, 180, 150, 120選取選取 120 + 150 + 180 + 240 + 250最優(yōu)不可能選出5個(gè)以上的物品每次盡可能地選取重量最小的物品貪心法簡介每次盡可能地選取重量最小的物品貪心算法Algorithm MaxLoad(W: int; A: int)begin Sort(A); let

4、 i = 0; while (W0) do if (Ai W) then W W - Ai; i i + 1; return A0.i;end最大裝載問題貪心法簡介最優(yōu)性證明：【引理6.1】設(shè)A*是問題P(A,W)的一個(gè)最優(yōu)解，那么a0總是可以包含在A*中?！疽?.2】設(shè)A*是問題P(A,W)的一個(gè)最優(yōu)解，且a0A*，那么A*a0也是問題P(Aa0,Wa0)的一個(gè)最優(yōu)解?！径ɡ?.1】貪心算法6.2輸出最大數(shù)量裝載問題P(A,W)的一個(gè)最優(yōu)解。每次盡可能地選取重量最小的物品最大裝載問題最小生成樹樹: 無回路的連通子圖生成樹：含圖中所有頂點(diǎn)的樹最小生成樹: 加權(quán)圖中權(quán)值最小的生成樹 最小生成樹

5、最小生成樹: 加權(quán)圖中權(quán)值最小的生成樹 abcde1810282420161512abcde10242015abcde1810281210abcde182012窮舉法窮舉法: O(2n)最小生成樹Prim算法: 每次選取連接V和VV的權(quán)值最小的邊 abcde1810282420161512abcde18101512最小生成樹O(n2)Algorithm Prim(V: set; E: set; w: int,)begin let n = |V|, Y = E E0; let V = E0.a, E0.b, E = E0, tw = wE0; while (|V| n) do let i = 0

6、; while (i |Y|) do if (Yi.aV Yi.bV) (Yi.aV Yi.bV) break; i i + 1; let e = Yi; /e為V和VV之間的最小邊 E E e; V V e.a, e.b; tw tw + we; Y Y e; return (E, tw);endPrim算法: 每次選取連接V和VV的權(quán)值最小的邊 最小生成樹最優(yōu)性證明：1權(quán)值最小的邊e0可以包含在G的最小生成樹中。2設(shè)T = 為最小生成樹T的一棵子樹，e為連接V和VV之間的所有邊中權(quán)值最小的一條，那么e可以包含在最小生成樹中。 按數(shù)學(xué)歸納法，Prim算法的結(jié)果是一棵最小生成樹。Prim算法:

7、 每次選取連接V和VV的權(quán)值最小的邊 最小生成樹Kruskal算法: 每次選取不產(chǎn)生回路的最小邊 abcde1810282420161512abcde18101512最小生成樹Kruskal算法: 每次選取不產(chǎn)生回路的最小邊 O(m logm)Algorithm Kruskal(V: set; E: set; w: int,)begin let n = |V|, Y = E E0; let V = E0.a,E0.b, E = E0, tw = wE0; while (|V0| |V|) do for i = 0 to |Y|-1 do e = Yi; if (AddWithoutLoop(V

8、, e) then E E e; tw tw + we; Y Y e; break; return (E, tw);end最小生成樹最優(yōu)性證明：1權(quán)值最小的邊e0可以包含在G的最小生成樹中。2設(shè)T = 為最小生成樹T的一個(gè)無環(huán)子圖，e為EE中權(quán)值最小、且Ee不會(huì)產(chǎn)生回路的一條邊，那么e可以包含在最小生成樹中。 按數(shù)學(xué)歸納法，Kruskal算法的結(jié)果是一棵最小生成樹。Kruskal算法: 每次選取不產(chǎn)生回路的最小邊 最小生成樹破圈算法: 每次刪除現(xiàn)有回路中的最大邊 abcde1810282420161512abcde1810282420161512最小生成樹破圈算法: 每次刪除現(xiàn)有回路中的最大邊

9、 O(mn)Algorithm Guan(V: set; E: set; w: int,)begin let E = E; foreach (e E) do if (Connect(V, Ee, e.a, e.b) then E E e; return (V,E);end最小生成樹最優(yōu)性證明：每次“破圈時(shí)刪除的邊都不屬于最小生成樹。破圈算法: 每次刪除現(xiàn)有回路中的最大邊 單源最短路徑輸入: 連通圖G = (權(quán)值非負(fù))，s,tV輸出: 圖中從s到t的最短路徑單源最短路徑Dijkstra算法: 每次選取VV中距s最近的一個(gè)頂點(diǎn) abcde1810282420161512abcde18102815單

10、源最短路徑O(n2)Algorithm Dijkstra(V: set; E: set; w: int,; s: int)begin let n = |V|, V = s, X = Vs; let dis = new intn, pre = new intn; for i=0 to n-1 do disi ws,i; prei s; while (|V| 0) do let d = disv+wv,v; if (disv d) then disv d; prev v; return (dis, pre);endDijkstra算法: 每次選取VV中距s最近的一個(gè)頂點(diǎn)單源最短路徑最優(yōu)性證明：【定

11、理】在算法的每一步，對(duì)所選取的頂點(diǎn)vV，disv是圖中從s到v的最短距離。證明數(shù)學(xué)歸納法Dijkstra算法: 每次選取VV中距s最近的一個(gè)頂點(diǎn)貪心調(diào)度往返運(yùn)輸問題輸入: 數(shù)組d，其中di為倉庫到第i個(gè)客戶的距離 (0in)輸出: 輸送序列，使得客戶的等待時(shí)間之和iti最小s1s2s4ss313102016s58貪心調(diào)度往返運(yùn)輸問題貪心策略: 優(yōu)先選取最近的尚未輸送的客戶s1s2s4ss313102016s58貪心調(diào)度帶權(quán)重的往返運(yùn)輸問題輸入: 數(shù)組d和r，其中di為倉庫到第i個(gè)客戶的距離，ri為第i個(gè)客戶的泉州 (0its0.b是ts中所有與0相容的活動(dòng)集，那么T0是S的最大相容子集。 按數(shù)學(xué)歸納法，貪心算法的結(jié)果是最大相容子集。區(qū)間活動(dòng)安排問題貪心策略: 優(yōu)先選取最早結(jié)束的尚未安排的相容活動(dòng)貪心調(diào)度單位時(shí)間任務(wù)調(diào)