貪心算法：

在對(duì)問題求解時(shí)，總做出當(dāng)前看來最好的選擇蛋褥，即求“目光短淺”的局部最優(yōu)，是一種近似最優(yōu)解睛驳，而不是從整體考慮烙心。

?

????????有時(shí)我們也可以嘗試使用窮舉法弃理，但是當(dāng)問題規(guī)模較大時(shí)溃论，窮舉法就會(huì)顯得很浪費(fèi)資源屎蜓。所以轉(zhuǎn)而使用貪心算法。

????????貪心算法是指當(dāng)一個(gè)問題可以分解成若干個(gè)子問題時(shí)，每個(gè)子問題的求解算灸，都選擇局部解最優(yōu)解扼劈。然后將子問題的局部最優(yōu)解合成原問題的解。

舉個(gè)栗子：

? ? ?

? ? ? ? 現(xiàn)有5元荐吵、2元、1元赊瞬、5角先煎、2角、1角的硬幣巧涧，需要找給顧客4元6角現(xiàn)金薯蝎，利用貪心算法，設(shè)(貪心選擇性質(zhì))為每次都選擇所有面值中不超過每次還需要的現(xiàn)金的最大面值谤绳。得：第一次2元占锯，還需2元6角；第二次2元缩筛，還需6角消略；第三次5角，還需1角瞎抛；第四次1角艺演。以上四次子問題的的求解均滿足，4張零錢共4元6角，解決的初始原問題钞艇。

? ? ????好啦啄寡，我們來從頭看一遍這個(gè)問題：第一步：共把一個(gè)問題分成了四個(gè)子問題。第二步：對(duì)每一次挑出的零錢做選擇哩照。第三步：所有挑出零錢的結(jié)果合成最優(yōu)解挺物。

（涉及概念）：

? ? ? ??【候選解集C】：?jiǎn)栴}的可能解，問題的最終解都取自于候選解集C飘弧。[本例中相當(dāng)于總的6種面值的零錢识藤。]

? ? ? ? 【解集S】：每一步形成的解的集合，雖貪心選擇的進(jìn)行次伶，S不斷擴(kuò)展痴昧，最終構(gòu)成滿足問題的完整解。[本例是這樣變化的{2}-->{2冠王，2}-->{2赶撰，2，0.5}-->{2柱彻，2豪娜，0.5，0.1}哟楷。]

? ? ? ?【解決函數(shù)solution】：檢查解集是否構(gòu)成問題完整解瘤载。[本例2+2+0.5+0.1=4.6。]

? ? ? ? 【選擇函數(shù)select】：（即貪心策略）與目標(biāo)函數(shù)有關(guān)卖擅，指出哪個(gè)問題最有希望構(gòu)成問題的解鸣奔。[本例每次選擇零錢中面值最大的硬幣。]

? ? ? ? 【可行函數(shù)feasible】：一個(gè)解集種加入一候選對(duì)象后惩阶，查看是否滿足約束條件挎狸。[本例每次選擇的和之前解集中的相加，不超過應(yīng)找零錢琳猫。]

抽象來看伟叛，求解步驟即為：

? ? ????①?分解：將原問題分解為若干相互獨(dú)立的階段。

????????②?求解：對(duì)于每個(gè)階段求局部最優(yōu)解脐嫂，即進(jìn)行貪心選擇统刮。在每個(gè)階段，選擇一旦做出就不可更改账千。做出貪心選擇的依據(jù)稱為貪心準(zhǔn)則侥蒙。貪心準(zhǔn)則的制定是用貪心算法解決最優(yōu)化問題的關(guān)鍵，它關(guān)系到問題能否得到成功解決及解決質(zhì)量的高低匀奏。

????????③?合并：將各個(gè)階段的解合并為原問題的一個(gè)可行解鞭衩。

算法特性：

????????通過分步?jīng)Q策，每步都形成局部解，利用這些局部解來構(gòu)成問題的最終解论衍；如果要求最終的解是最優(yōu)解瑞佩，每步的解必須是當(dāng)前步驟的最優(yōu)解。從問題的某一個(gè)初始解來逐步逼近給定的目標(biāo)坯台，以盡可能快地求得最優(yōu)解炬丸。

????????當(dāng)然，如果我們把面值換一下蜒蕾，如繼續(xù)上面的問題稠炬，若我們需要照給顧客四角，①我們就不能保證用貪心算法解得的答案是問題的最優(yōu)解咪啡。②可以看出貪心算法求解的每一步只看當(dāng)前是否滿足局部最優(yōu)解首启，而不考慮在后面看來這些選擇是否合理做過的決定并不會(huì)因?yàn)楹罄m(xù)問題而改變，無(wú)回溯過程屬于自頂向下求解撤摸。

????????最優(yōu)子結(jié)構(gòu)性質(zhì)（問題最優(yōu)解特性）：當(dāng)一個(gè)問題的最優(yōu)解包含子問題最優(yōu)解時(shí)毅桃，稱該問題具有最優(yōu)子結(jié)構(gòu)特性。

設(shè)計(jì)模式：

```

Greedy(A,n)???

{

A[0:n-1]包含n個(gè)輸入愁溜；

?將解向量solution初始化為空疾嗅；

??? for(i=0;i<n;i++)

??? {???????????????????

x=select(A);???? ????????????? //從問題的某一初始解出發(fā)

???????if(feasiable(solution,x))???????

solution=union(solution,x)外厂；//部分解空間進(jìn)行合并

?}

return（解向量solution）冕象；

}

```

優(yōu)缺點(diǎn)：

????????優(yōu)點(diǎn)：算法簡(jiǎn)單，求解速度快汁蝶，時(shí)間空間復(fù)雜度低渐扮。

????????缺點(diǎn)：需要證明要求的問題的解是最優(yōu)解。

：

? ? ? ? 給定n種物品和一個(gè)容量為C的背包墓律，物品i重量是wi，其價(jià)值為vi幔亥，背包問題是如何選擇裝入背包的物品耻讽，使得裝入背包中物品的總價(jià)值最大？

（1）0/1背包問題：要么裝入帕棉，要么不裝入针肥。

（2）一般背包問題：物品是可以分割的，可將物品部分裝入背包中香伴。

最好的貪心策略是選擇單位重量?jī)r(jià)值最大的物品慰枕。

時(shí)間復(fù)雜度為O（nlogn）

????????有一批集裝箱要裝上一艘載重量為c的輪船即纲。其中集裝箱i的重量為wi具帮。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。

最好的貪心策略是選擇最輕先裝蜂厅。

計(jì)算時(shí)間O（nlogn）

????????設(shè)有n個(gè)獨(dú)立的作業(yè)10,1，…掘猿，m1}锹雏，由m臺(tái)相同的機(jī)器{M。.M1术奖，…礁遵，M1}進(jìn)行加工處理，作業(yè)i所需的處理時(shí)間為t（0≤ism1）采记，每個(gè)作業(yè)均可在一臺(tái)機(jī)器上加工處理佣耐，但不可間斷、拆分唧龄。多機(jī)調(diào)度問題（ Multi-Machine Scheduling Problem）要求給出一種作業(yè)調(diào)度方案兼砖，使所給的n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由m臺(tái)機(jī)器加工處理完成。

最好的貪心策略是選擇最長(zhǎng)處理時(shí)間作業(yè)優(yōu)先既棺，把處理時(shí)間最長(zhǎng)的作業(yè)分配給最先空閑的機(jī)器讽挟，保證處理時(shí)間長(zhǎng)的作業(yè)優(yōu)先處理，整體上獲得盡可能短的處理時(shí)間丸冕。

時(shí)間復(fù)雜度：當(dāng)m<<n時(shí)耽梅，為O(m*n)

????????設(shè)有n個(gè)活動(dòng)的集合E={1,2胖烛，…眼姐，n}，其中每個(gè)活動(dòng)都要求使用同一資源（如演講會(huì)場(chǎng)）佩番，而在同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能使用這一資源众旗。每個(gè)活動(dòng)都有個(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)與活動(dòng)是相容的。也就是說沃琅，當(dāng)si>=fj或sj<=fi時(shí)哗咆，活動(dòng)i與活動(dòng)j相容∫婷迹活動(dòng)安排問題要求在所給的活動(dòng)集合中選出最大的相容活動(dòng)子集晌柬。

最好的貪心策略是選擇最早結(jié)束時(shí)間姥份，這樣使下一個(gè)活動(dòng)今早開始。

算法效率：

????????若輸入進(jìn)去的活動(dòng)按時(shí)間已排好順序年碘，則時(shí)間復(fù)雜度為O（n）澈歉；

? ? ? ? 若輸入進(jìn)去的活動(dòng)未按時(shí)間已排好順序，則時(shí)間復(fù)雜度為O（nlogn）屿衅；【排序消耗】

時(shí)間復(fù)雜度：O（n2）

TSP問題：旅行商問題，即TSP問題（Traveling Salesman Problem）又譯為旅行推銷員問題涤久、貨郎擔(dān)問題涡尘，是數(shù)學(xué)領(lǐng)域中著名問題之一。假設(shè)有一個(gè)旅行商人要拜訪n個(gè)城市响迂，他必須選擇所要走的路徑考抄，路徑的限制是每個(gè)城市只能拜訪一次，而且最后要回到原來出發(fā)的城市蔗彤。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值川梅。

（1）

最近鄰點(diǎn)貪心策略所得結(jié)果不一定是最優(yōu)解。

時(shí)間復(fù)雜度：O（n2）

（2）

時(shí)間復(fù)雜度：

????最短邊順序查找O（n2）

????選取最短邊操作：O(nlog2 n)

（與最短連接相似）

prim算法（邊稠密）：

最近頂點(diǎn)策略：

時(shí)間復(fù)雜度：O（n2）

克魯斯卡爾算法（邊稀疏）：

最短邊策略：

時(shí)間復(fù)雜度：O（elog2 e）

e為無(wú)向連通圖中邊的個(gè)數(shù)贫途。

貪心法求解圖著色問題可能但不能保證找到一個(gè)最優(yōu)解待侵。

https://blog.csdn.net/qq_41289920/article/details/83582478