貪心算法
先來比較一下貪心算法和動(dòng)態(tài)規(guī)劃
貪心算法是指在對(duì)問題求解時(shí)故黑，總是做出在當(dāng)前看來是最好的選擇遥诉，不考慮整體拢驾，只考慮局部最優(yōu)，所以它不一定能得到最優(yōu)解定铜；
動(dòng)態(tài)規(guī)劃則是每個(gè)步驟都要進(jìn)行一次選擇阳液，但選擇通常要依賴子問題的解，所以它是考慮整體的揣炕，由于通常要依賴子問題的解帘皿，所以一般選自自底向上自帶備忘的機(jī)制，所以一定是最優(yōu)解祝沸；
最優(yōu)子結(jié)構(gòu)的概念
如果一個(gè)問題的解包含其子問題的最優(yōu)解矮烹，則稱該問題具有最優(yōu)子結(jié)構(gòu)越庇，也就是求解大問題的解罩锐，是通過求解小問題取解決
如果理解了最優(yōu)子結(jié)構(gòu)，則會(huì)發(fā)現(xiàn)貪心算法和動(dòng)態(tài)規(guī)劃都利用了最優(yōu)子結(jié)構(gòu)的性質(zhì)
實(shí)現(xiàn)該算法的過程
從問題的某一初始解出發(fā)
while 能朝給定總目標(biāo)前進(jìn)一步 do
求出可行解的一個(gè)解元素
由所有解元素組合成問題的一個(gè)可行解
典型的可用貪心來解的問題有
最小生成樹卤唉、分?jǐn)?shù)背包問題（類似0-1背包問題涩惑，只不過可以取物體的一部分）
用分?jǐn)?shù)背包問題舉個(gè)例子
W=30（所選物體不能超過30）
物品：A B C
重量：20 5? 20
價(jià)值：40 20 20
這個(gè)時(shí)候的貪心選擇肯定是選擇單位價(jià)值量最高的
所以先選擇B，再選擇A?
再從C中選擇5??
這時(shí)價(jià)值肯定最大
但貪心算法一開始就說了桑驱，并不保證最優(yōu)解竭恬，所以有時(shí)會(huì)配合隨機(jī)算法（算法導(dǎo)論第三版第五章有講）使用?
一般來說貪心算法的代碼比動(dòng)態(tài)規(guī)劃簡(jiǎn)單的多
回溯算法
回溯法概念
通常采取深度遍歷的形式，按照某種規(guī)則的能夠避免某些不必要搜索的窮舉式搜索
解空間（所有解的集合）
可以組織成一棵解集合的樹
解集合樹中的節(jié)點(diǎn)分為幾種
擴(kuò)展節(jié)點(diǎn)
在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處熬的，搜索向縱深方向移至一個(gè)新結(jié)點(diǎn)痊硕。這個(gè)結(jié)點(diǎn)就成為一個(gè)新的活結(jié)點(diǎn)，并成為當(dāng)前擴(kuò)展結(jié)點(diǎn)押框。
死節(jié)點(diǎn)
如果在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處不能再向縱深方向移動(dòng)岔绸，則當(dāng)前的擴(kuò)展結(jié)點(diǎn)就成為死結(jié)點(diǎn)，此時(shí)應(yīng)往回移動(dòng)（回溯）至最近的一個(gè)活結(jié)點(diǎn)處，并使這個(gè)活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)盒揉，用這種方式遞歸地在解空間中搜索晋被，直至找到所要求的解或解空間中已無活結(jié)點(diǎn)為止
典型問題
貨擔(dān)郎問題（TSP問題）
設(shè)某售貨員要到若干城市去推銷商品，已知各城市之間的路程（或路費(fèi)）刚盈。他要選定一條從駐地出發(fā)羡洛，經(jīng)過每個(gè)城市一遍，最后回到駐地的路線藕漱，使總的路程最小欲侮。
這是解集合樹（具體怎么解決這個(gè)問題，再分子界限算法中解決肋联，這里只是介紹回溯法本身）
利用回溯法解決該類問題步驟
1锈麸、針對(duì)所給問題，定義問題的解空間牺蹄；
2忘伞、確定易于搜索的解空間結(jié)構(gòu)；
3沙兰、以深度優(yōu)先方式搜索解空間氓奈，并在搜索過程中用剪枝函數(shù)避免無效搜索。
常用剪枝函數(shù)（這里明白概念就行鼎天，具體在分支界限算法講）
用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿足約束的子樹舀奶；
用限界函數(shù)剪去得不到最優(yōu)解的子樹。
具體例子斋射，0-1背包問題和TSP問題育勺，將在下一章結(jié)合分支界限介紹，這章只介紹概念
