演講人：日期:算法設計與分析貪心算法目錄CATALOGUE01算法概述02核心要素03典型應用實例04正確性驗證方法05算法對比分析06實戰訓練PART01算法概述基本定義與特性01基本定義貪心算法是一種在每一步選擇中都采取在當前狀態下最好或最優（即最有利）的選擇，從而希望導致結果是全局最好或最優的算法。02特性貪心算法具有無后效性，即某個狀態以前的過程不會影響以后的狀態；同時，貪心算法也具有最優子結構性質，即問題的最優解包含其子問題的最優解。貪心策略核心思想貪心算法通過一系列局部最優選擇達到全局最優，每一步選擇都是當前狀態下的最優解。局部最優逐步構造結果不一定最優從問題的某個初始解開始，根據貪心策略逐步構造最優解，每一步只考慮當前狀態，不考慮之前的狀態。由于貪心算法只關注當前狀態下的最優解，因此得到的結果不一定是全局最優解，而可能是次優解或近似最優解。適用場景與局限性貪心算法適用于那些具有最優子結構性質和貪心選擇性質的問題，如哈夫曼編碼、最小生成樹（如Prim算法和Kruskal算法）、最短路徑（如Dijkstra算法）等。適用場景貪心算法不能解決所有問題，特別是那些不具備最優子結構性質或貪心選擇性質的問題；同時，對于某些問題，貪心算法得到的解與最優解相差較大，因此需要使用其他算法進行修正或優化。局限性0102PART02核心要素最優子結構性質局部最優解在貪心算法中，局部最優解即全局最優解，通過逐步構建局部最優解來達到全局最優解。子問題最優性最優子結構性質證明在求解過程中，算法每一步都選擇當前狀態下的最優解，從而保證最終構建的解是全局最優的。證明問題的最優解包含子問題的最優解，從而確保貪心算法的正確性。123貪心選擇性質貪心算法在每一步都做出在當前看來最好的選擇，從而逐步構建全局最優解。貪心選擇策略貪心選擇性質保證了每一步的局部最優解能夠導向全局最優解。局部最優到全局最優證明貪心選擇策略的正確性，即證明每一步的貪心選擇都能得到全局最優解的一部分。貪心選擇策略的證明算法步驟設計原則明確問題目標設計貪心策略逐步構建解驗證解的正確性深入理解問題的本質和求解目標，確保每一步都朝著目標前進。根據問題的特性，設計有效的貪心選擇策略，確保每一步都能獲得當前最優解。通過逐步應用貪心策略，將問題分解為更小的子問題，逐步構建全局最優解。在構建解的過程中，及時驗證解的正確性和可行性，確保最終得到的解是問題的有效解。PART03典型應用實例活動選擇問題問題描述在給定的一組活動中選擇最大數量的相互不重疊的活動。貪心策略每次選擇結束時間最早的活動，以便為后面的活動留下更多的時間。復雜度分析時間復雜度為O(nlogn)，其中n為活動數量，主要由排序步驟決定。示例假設有一組活動{A,B,C,D,E}，開始時間和結束時間分別為{1,3},{2,4},{0,6},{5,7},{3,8}，則選擇的活動為A,B,D。霍夫曼編碼問題描述構造一種可變長度字符編碼，使得文本的總編碼長度最小。貪心策略頻率低的字符用較長的編碼，頻率高的字符用較短的編碼，且編碼為二進制前綴碼。復雜度分析構造霍夫曼樹的時間復雜度為O(nlogn)，其中n為字符種類數。示例給定字符及其頻率{A:5,B:9,C:12,D:13,E:16,F:45}，構造的霍夫曼編碼為{A:1100,B:111,C:010,D:011,E:00,F:10}。最小生成樹算法在一個加權無向圖中，找到一棵包含所有頂點的樹，使得樹中所有邊的權值之和最小。問題描述每次選擇連接兩個不同頂點且權值最小的邊，加入到生成樹中，直到生成樹包含所有頂點。貪心策略Prim算法和Kruskal算法的時間復雜度分別為O(n^2)和O(eloge)，其中n為頂點數，e為邊數。復雜度分析給定一個包含5個頂點的加權無向圖，邊的權值分別為{(A,B):1,(A,C):3,(B,C):1,(B,D):6,(C,D):5,(C,E):4,(D,E):2}，則最小生成樹包含的邊為{(A,B),(B,C),(C,E),(D,E)}。示例PART04正確性驗證方法貪心選擇證明策略01最優子結構證明問題具有貪心選擇性質，即全局最優解可以通過一系列局部最優選擇得到。02貪心選擇性質證明在每一步做出的貪心選擇都是當前狀態下的最優選擇，從而保證最終解的最優性。數學歸納法應用證明貪心算法在初始情況下或最簡單情況下是正確的。歸納基礎歸納假設歸納步驟假設貪心算法在某一情況下是正確的，并基于此假設進行下一步推導。證明在歸納假設成立的情況下，貪心算法在下一步仍然保持正確性，從而推導出算法在一般情況下都是正確的。反例分析法構造反例修正算法反例分析嘗試構造一個不滿足貪心選擇性質的問題實例，或者貪心算法在該實例上無法得到正確解的情況。分析反例的特點，找出貪心算法在該反例上失敗的原因，從而進一步理解貪心算法的適用范圍和限制。根據反例分析的結果，對貪心算法進行修正或改進，以提高其正確性和適用范圍。PART05算法對比分析與動態規劃的區別貪心算法每一步選擇都采取當前狀態下最好或最優（即最有利）的選擇，從而希望導致結果是全局最好或最優的算法。動態規劃狀態轉移方程與最優子結構將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解中得到原問題的解；利用子問題的重疊性，通過記錄已解決的子問題的答案來避免重復計算。動態規劃通過狀態轉移方程來逐步求解問題，貪心算法則不一定依賴于狀態轉移方程；動態規劃要求問題具有最優子結構性質，貪心算法則不需要。123與分治算法的優劣貪心算法每一步選擇當前最優解，不考慮全局；分治算法將問題分解為更小的相似子問題，遞歸求解。貪心算法與分治算法貪心算法通常具有更高的時間效率，因為它不需要遞歸和回溯；但貪心算法可能無法得到全局最優解。求解效率貪心算法適用于具有貪心選擇性質的問題，即局部最優解能導致全局最優解；分治算法則適用于可以被分解為更小相似子問題的問題。問題適用性實際場景選擇依據對于具有貪心選擇性質的問題，貪心算法是更好的選擇；對于需要求解最優解的問題，可能需要考慮動態規劃或分治算法。問題類型當問題規模較大時，貪心算法由于其高效性可能更具優勢；但對于一些規模較小的問題，其他算法可能同樣有效甚至更優。貪心算法通常實現較為簡單，代碼可讀性較好；而其他算法如動態規劃可能實現較為復雜，但更能保證解的準確性。問題規模貪心算法通常無法保證得到全局最優解，但可以得到近似最優的解；若需要精確求解，則需考慮其他算法。求解精度01020403實現難度與代碼可讀性PART06實戰訓練經典題目解析哈夫曼編碼構建字符出現頻率的哈夫曼樹，頻率高的字符路徑短，頻率低的字符路徑長，實現壓縮編碼。03將物品按單位重量的價值排序，依次選擇價值最高的物品放入背包，直到背包無法容納更多物品。02背包問題最小生成樹問題通過貪心策略選擇最小權重的邊，保證生成樹的總權重最小。01時間復雜度優化技巧優先隊列使用優先隊列維護貪心策略中的候選元素，以減少每次選擇的時間開銷。01局部貪心將大問題分解為多個小問題，分別應用貪心策略求解，從而降低整體時間復雜度。02剪枝策略在貪心策略中，提前排除不可能得到最優解的情況，以減少不必要的計算。03代碼實現要點邊界條件處理數據結構