資源簡介

(共19張PPT)
第13課
算法的設計
01
02
03
04
貪心算法概念
貪心算法的基本思路
貪心算法的過程
貪心算法應用
CONTENTS
目錄
貪心算法概念
01
Part One
【貪心算法概念】
所謂貪心算法是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的局部最優解。心算法不是對所有問題都能得到整體最優解，但對范圍相當廣泛的許多問題他能產生整體最優解或者是整體最優解的近似解。
貪心算法的基本思路
02
貪心算法的基本思路如下：
建立數學模型來描述問題。
01
把求解的問題分成若干個子問題。
02
對每一子問題求解，得到子問題的局部最優解。
03
把子問題的解局部最優解合成原來解問題的一個解。
04
貪心算法的過程
03
貪心算法的過程
從問題的某一初始解出發；
while 能朝給定總目標前進一步 do
由所有解元素組合成問題的一個可行解
求出可行解的一個解元素；
下面是一個可以使用貪心算法解的題目，貪心解的確不錯，可惜不是最優解：
例題分析：
[背包問題]有一個背包，背包容量是M=150。有7個物品，物品可以分割成任意大小。
要求盡可能讓裝入背包中的物品總價值最大，但不能超過總容量。
物品： A B C D E F G
重量： 35 30 60 50 40 10 25
價值： 10 40 30 50 35 40 30
分析：
目標函數： ∑pi最大
約束條件是裝入的物品總重量不超過背包容量：∑wi\u003C=M( M=150)
（1）根據貪心的策略，每次挑選價值最大的物品裝入背包，得到的結果是否最優？
（2）每次挑選所占重量最小的物品裝入是否能得到最優解？
（3）每次選取單位重量價值最大的物品，成為解本題的策略。
值得注意的是，貪心算法并不是完全不可以使用，貪心策略一旦經過證明成立后，它就是一種高效的算法。貪心算法還是很常見的算法之一，這是由于它簡單易行，構造貪心策略不是很困難。可惜的是，它需要證明后才能真正運用到題目的算法中。
一般來說，貪心算法的證明圍繞著：整個問題的最優解一定由在貪心策略中存在的子問題的最優解得來的。
對于例題中的3種貪心策略，都是無法成立（無法被證明）的，解釋如下：
（1）貪心策略：選取價值最大者。反例：
W=30
物品：A B C
重量：28 12 12
價值：30 20 20
根據策略，首先選取物品A，接下來就無法再選取了，可是，選取B、C則更好。
（2）貪心策略：選取重量最小。它的反例與第一種策略的反例差不多。
（3）貪心策略：
選取單位重量價值最大的物品。反例：
W=30
物品：A B C
重量：28 20 10
價值：28 20 10
根據策略，三種物品單位重量價值一樣，程序無法依據現有策略作出判斷，如果選擇A，則答案錯誤。
貪心算法應用
04
貪心算法應用：
最小生成樹之Prim算法
最小生成樹之kruskal算法
Dijkstra算法（求解最短路徑)
Huffman編碼
再論背包問題
錢幣找零問題
活動選擇問題
小船過河問題
區間覆蓋問題
銷售比賽
練習1
針對機器人畫正六邊形的問題,設計一個算法。
練習2
練習3
感謝聆聽

展開更多......

收起↑