算法設(shè)計(jì)與分析-第4章 貪心算法

1、第第4 4章章 貪心算法貪心算法4.1 4.1 什么是貪心法什么是貪心法4.2 4.2 貪心法的典型示例貪心法的典型示例本章小結(jié)本章小結(jié)算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 2 4.1 什么是貪心法什么是貪心法4.1.1 復(fù)雜問(wèn)題的求解方法復(fù)雜問(wèn)題的求解方法4.1.2 貪心法的設(shè)計(jì)思想貪心法的設(shè)計(jì)思想4.2.3 幾個(gè)例子幾個(gè)例子4.2.4 小結(jié)小結(jié)算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 3 4.1.1 復(fù)雜問(wèn)題的求解典型方法復(fù)雜問(wèn)題的求解典型方法|分

2、治法分治法將復(fù)雜問(wèn)題分成將復(fù)雜問(wèn)題分成若干個(gè)相互獨(dú)立若干個(gè)相互獨(dú)立的子問(wèn)題，通過(guò)求的子問(wèn)題，通過(guò)求解子問(wèn)題，并將子問(wèn)題的解合并得到原問(wèn)題的解。解子問(wèn)題，并將子問(wèn)題的解合并得到原問(wèn)題的解。|動(dòng)態(tài)規(guī)劃法動(dòng)態(tài)規(guī)劃法將一個(gè)復(fù)雜問(wèn)題分解為將一個(gè)復(fù)雜問(wèn)題分解為若干個(gè)相互重疊若干個(gè)相互重疊的子問(wèn)題，的子問(wèn)題，通過(guò)求解子問(wèn)題形成一系列決策得到原問(wèn)題的解。通過(guò)求解子問(wèn)題形成一系列決策得到原問(wèn)題的解。動(dòng)態(tài)規(guī)劃是對(duì)分治的改善動(dòng)態(tài)規(guī)劃是對(duì)分治的改善，在發(fā)現(xiàn)有重疊問(wèn)題時(shí)，在發(fā)現(xiàn)有重疊問(wèn)題時(shí)，使用自底向上的策略避免重復(fù)計(jì)算，從而提升了算使用自底向上的策略避免重復(fù)計(jì)算，從而提升了算法的效率。法的效率。但但僅有動(dòng)態(tài)規(guī)劃是不夠

3、的！僅有動(dòng)態(tài)規(guī)劃是不夠的！算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 4 4.1.1 復(fù)雜問(wèn)題的求解典型方法復(fù)雜問(wèn)題的求解典型方法|貪心法（貪心法（Greedy Method）將一個(gè)復(fù)雜問(wèn)題分解為將一個(gè)復(fù)雜問(wèn)題分解為一系列較為簡(jiǎn)單的局部最一系列較為簡(jiǎn)單的局部最優(yōu)選擇優(yōu)選擇，每一個(gè)選擇都是對(duì)當(dāng)前解的一個(gè)擴(kuò)展，每一個(gè)選擇都是對(duì)當(dāng)前解的一個(gè)擴(kuò)展，直到獲得問(wèn)題的完整解。直到獲得問(wèn)題的完整解。|搜索法搜索法算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 5 4.1.2 貪心

4、法的設(shè)計(jì)思想貪心法的設(shè)計(jì)思想|基本思想基本思想將問(wèn)題的求解過(guò)程看作是將問(wèn)題的求解過(guò)程看作是一系列選擇一系列選擇，每次選擇，每次選擇都是當(dāng)前狀態(tài)下的最好選擇都是當(dāng)前狀態(tài)下的最好選擇(局部最優(yōu)解局部最優(yōu)解)。每作一次選擇后，所求問(wèn)題會(huì)簡(jiǎn)化為一個(gè)規(guī)模更每作一次選擇后，所求問(wèn)題會(huì)簡(jiǎn)化為一個(gè)規(guī)模更小的子問(wèn)題，從而通過(guò)每一步的最優(yōu)解逐步達(dá)到小的子問(wèn)題，從而通過(guò)每一步的最優(yōu)解逐步達(dá)到整體的最優(yōu)解。整體的最優(yōu)解。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 6 4.1.2 貪心法的設(shè)計(jì)思想貪心法的設(shè)計(jì)思想|特點(diǎn)特點(diǎn)貪心法在解決問(wèn)題的策略上目光短

5、淺，只根據(jù)當(dāng)貪心法在解決問(wèn)題的策略上目光短淺，只根據(jù)當(dāng)前已有的信息就做出選擇，而且一旦做出了選擇，前已有的信息就做出選擇，而且一旦做出了選擇，不管將來(lái)有什么結(jié)果，這個(gè)選擇都不會(huì)改變。不管將來(lái)有什么結(jié)果，這個(gè)選擇都不會(huì)改變。換言之：換言之：n貪心法并不是從整體最優(yōu)考慮，它所做出的選貪心法并不是從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的擇只是在某種意義上的局部最優(yōu)局部最優(yōu)。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 7 4.2.3 幾個(gè)例子幾個(gè)例子例例1：數(shù)字三角形問(wèn)題數(shù)字三角形問(wèn)題例例2：渴嬰問(wèn)題渴嬰問(wèn)題例例3：找零錢(qián)問(wèn)題

6、找零錢(qián)問(wèn)題算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 8 例例1：數(shù)字三角形問(wèn)題：數(shù)字三角形問(wèn)題|數(shù)字三角形問(wèn)題數(shù)字三角形問(wèn)題窮舉法窮舉法動(dòng)態(tài)規(guī)劃法動(dòng)態(tài)規(guī)劃法n89：13-11-26-15-24貪心法貪心法n63：13-11-12-14-131311872612141567131211824算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 9 例例2：渴嬰問(wèn)題：渴嬰問(wèn)題|問(wèn)題描述問(wèn)題描述已知：已知：n飲料類型：飲料類型： n n飲料滿意度：飲料滿意度： s1 , s

7、2, , si , , sn n飲料總量飲料總量 ： a1 , a2, , ai , , an n需求：需求： t 問(wèn)：?jiǎn)枺簄需要飲用需要飲用n種不同的飲料各多少量才能滿足嬰兒解渴的種不同的飲料各多少量才能滿足嬰兒解渴的需求，而且能達(dá)到最大的滿意程度呢需求，而且能達(dá)到最大的滿意程度呢？算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 10 11max (1,2,)niiiniiiis xxtxain目標(biāo)函數(shù)：約束條件：0,例例2：渴嬰問(wèn)題：渴嬰問(wèn)題|問(wèn)題分析：?jiǎn)栴}分析：令：令：xi 為嬰兒將要飲用的第為嬰兒將要飲用的第i 種飲料的量

8、種飲料的量則：需要解決的問(wèn)題是找到一組實(shí)數(shù)則：需要解決的問(wèn)題是找到一組實(shí)數(shù)xi （1in）算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 11 例例2：渴嬰問(wèn)題：渴嬰問(wèn)題|解決方案：解決方案：分步獲取飲料，每次喝一種飲料，且需要考慮選分步獲取飲料，每次喝一種飲料，且需要考慮選用哪種飲料；用哪種飲料；根據(jù)這種思想，利用如下的根據(jù)這種思想，利用如下的貪心準(zhǔn)則貪心準(zhǔn)則：n從余下的飲料中，選擇滿意度最高的飲料，直從余下的飲料中，選擇滿意度最高的飲料，直到達(dá)到解渴的需要，或者全部飲料被喝完為止。到達(dá)到解渴的需要，或者全部飲料被喝完為止。算法

9、設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 12 例例3：找零錢(qián)問(wèn)題：找零錢(qián)問(wèn)題|問(wèn)題描述問(wèn)題描述假如售貨員需要找給小孩假如售貨員需要找給小孩98元的零錢(qián)，售貨員手元的零錢(qián)，售貨員手中有中有1、2、5、10、20、50元的零錢(qián)若干。元的零錢(qián)若干。在小孩的催促下，售貨員想盡快將錢(qián)找給小孩。在小孩的催促下，售貨員想盡快將錢(qián)找給小孩。|分析：分析：貪心準(zhǔn)則：貪心準(zhǔn)則：n每一次選擇應(yīng)使零錢(qián)數(shù)盡量增大。每一次選擇應(yīng)使零錢(qián)數(shù)盡量增大。n為保證解法的可行性為保證解法的可行性985020 20 52 1算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法

10、 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 13 4.1.4 小結(jié)小結(jié)|貪心法的基本思想貪心法的基本思想由一系列步驟構(gòu)成由一系列步驟構(gòu)成每步滿足每步滿足n可行可行：滿足問(wèn)題的約束條件：滿足問(wèn)題的約束條件n局部最優(yōu)局部最優(yōu)：當(dāng)前狀況下的最優(yōu)解：當(dāng)前狀況下的最優(yōu)解n不可取消不可取消：一旦作出選擇，不可更改：一旦作出選擇，不可更改|求解問(wèn)題的類型求解問(wèn)題的類型局部最優(yōu)導(dǎo)致全局最優(yōu)（局部最優(yōu)導(dǎo)致全局最優(yōu)（最優(yōu)解最優(yōu)解）局部最優(yōu)接近全局最優(yōu)（局部最優(yōu)接近全局最優(yōu)（近似解近似解），但速度極快），但速度極快|優(yōu)點(diǎn)優(yōu)點(diǎn)求解速度快，時(shí)間復(fù)雜性有較低的階求解速度快，時(shí)間復(fù)雜性有較低的階 。

11、算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 14 4.1.4 小結(jié)小結(jié)|貪心法的基本要素貪心法的基本要素:具備具備貪心選擇貪心選擇性質(zhì)和性質(zhì)和最優(yōu)子結(jié)構(gòu)最優(yōu)子結(jié)構(gòu)性質(zhì)的最優(yōu)化問(wèn)性質(zhì)的最優(yōu)化問(wèn)題。題。整體的最優(yōu)解可通過(guò)一整體的最優(yōu)解可通過(guò)一系列局部最優(yōu)解達(dá)到。系列局部最優(yōu)解達(dá)到。每次的選擇可以依賴以每次的選擇可以依賴以前作出的選擇前作出的選擇, ,但不能依但不能依賴于后面的選擇。賴于后面的選擇。問(wèn)題的整體最優(yōu)解中包含問(wèn)題的整體最優(yōu)解中包含著它的子問(wèn)題的最優(yōu)解著它的子問(wèn)題的最優(yōu)解. .算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法

12、四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 15 4.2 貪心法的典型應(yīng)用貪心法的典型應(yīng)用組合問(wèn)題中的貪心法組合問(wèn)題中的貪心法圖問(wèn)題中的貪心法圖問(wèn)題中的貪心法其他問(wèn)題其他問(wèn)題算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 16 應(yīng)用專題一應(yīng)用專題一|組合問(wèn)題中的貪心法組合問(wèn)題中的貪心法例例1：活動(dòng)安排問(wèn)題活動(dòng)安排問(wèn)題例例2：最優(yōu)裝載問(wèn)題最優(yōu)裝載問(wèn)題例例3：01背包問(wèn)題背包問(wèn)題例例4：背包問(wèn)題背包問(wèn)題貪心法與動(dòng)態(tài)規(guī)劃法的異同點(diǎn)貪心法與動(dòng)態(tài)規(guī)劃法的異同點(diǎn)例例5：多機(jī)調(diào)度問(wèn)題多機(jī)調(diào)度問(wèn)題算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析

13、貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 17 例例1：活動(dòng)安排問(wèn)題：活動(dòng)安排問(wèn)題|問(wèn)題提出：?jiǎn)栴}提出：n個(gè)活動(dòng)的集合個(gè)活動(dòng)的集合E=1,2,n每個(gè)活動(dòng)每個(gè)活動(dòng)i 要求使用資源的時(shí)間：要求使用資源的時(shí)間：si, fi)活動(dòng)活動(dòng)i與活動(dòng)與活動(dòng)j是相容的：是相容的：n若區(qū)間若區(qū)間si, fi)與區(qū)間與區(qū)間sj, fj)不相交，稱活動(dòng)不相交，稱活動(dòng)i與活與活動(dòng)動(dòng)j是相容的。是相容的?；顒?dòng)安排問(wèn)題活動(dòng)安排問(wèn)題：在所給的活動(dòng)集合中選出最大的：在所給的活動(dòng)集合中選出最大的相容活動(dòng)子集合。相容活動(dòng)子集合。即：要求高效地安排一系列爭(zhēng)即：要求高效地安排一系列爭(zhēng)用某一公共

14、資源的活動(dòng)。用某一公共資源的活動(dòng)。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 18 例例1：活動(dòng)安排問(wèn)題：活動(dòng)安排問(wèn)題|活動(dòng)安排問(wèn)題的貪心選擇方案活動(dòng)安排問(wèn)題的貪心選擇方案具有最短時(shí)段的相容活動(dòng)具有最短時(shí)段的相容活動(dòng)覆蓋未選擇活動(dòng)最少的相容活動(dòng)覆蓋未選擇活動(dòng)最少的相容活動(dòng)在未安排的活動(dòng)中挑選在未安排的活動(dòng)中挑選結(jié)束時(shí)間最早的活動(dòng)結(jié)束時(shí)間最早的活動(dòng)安排安排算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 19 例例1：活動(dòng)安排問(wèn)題：活動(dòng)安排問(wèn)題|例如：例如：i1234

15、567si1345556fi45678910算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 20 例例1：活動(dòng)安排問(wèn)題：活動(dòng)安排問(wèn)題|算法描述：算法描述：int greedySelector(int s , int f , bool a ) a1=true;int j=1,count=1;for (int i=2;i=fj) ai=true; j=i; count+; else ai=false; return count; 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳

16、劉芳 21 例例1：活動(dòng)安排問(wèn)題：活動(dòng)安排問(wèn)題|算法時(shí)間分析：算法時(shí)間分析：算法算法greedySelector的效率極高。的效率極高。n當(dāng)輸入的活動(dòng)已按結(jié)束時(shí)間的非減序排列，算當(dāng)輸入的活動(dòng)已按結(jié)束時(shí)間的非減序排列，算法只需法只需O(n)的時(shí)間安排的時(shí)間安排n個(gè)活動(dòng)，使最多的活動(dòng)個(gè)活動(dòng)，使最多的活動(dòng)能相容地使用公共資源。能相容地使用公共資源。n如果所給出的活動(dòng)未按非減序排列，可以用如果所給出的活動(dòng)未按非減序排列，可以用O(nlogn)的時(shí)間重排。的時(shí)間重排。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 22 例例1：活動(dòng)安排問(wèn)

17、題：活動(dòng)安排問(wèn)題|利用數(shù)學(xué)歸納法可以證明：利用數(shù)學(xué)歸納法可以證明：貪心算法貪心算法greedySelector總能求得的整體最總能求得的整體最優(yōu)解，即它最終所確定的相容活動(dòng)集合優(yōu)解，即它最終所確定的相容活動(dòng)集合A的的規(guī)模最大。規(guī)模最大。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 23 例例1：活動(dòng)安排問(wèn)題：活動(dòng)安排問(wèn)題|練習(xí)：練習(xí)：已知待安排的已知待安排的11個(gè)活動(dòng)的開(kāi)始時(shí)間和結(jié)束時(shí)間，個(gè)活動(dòng)的開(kāi)始時(shí)間和結(jié)束時(shí)間，并且已經(jīng)按結(jié)束時(shí)間的非減序排列如下：并且已經(jīng)按結(jié)束時(shí)間的非減序排列如下：i1234567891011Si13053

18、5688212fi4567891011121314算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 24 例例1：活動(dòng)安排問(wèn)題：活動(dòng)安排問(wèn)題算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 25 算法實(shí)現(xiàn)題算法實(shí)現(xiàn)題4-1|會(huì)場(chǎng)安排問(wèn)題會(huì)場(chǎng)安排問(wèn)題算法算法1：用算法：用算法GreedySelector來(lái)安排會(huì)場(chǎng)來(lái)安排會(huì)場(chǎng)算法算法2：n對(duì)對(duì)n個(gè)活動(dòng)看做是實(shí)直線上的個(gè)活動(dòng)看做是實(shí)直線上的n個(gè)半閉活動(dòng)區(qū)間，問(wèn)題個(gè)半閉活動(dòng)區(qū)間，問(wèn)題的實(shí)質(zhì)是討論的實(shí)質(zhì)是討論n個(gè)活動(dòng)區(qū)的最大重疊數(shù)個(gè)

19、活動(dòng)區(qū)的最大重疊數(shù)m。n若求得了最大重疊數(shù)若求得了最大重疊數(shù)m，則這，則這m個(gè)重疊區(qū)所對(duì)應(yīng)的活動(dòng)個(gè)重疊區(qū)所對(duì)應(yīng)的活動(dòng)互不相容，因此至少要安排互不相容，因此至少要安排m個(gè)會(huì)場(chǎng)來(lái)容納這個(gè)會(huì)場(chǎng)來(lái)容納這n個(gè)活動(dòng)。個(gè)活動(dòng)。n（1）將活動(dòng)的開(kāi)始和結(jié)束時(shí)間進(jìn)行排序）將活動(dòng)的開(kāi)始和結(jié)束時(shí)間進(jìn)行排序n（2）掃描整個(gè)實(shí)直線，遇到一個(gè)）掃描整個(gè)實(shí)直線，遇到一個(gè)si,則安排一個(gè)空閑會(huì)則安排一個(gè)空閑會(huì)場(chǎng)，遇到一個(gè)場(chǎng)，遇到一個(gè)fi,就釋放一個(gè)會(huì)場(chǎng)為空閑備用。就釋放一個(gè)會(huì)場(chǎng)為空閑備用。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 26 例例2：最優(yōu)裝載：最優(yōu)

20、裝載|問(wèn)題描述問(wèn)題描述有一批集裝箱要裝上一艘載重量為有一批集裝箱要裝上一艘載重量為c的輪船，其中的輪船，其中集裝箱集裝箱i的重量為的重量為wi （1in） 。最優(yōu)裝載問(wèn)題要求確定在裝載體積不受限制的情最優(yōu)裝載問(wèn)題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。況下，將盡可能多的集裝箱裝上輪船。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 27 例例2：最優(yōu)裝載：最優(yōu)裝載|分析：分析： 這個(gè)問(wèn)題可以作為最優(yōu)化問(wèn)題進(jìn)行描述：這個(gè)問(wèn)題可以作為最優(yōu)化問(wèn)題進(jìn)行描述：11max0,1)niiniiiixw xcx標(biāo)數(shù)：約條：

21、，(目函束件算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 28 例例2：最優(yōu)裝載：最優(yōu)裝載|解決方案：解決方案：船可以分步裝載，每步裝一個(gè)貨箱，且需要考慮船可以分步裝載，每步裝一個(gè)貨箱，且需要考慮裝載哪一個(gè)貨箱。裝載哪一個(gè)貨箱。貪心準(zhǔn)則：貪心準(zhǔn)則：n從剩下的貨箱中，選擇重量最小的貨箱。從剩下的貨箱中，選擇重量最小的貨箱。n這種選擇次序可以保證所選的貨箱總重量最小，這種選擇次序可以保證所選的貨箱總重量最小，從而可以裝載更多的貨箱從而可以裝載更多的貨箱。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科

22、學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 29 例例2：最優(yōu)裝載：最優(yōu)裝載|例如：例如：n 8w100,200,50,90,150,50,20,80, c400。按照重量貪心原則，確定裝載方案。按照重量貪心原則，確定裝載方案。|解：解：所考察貨箱的次序所考察貨箱的次序 :7, 3, 6, 8, 4, 1, 5, 2，最優(yōu)解最優(yōu)解x= 1, 0, 1, 1, 0, 1, 1, 1。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 30 例例2：最優(yōu)裝載：最優(yōu)裝載|算法描述：算法描述：templatevoid Loading(int x , Ty

23、pe 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 & wti = c; i+) xti = 1; c -= wti; 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 31 例例2：最優(yōu)裝載：最優(yōu)裝載|分析：分析：最優(yōu)裝載問(wèn)題滿足最優(yōu)裝載問(wèn)題滿足貪心選擇性質(zhì)貪心選擇性質(zhì)和和最優(yōu)子結(jié)構(gòu)性最優(yōu)子結(jié)構(gòu)性質(zhì)質(zhì)，故算法正確，能求得最優(yōu)解。，故算法正確，能求

24、得最優(yōu)解。時(shí)間復(fù)雜性：時(shí)間復(fù)雜性：n算法算法loading的主要計(jì)算量在于將集裝箱依其重量從小的主要計(jì)算量在于將集裝箱依其重量從小到大排序，故算法所需的計(jì)算時(shí)間為到大排序，故算法所需的計(jì)算時(shí)間為 O(nlogn)。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 32 例例3：0-1背包問(wèn)題背包問(wèn)題|問(wèn)題描述：?jiǎn)栴}描述：n給定給定n個(gè)物品和一個(gè)背包，物品個(gè)物品和一個(gè)背包，物品 i 的重量為的重量為wi ,其價(jià)值為其價(jià)值為vi ,背包的容量為背包的容量為c。n問(wèn)問(wèn):如何裝物品，使得裝入背包中物品總價(jià)值最如何裝物品，使得裝入背包中物品

25、總價(jià)值最大？大？11max0,1)niiiniiiiv xw xcx標(biāo)數(shù)：約條：，(目函束件算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 33 例例3：0-1背包問(wèn)題背包問(wèn)題|分析分析解決方案：解決方案：n分步裝入，在每一步過(guò)程中利用貪心準(zhǔn)則選擇分步裝入，在每一步過(guò)程中利用貪心準(zhǔn)則選擇一個(gè)物品裝入背包。一個(gè)物品裝入背包。n至少有三種看似合理的貪心策略：至少有三種看似合理的貪心策略： u重量貪心準(zhǔn)則重量貪心準(zhǔn)則u價(jià)值貪心準(zhǔn)則價(jià)值貪心準(zhǔn)則u價(jià)值密度貪心準(zhǔn)則價(jià)值密度貪心準(zhǔn)則算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川

26、師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 34 例例3：0-1背包問(wèn)題背包問(wèn)題n3,v 20,15,15 w100,10,10c= 1 0 5n 2 v 5 , 100 w10 , 20 c 25 n 3 v 60,100,120 w10 , 20,30 c50重量貪心準(zhǔn)則重量貪心準(zhǔn)則（0，1，1）30（1，0） 5（1，1，0）160價(jià)值貪心準(zhǔn)則價(jià)值貪心準(zhǔn)則（1，0，0）20（0，1）100（0，1，1）220價(jià)值密度貪心準(zhǔn)價(jià)值密度貪心準(zhǔn)則則（0，1，1）30（0，1）100（1，1，0）160三種策略都不能保證得到最優(yōu)解三種策略都不能保證得到最優(yōu)解算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算

27、法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 35 例例3：0-1背包問(wèn)題背包問(wèn)題|分析：分析：三種貪心策略都不能保證得到最優(yōu)解的原因三種貪心策略都不能保證得到最優(yōu)解的原因n重量貪心準(zhǔn)則重量貪心準(zhǔn)則n價(jià)值貪心準(zhǔn)則價(jià)值貪心準(zhǔn)則n價(jià)值密度貪心準(zhǔn)則價(jià)值密度貪心準(zhǔn)則u對(duì)于對(duì)于01背包問(wèn)題，貪心選擇不能得到最優(yōu)解的原因背包問(wèn)題，貪心選擇不能得到最優(yōu)解的原因是它是它無(wú)法保證最終能將背包裝滿無(wú)法保證最終能將背包裝滿。u部分閑置背包空間使單位重量背包空間所具有的價(jià)值部分閑置背包空間使單位重量背包空間所具有的價(jià)值降低了。降低了。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師

28、范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 36 例例3：0-1背包問(wèn)題背包問(wèn)題事實(shí)上事實(shí)上:n在考慮在考慮01背包問(wèn)題的物品選擇時(shí)，應(yīng)比較選背包問(wèn)題的物品選擇時(shí)，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終結(jié)果，擇該物品和不選擇該物品所導(dǎo)致的最終結(jié)果，然后再作出最好選擇。然后再作出最好選擇。n由此導(dǎo)出許多互相由此導(dǎo)出許多互相重疊的子問(wèn)題重疊的子問(wèn)題。n這正是動(dòng)態(tài)規(guī)劃法求解問(wèn)題的一個(gè)重要特征。這正是動(dòng)態(tài)規(guī)劃法求解問(wèn)題的一個(gè)重要特征。n動(dòng)態(tài)規(guī)劃法可以有效地解決動(dòng)態(tài)規(guī)劃法可以有效地解決01背包問(wèn)題。背包問(wèn)題。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算

29、機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 37 例例4：背包問(wèn)題：背包問(wèn)題|問(wèn)題描述：?jiǎn)栴}描述：給定給定n個(gè)物品和一個(gè)背包，物品個(gè)物品和一個(gè)背包，物品 i 的重量為的重量為wi ,其其價(jià)值為價(jià)值為vi ,背包的容量為背包的容量為c。問(wèn)問(wèn):如何裝物品，使得裝入背包中物品總價(jià)值最大？如何裝物品，使得裝入背包中物品總價(jià)值最大？11 max 011,2, niiiiii niv xw xcxin 標(biāo)數(shù)：約條： 目函束件算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 38 例例4：背包問(wèn)題：背包問(wèn)題|分析：分析：貪心準(zhǔn)則貪心準(zhǔn)則n重量重量n價(jià)值價(jià)

30、值n價(jià)值密度價(jià)值密度|可以證明：可以證明：按價(jià)值密度（單位價(jià)值）作為度量標(biāo)準(zhǔn)，背包問(wèn)按價(jià)值密度（單位價(jià)值）作為度量標(biāo)準(zhǔn)，背包問(wèn)題達(dá)到題達(dá)到最優(yōu)解最優(yōu)解。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 39 例例4：背包問(wèn)題：背包問(wèn)題|例如：例如：n3,v 20,15,15 w100,10,10c= 1 0 5n 2 v 5 , 100 w10 , 20 c 25 n 3 v 60,100,120 w10 , 20,30 c50重量貪心準(zhǔn)則重量貪心準(zhǔn)則（1,3/4）80價(jià)值貪心準(zhǔn)則價(jià)值貪心準(zhǔn)則（1,1/2,0）27.5（0,1,1）

31、220價(jià)值密度貪心價(jià)值密度貪心準(zhǔn)則準(zhǔn)則（0.85,1,1）47（1/2,1）102.5（1,1,2/3）240算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 40 例例4：背包問(wèn)題：背包問(wèn)題|算法描述算法描述void Knapsack(int n,float M,float *v,float * w ,float *x) Sort(n, v, w); /按單位價(jià)值排序按單位價(jià)值排序/ for (i =1;i = n;i+) xi = 0; /初始化初始化 float c = M; /c為背包剩余空間為背包剩余空間/ for (i

32、=1;i c) break; xi= 1; /放入物品放入物品i c-= wi; if(i= n) xi = c/wi;算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 41 例例4：背包問(wèn)題：背包問(wèn)題|算法分析算法分析: 排序?yàn)樗惴ǖ闹饕獣r(shí)間，故：排序?yàn)樗惴ǖ闹饕獣r(shí)間，故：T(n)=O(nlogn) 。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 42 貪心法與動(dòng)態(tài)規(guī)劃法的異同點(diǎn)貪心法與動(dòng)態(tài)規(guī)劃法的異同點(diǎn)|相同點(diǎn)相同點(diǎn)要求問(wèn)題具備最優(yōu)子結(jié)構(gòu)性質(zhì)。要求問(wèn)題具備最優(yōu)子結(jié)

33、構(gòu)性質(zhì)。|不同點(diǎn)不同點(diǎn)動(dòng)態(tài)規(guī)劃算法動(dòng)態(tài)規(guī)劃算法的另一個(gè)基本要素是的另一個(gè)基本要素是重疊子問(wèn)題性重疊子問(wèn)題性質(zhì)，質(zhì)，通常以自底向上的方式解各子問(wèn)題。通常以自底向上的方式解各子問(wèn)題。貪心算法貪心算法通常以自頂向下的方式進(jìn)行，以迭代的通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為規(guī)模更小的子問(wèn)題。將所求問(wèn)題簡(jiǎn)化為規(guī)模更小的子問(wèn)題。 （貪心選貪心選擇性質(zhì)擇性質(zhì)）算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 43 例例5：多機(jī)調(diào)度問(wèn)題：多機(jī)調(diào)度問(wèn)題|問(wèn)

34、題描述：?jiǎn)栴}描述：多機(jī)調(diào)度問(wèn)題要求給出一種作業(yè)調(diào)度方案，使所多機(jī)調(diào)度問(wèn)題要求給出一種作業(yè)調(diào)度方案，使所給的給的n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由m臺(tái)機(jī)器加工臺(tái)機(jī)器加工處理完成。處理完成。約定：約定：n每個(gè)作業(yè)均可在任何一臺(tái)機(jī)器上加工處理，但未完工每個(gè)作業(yè)均可在任何一臺(tái)機(jī)器上加工處理，但未完工前不允許中斷處理。前不允許中斷處理。n作業(yè)不能拆分成更小的子作業(yè)。作業(yè)不能拆分成更小的子作業(yè)。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 44 例例5：多機(jī)調(diào)度問(wèn)題：多機(jī)調(diào)度問(wèn)題|解決方案解決方案貪心算法貪心算法n短時(shí)優(yōu)

35、先短時(shí)優(yōu)先u需要需要短處理時(shí)間短處理時(shí)間作業(yè)優(yōu)先處理作業(yè)優(yōu)先處理n長(zhǎng)時(shí)優(yōu)先長(zhǎng)時(shí)優(yōu)先u需要需要長(zhǎng)處理時(shí)間長(zhǎng)處理時(shí)間作業(yè)優(yōu)先處理作業(yè)優(yōu)先處理u注：注：“長(zhǎng)時(shí)優(yōu)先長(zhǎng)時(shí)優(yōu)先”的貪心選擇策略可以設(shè)計(jì)出的貪心選擇策略可以設(shè)計(jì)出解多機(jī)調(diào)度問(wèn)題的較好的解多機(jī)調(diào)度問(wèn)題的較好的近似算法近似算法。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 45 例例5：多機(jī)調(diào)度問(wèn)題：多機(jī)調(diào)度問(wèn)題|“長(zhǎng)時(shí)優(yōu)先長(zhǎng)時(shí)優(yōu)先”貪心算法的求解分析：貪心算法的求解分析：當(dāng)當(dāng)nm時(shí)：時(shí)：n首先將首先將n個(gè)作業(yè)依其所需的處理時(shí)間從大到小個(gè)作業(yè)依其所需的處理時(shí)間從大到小排序，然后依

36、此順序?qū)⒆鳂I(yè)分配給空閑的處理排序，然后依此順序?qū)⒆鳂I(yè)分配給空閑的處理機(jī)，算法需要機(jī)，算法需要O(nlogn)的計(jì)算時(shí)間。的計(jì)算時(shí)間。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 46 例例5：多機(jī)調(diào)度問(wèn)題：多機(jī)調(diào)度問(wèn)題|例如：例如：設(shè)設(shè)7個(gè)獨(dú)立作業(yè)個(gè)獨(dú)立作業(yè)1,2,3,4,5,6,7，所需的處理時(shí)間分，所需的處理時(shí)間分別為別為2,14,4,16,6,5,3，由，由3臺(tái)機(jī)器臺(tái)機(jī)器M1M3加工處理。加工處理。機(jī)器機(jī)器調(diào)度方案調(diào)度方案M1M2M3J4J2J7J5J6J3J1所用時(shí)間所用時(shí)間1614+3=176+5+4+2=17 算法設(shè)

37、計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 47 應(yīng)用專題二應(yīng)用專題二|圖問(wèn)題中的貪心法圖問(wèn)題中的貪心法例例1：Huffman 編碼問(wèn)題編碼問(wèn)題例例2：?jiǎn)卧袋c(diǎn)最短路徑問(wèn)題：?jiǎn)卧袋c(diǎn)最短路徑問(wèn)題：Dijkstra算法算法例例3：最小生成樹(shù)問(wèn)題：最小生成樹(shù)問(wèn)題：Prim算法算法例例4：TSP問(wèn)題問(wèn)題算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 48 例例1：Huffman編碼編碼|問(wèn)題提出問(wèn)題提出:通訊過(guò)程中需將傳輸?shù)男畔⑥D(zhuǎn)換為二進(jìn)制碼。由通訊過(guò)程中需將傳輸?shù)男畔⑥D(zhuǎn)換為二進(jìn)

38、制碼。由于英文字母使用頻率不同，若頻率高的字母對(duì)應(yīng)于英文字母使用頻率不同，若頻率高的字母對(duì)應(yīng)短的編碼，頻率低的字母對(duì)應(yīng)長(zhǎng)的編碼，傳輸?shù)亩痰木幋a，頻率低的字母對(duì)應(yīng)長(zhǎng)的編碼，傳輸?shù)臄?shù)據(jù)總量就會(huì)降低。要求找到一個(gè)編碼方案數(shù)據(jù)總量就會(huì)降低。要求找到一個(gè)編碼方案,使傳使傳輸?shù)臄?shù)據(jù)量最少。輸?shù)臄?shù)據(jù)量最少。|分析：分析：為能正確譯碼，編碼需采用前綴碼，前綴碼和二為能正確譯碼，編碼需采用前綴碼，前綴碼和二叉樹(shù)一一對(duì)應(yīng)。問(wèn)題可化為求一棵最優(yōu)二叉樹(shù)。叉樹(shù)一一對(duì)應(yīng)。問(wèn)題可化為求一棵最優(yōu)二叉樹(shù)。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 49 例例1

39、： Huffman編碼編碼|貪心選擇性貪心選擇性設(shè)設(shè)T T為帶權(quán)為帶權(quán)w w1 1 w w2 2. . w wt t的最優(yōu)樹(shù)，的最優(yōu)樹(shù)，n帶權(quán)帶權(quán)w w1 1和和w w2 2的樹(shù)葉的樹(shù)葉v vw w1 1和和v vw w2 2是兄弟。是兄弟。n以以v vw w1 1和和v vw w2 2為兒子的分枝點(diǎn)為兒子的分枝點(diǎn), ,其通路長(zhǎng)度最長(zhǎng)。其通路長(zhǎng)度最長(zhǎng)。|最優(yōu)子結(jié)構(gòu)最優(yōu)子結(jié)構(gòu):設(shè)設(shè)T T為帶權(quán)為帶權(quán)w w1 1 w w2 2. . w wt t的最優(yōu)樹(shù)，若將以帶權(quán)的最優(yōu)樹(shù)，若將以帶權(quán)w w1 1和和w w2 2的樹(shù)葉為兒子的分枝點(diǎn)改為帶權(quán)的樹(shù)葉為兒子的分枝點(diǎn)改為帶權(quán)w w1 1+w+w2 2的的

40、樹(shù)葉，得到一棵新樹(shù)樹(shù)葉，得到一棵新樹(shù)T T ，則則TT也是最優(yōu)樹(shù)。也是最優(yōu)樹(shù)。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 50 例例1： Huffman編碼編碼|Huffman算法算法|例如：例如：求帶權(quán)為求帶權(quán)為2,2,3,3,5的最優(yōu)二元樹(shù)的最優(yōu)二元樹(shù).算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 51 例例2：?jiǎn)卧袋c(diǎn)最短路徑單源點(diǎn)最短路徑|問(wèn)題描述問(wèn)題描述設(shè)給定一個(gè)帶權(quán)有向圖設(shè)給定一個(gè)帶權(quán)有向圖G=V，E，指定指定G中一中一個(gè)頂點(diǎn)個(gè)頂點(diǎn) vs為源點(diǎn)為源點(diǎn),

41、現(xiàn)在要求出從現(xiàn)在要求出從vs到圖中其余各個(gè)到圖中其余各個(gè)頂點(diǎn)之間的最短路徑，該問(wèn)題稱為頂點(diǎn)之間的最短路徑，該問(wèn)題稱為單源點(diǎn)最短路單源點(diǎn)最短路徑問(wèn)題徑問(wèn)題。|Dijkstra算法算法從圖中的給定源點(diǎn)從圖中的給定源點(diǎn)vs到其他各個(gè)頂點(diǎn)之間客觀上應(yīng)存在一到其他各個(gè)頂點(diǎn)之間客觀上應(yīng)存在一條最短路徑，在這組最短路徑中，按條最短路徑，在這組最短路徑中，按路徑長(zhǎng)度遞增次序路徑長(zhǎng)度遞增次序，依次求出到不同頂點(diǎn)的最短路徑長(zhǎng)度。依次求出到不同頂點(diǎn)的最短路徑長(zhǎng)度。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 52 例例2：?jiǎn)卧袋c(diǎn)最短路徑單源點(diǎn)最短路徑

42、|基本思想：基本思想：設(shè)置一個(gè)頂點(diǎn)集合設(shè)置一個(gè)頂點(diǎn)集合S并不斷作并不斷作貪心選擇貪心選擇來(lái)擴(kuò)充該集合。來(lái)擴(kuò)充該集合。Step1：初始時(shí)：初始時(shí)nS=vs，n設(shè)置距離數(shù)組設(shè)置距離數(shù)組distu設(shè)設(shè)u是是G的某一頂點(diǎn)，的某一頂點(diǎn)， distu記錄記錄vs到到u且中間只經(jīng)過(guò)且中間只經(jīng)過(guò)S中頂點(diǎn)的中頂點(diǎn)的路徑的長(zhǎng)度。路徑的長(zhǎng)度。Step2：從：從VS中取出最短路徑長(zhǎng)度的頂點(diǎn)中取出最短路徑長(zhǎng)度的頂點(diǎn)u，將將u添加到添加到S中，同時(shí)對(duì)數(shù)組中，同時(shí)對(duì)數(shù)組dist做必要的修正。做必要的修正。Step3：算法重復(fù)：算法重復(fù)Step2 ,直到直到S=V，dist就記錄了從就記錄了從vs到所有到所有其他頂點(diǎn)之間的最

43、短路徑長(zhǎng)度。其他頂點(diǎn)之間的最短路徑長(zhǎng)度。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 53 例例2：?jiǎn)卧袋c(diǎn)最短路徑單源點(diǎn)最短路徑|例：?jiǎn)卧袋c(diǎn)最短路徑算法運(yùn)行例：?jiǎn)卧袋c(diǎn)最短路徑算法運(yùn)行實(shí)實(shí)例。例。v0v5v4v1v3v21006030102050510v2v4v3v5v1算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 54 例例3：最小生成樹(shù)：最小生成樹(shù)|基本定義基本定義子圖子圖生成子圖生成子圖生成樹(shù)生成樹(shù)算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川

44、師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 55 例例3：最小生成樹(shù)：最小生成樹(shù)|基本定義基本定義子圖子圖生成子圖生成子圖生成樹(shù)生成樹(shù)n一個(gè)連通無(wú)向圖一個(gè)連通無(wú)向圖G=(V, E)，邊權(quán)為邊權(quán)為W=W1,W2,Wn-1，且且 T 是是 G 的生成樹(shù)，其邊權(quán)總和記為：的生成樹(shù)，其邊權(quán)總和記為： W(T)。最小生成樹(shù)最小生成樹(shù)nT*：11()niiW TW( *)min( )TW TW T算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 56 例例3：最小生成樹(shù)：最小生成樹(shù)|最小生成樹(shù)的性質(zhì)最小生成樹(shù)的性質(zhì)設(shè)一個(gè)連通帶權(quán)圖設(shè)一個(gè)連

45、通帶權(quán)圖G=(V, E)，S是是V的一個(gè)真子集。的一個(gè)真子集。如果邊如果邊(u, v) E 且且 u S, v VS, 而且所有這樣的邊而且所有這樣的邊(u, v)的權(quán)的權(quán)cuv最小，則一定存在最小，則一定存在G的一棵最小生成樹(shù)，它以的一棵最小生成樹(shù)，它以(u, v)為其中的一條邊。為其中的一條邊。|證明：證明：uuvvSVS算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 57 例例3：最小生成樹(shù)：最小生成樹(shù)|分析：分析：獲得最小生成樹(shù)的貪心方法是獲得最小生成樹(shù)的貪心方法是按照邊的成本的和按照邊的成本的和有最小增量為度量標(biāo)準(zhǔn)有最小

46、增量為度量標(biāo)準(zhǔn)，逐條邊地構(gòu)造這棵樹(shù)。，逐條邊地構(gòu)造這棵樹(shù)。根據(jù)使用貪心策略的不同，可以分為：根據(jù)使用貪心策略的不同，可以分為：nPrim 算法算法n Kruskal 算法。算法。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 58 例例3：最小生成樹(shù)：最小生成樹(shù)|Prim算法算法基本思想：基本思想：n先置先置S=1，n只要只要S是是V的真子集，就作如下的的真子集，就作如下的貪心選擇貪心選擇：u選取滿足條件選取滿足條件i S, j VS且權(quán)且權(quán)cij最小的最小的邊，并將頂點(diǎn)邊，并將頂點(diǎn)j添加到添加到S中，中，n直到直到S = V為止

47、。為止。注意：注意：T始終是一棵樹(shù)。始終是一棵樹(shù)。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 59 例例3：最小生成樹(shù)：最小生成樹(shù)算法描述算法描述void Prim() T= ; / T存放最小生成樹(shù)的邊存放最小生成樹(shù)的邊 S =1；/ S存放最小生成樹(shù)的頂點(diǎn)存放最小生成樹(shù)的頂點(diǎn) while(S!=V) ( i, j ) = i S, j VS的最小權(quán)邊；的最小權(quán)邊； T = T ( i, j )； S = S j; 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳

48、 60 例例3：最小生成樹(shù)：最小生成樹(shù)|Prim算法過(guò)程示例：算法過(guò)程示例：v3v2v4v5v66155536426v1v3v6v4v2v5v1算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 61 例例3：最小生成樹(shù)：最小生成樹(shù)|Kruskal算法算法1. T=V， ；2. (u0,v0)= min(cost(u,v) |u，v分屬不同的連通分分屬不同的連通分量量,將邊將邊(u0,v0 )并入并入T的邊集合的邊集合TE；3. 重復(fù)第重復(fù)第2步，直至所有頂點(diǎn)在同一個(gè)連通分量中步，直至所有頂點(diǎn)在同一個(gè)連通分量中為止。為止。|注意：注意

49、：生成最小生成樹(shù)的過(guò)程中，生成最小生成樹(shù)的過(guò)程中，T一般是森林，最后才變?yōu)橐话闶巧郑詈蟛抛優(yōu)橐豢脴?shù)。一棵樹(shù)。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 62 例例3：最小生成樹(shù)：最小生成樹(shù)|算法描述算法描述void Kruskal() T= ; / T存放最小生成樹(shù)的邊存放最小生成樹(shù)的邊 while( T的邊少于的邊少于n1) 從邊集從邊集E中選一條最小權(quán)邊中選一條最小權(quán)邊( v, w )； 從邊集從邊集E中刪去邊中刪去邊( v, w )； if （邊邊( v, w )在在T中不生成環(huán)）中不生成環(huán)） 將將( v, w )加

50、到加到T； else 舍棄舍棄( v, w )； 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 63 例例3：最小生成樹(shù)：最小生成樹(shù)|Kruskal過(guò)程示例過(guò)程示例：v3v2v4v5v66155536426v115342v3v2v4v5v6v1算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 64 例例4： TSP問(wèn)題問(wèn)題|問(wèn)題描述問(wèn)題描述637322335v1v5v2v4v32算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算

51、機(jī)科學(xué)學(xué)院 劉芳劉芳 65 例例4： TSP問(wèn)題問(wèn)題|分析：分析：求解求解TSP問(wèn)題至少有兩種貪心策略是合理的貪心問(wèn)題至少有兩種貪心策略是合理的貪心策略策略n貪心策略貪心策略1：最近鄰點(diǎn)最近鄰點(diǎn)策略策略n貪心策略貪心策略2：最短鏈接最短鏈接策略策略算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 66 貪心策略貪心策略1：最近鄰點(diǎn)策略：最近鄰點(diǎn)策略|最近鄰點(diǎn)策略：最近鄰點(diǎn)策略：從任意城市出發(fā)，每次在沒(méi)有到過(guò)的城市中選擇從任意城市出發(fā)，每次在沒(méi)有到過(guò)的城市中選擇最近的一個(gè)，直到經(jīng)過(guò)了所有的城市，最后回到最近的一個(gè)，直到經(jīng)過(guò)了所有的城市

52、，最后回到出發(fā)城市。出發(fā)城市。|例如：例如：637322335v1v5v2v4v32算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 67 (3) 城市城市3城市城市5 (4) 城市城市5城市城市2 (5) 城市城市2城市城市1 25221543225221543232522154327363215432233215432C= 3 3 2 63 7 3 23 7 2 52 3 2 36 2 5 3 5城市的代價(jià)矩陣城市的代價(jià)矩陣 (1) 城市城市1城市城市4 (2) 城市城市4城市城市3貪心策略貪心策略1：最近鄰點(diǎn)策略：最近鄰點(diǎn)策略

53、算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 68 貪心策略貪心策略1：最近鄰點(diǎn)策略：最近鄰點(diǎn)策略|算法：算法：輸入輸入:城市的數(shù)目城市的數(shù)目n,代價(jià)矩陣代價(jià)矩陣c,起點(diǎn)城市起點(diǎn)城市v0輸出輸出: 最小代價(jià)路線最小代價(jià)路線tour，cost為最小代價(jià)為最小代價(jià)tour=0; cost=0; v=v0 ; V=V-v0;for （ k=1；kn;k+) /查找與頂點(diǎn)查找與頂點(diǎn)v鄰接的最小代價(jià)邊鄰接的最小代價(jià)邊(v, w)并且并且wV； tour+= (v,w) ; cost+= c(v,w) ; v=w; V=V-w;tour+=

54、(v, v0); cost+= c(v, v0) ; printf( tour, cost )；算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 69 貪心策略貪心策略1：最近鄰點(diǎn)策略：最近鄰點(diǎn)策略|分析分析算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度O(n2)|注意：注意：用最近鄰點(diǎn)貪心策略求解用最近鄰點(diǎn)貪心策略求解TSP問(wèn)題所得的結(jié)果不問(wèn)題所得的結(jié)果不一定是最優(yōu)解，上圖從城市一定是最優(yōu)解，上圖從城市1出發(fā)的最優(yōu)解是出發(fā)的最優(yōu)解是125431，總代價(jià)只有，總代價(jià)只有13。當(dāng)當(dāng)圖中頂點(diǎn)個(gè)數(shù)較多并且各邊的代價(jià)值分布比較圖中頂點(diǎn)個(gè)數(shù)較多并且各邊的代

55、價(jià)值分布比較均勻均勻時(shí)，最近鄰點(diǎn)策略可以給出時(shí)，最近鄰點(diǎn)策略可以給出較好的較好的近似解近似解，不過(guò)，這個(gè)近似解以何種程度近似于最優(yōu)解，卻不過(guò)，這個(gè)近似解以何種程度近似于最優(yōu)解，卻難以保證。難以保證。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 70 貪心策略貪心策略2：最短鏈接策略：最短鏈接策略|最短鏈接策略最短鏈接策略每次在整個(gè)圖的范圍內(nèi)選擇每次在整個(gè)圖的范圍內(nèi)選擇最短邊最短邊加入到解集合加入到解集合中，但是，要保證加入解集合中的邊最終形成一中，但是，要保證加入解集合中的邊最終形成一個(gè)哈密頓回路。個(gè)哈密頓回路。因此，當(dāng)從剩余邊

56、集因此，當(dāng)從剩余邊集E按照權(quán)值中選擇一條邊按照權(quán)值中選擇一條邊(u, v)加入解集合加入解集合S中，并盡可能權(quán)值小的邊。應(yīng)滿足中，并盡可能權(quán)值小的邊。應(yīng)滿足以下條件：以下條件：n邊邊(u, v)加入解集合加入解集合S后，后，S中不產(chǎn)生回路；中不產(chǎn)生回路；n邊邊(u, v) 加入解集合加入解集合S后，后，S中不產(chǎn)生分枝；中不產(chǎn)生分枝；n使權(quán)值盡可能小。使權(quán)值盡可能小。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 71 貪心策略貪心策略2：最短鏈接策略：最短鏈接策略|例如：例如：637322335v1v5v2v4v32算法設(shè)計(jì)與分析

57、算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 72 貪心策略貪心策略2：最短鏈接策略：最短鏈接策略215432215432C= 3 3 2 63 7 3 23 7 2 52 3 2 36 2 5 3 5城市的代價(jià)矩陣城市的代價(jià)矩陣 (1) 城市城市1城市城市4 (2) 城市城市5城市城市22(3) 城市城市4城市城市3 (4) 城市城市2城市城市1 (5) 城市城市3到城市到城市5222154322221543222215432353算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳

58、 73 P= ; E=E; /候選集合，初始時(shí)為圖中所有邊候選集合，初始時(shí)為圖中所有邊 do 循環(huán)直到集合循環(huán)直到集合P中包含中包含n- -1條邊條邊 在在E中選取最短邊中選取最短邊(u, v); E=E- -(u, v); if (頂點(diǎn)頂點(diǎn)u和和v在在P中不連通中不連通 and 不產(chǎn)生分枝不產(chǎn)生分枝) then P=P+(u, v); while (集合集合P中的邊數(shù)少于中的邊數(shù)少于n-1) 貪心策略貪心策略2：最短鏈接策略：最短鏈接策略|算法描述：算法描述：頂點(diǎn)數(shù)頂點(diǎn)數(shù):n ,代價(jià)矩陣代價(jià)矩陣:c ,E:候選邊集合候選邊集合,P:經(jīng)過(guò)的邊集。經(jīng)過(guò)的邊集。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法

59、貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 74 貪心策略貪心策略2：最短鏈接策略：最短鏈接策略|算法的時(shí)間性能分析：算法的時(shí)間性能分析：對(duì)于對(duì)于“兩個(gè)頂點(diǎn)是否連通以及是否會(huì)產(chǎn)生分枝兩個(gè)頂點(diǎn)是否連通以及是否會(huì)產(chǎn)生分枝”的操作的操作n可以用并查集的操作將其時(shí)間性能提高到可以用并查集的操作將其時(shí)間性能提高到O(n)；如果操作如果操作“ 在在E中選取最短邊中選取最短邊(u, v) ”n用順序查找，則選取最短邊的操作可以是用順序查找，則選取最短邊的操作可以是O(n)，此時(shí)算此時(shí)算法的時(shí)間性能為法的時(shí)間性能為O(n2)。n如果采用堆排序的方法將集合如果采用堆排序的方法將集

60、合E中的邊建立堆，則選中的邊建立堆，則選取最短邊的操作可以是取最短邊的操作可以是O(log2n)，此時(shí)算法的時(shí)間性能此時(shí)算法的時(shí)間性能為為O(nlog2n)。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析貪心算法貪心算法 四川師范大學(xué)四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 劉芳劉芳 75 應(yīng)用專題三應(yīng)用專題三|貪心策略：貪心策略：不僅僅可以應(yīng)用于不僅僅可以應(yīng)用于最優(yōu)化問(wèn)題最優(yōu)化問(wèn)題中；中；有時(shí)在解決有時(shí)在解決構(gòu)造類構(gòu)造類等問(wèn)題時(shí)，用這種策略可以盡等問(wèn)題時(shí)，用這種策略可以盡快地構(gòu)造出一組解?？斓貥?gòu)造出一組解。|其他應(yīng)用專題其他應(yīng)用專題例例1：汽車加油問(wèn)題汽車加油問(wèn)題例例2：旅行家的預(yù)算旅行家的預(yù)算例例3：數(shù)列極差問(wèn)題