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

1、 設(shè)有n個(gè)活動(dòng)的集合E=1,2,n，其中每個(gè)活動(dòng)都要求使用同一資源，如演講會(huì)場(chǎng)等，而在同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能使用這一資源。每個(gè)活動(dòng)i都有一個(gè)要求使用該資源的起始時(shí)間si和一個(gè)結(jié)束時(shí)間fi,且si fi 。如果選擇了活動(dòng)i，則它在半開時(shí)間區(qū)間si, fi)內(nèi)占用資源。若區(qū)間si, fi)與區(qū)間sj, fj)不相交，則稱活動(dòng)i與活動(dòng)j是相容的。也就是說，當(dāng)sifj或sjfi時(shí)，活動(dòng)i與活動(dòng)j相容。下面給出解活動(dòng)安排問題的貪心算法GreedySelectorGreedySelector :各活動(dòng)的起始時(shí)間和結(jié)各活動(dòng)的起始時(shí)間和結(jié)束時(shí)間存儲(chǔ)于數(shù)組束時(shí)間存儲(chǔ)于數(shù)組s s和和f f中且按結(jié)束時(shí)間的非減中

2、且按結(jié)束時(shí)間的非減序排列序排列 所謂貪心選擇性質(zhì)貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解整體最優(yōu)解可以通過一系列局部最優(yōu)局部最優(yōu)的選擇，即貪心選擇來達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。 動(dòng)態(tài)規(guī)劃算法通常以自底向上自底向上的方式解各子問題，而貪心算法則通常以自頂向下自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡(jiǎn)化為規(guī)模更小的子問題。 對(duì)于一個(gè)具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。2 2、最優(yōu)子結(jié)構(gòu)性質(zhì)、最優(yōu)子結(jié)構(gòu)性質(zhì)3、貪心算法與動(dòng)態(tài)規(guī)劃算法的差異 在選擇裝入背包的物

3、品時(shí)，對(duì)每種物品在選擇裝入背包的物品時(shí)，對(duì)每種物品i i只有只有2 2種選擇，即種選擇，即裝入背包或不裝入背包。不能將物品裝入背包或不裝入背包。不能將物品i i裝入背包多次，也不能只裝入背包多次，也不能只裝入部分的物品裝入部分的物品i i。 這2類問題都具有最優(yōu)子結(jié)構(gòu)最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似，但背包問題可以用貪心算法求解，而0-1背包問題卻不能用貪心算法求解。 用貪心算法解背包問題的基本步驟： 算法算法knapsackknapsack的的主要計(jì)算時(shí)間在于將主要計(jì)算時(shí)間在于將各種物品依其單位重各種物品依其單位重量的價(jià)值從大到小排量的價(jià)值從大到小排序。因此，算法的計(jì)序。因此，算法的計(jì)算時(shí)間上界為算時(shí)間上界為O O（nlognnlogn）。）。為了證明算法的正確為了證明算法的正確性，還必須證明背包性，還必須證明背包問題具有貪心選擇性問題具有貪心選擇性質(zhì)質(zhì)。)()()(cdcfTBTCc Dijkstra算法的迭代過程： )(nO)(2nO)(2nO)(2nO)log(eeO)(2ne)(2noe 約定，每個(gè)作業(yè)均可在任何一臺(tái)機(jī)器上加工處理，但未約定，每個(gè)作業(yè)均可在任何一臺(tái)機(jī)器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。mn mn ),(GGGISMAxxWAW)()