【算法資源】貪婪算法

2021-03-02 數學中國

貪婪算法(Greedy algorithm)是一種對某些求最優解問題的更簡單、更迅速的設計技術。用貪婪法設計算法的特點是一步一步地進行，常以當前情況為基礎根據某個優化測度作最優選擇，而不考慮各種可能的整體情況，它省去了為找最優解要窮盡所有可能而必須耗費的大量時間，它採用自頂向下，以迭代的方法做出相繼的貪心選擇，每做一次貪心選擇就將所求問題簡化為一個規模更小的子問題，通過每一步貪心選擇，可得到問題的一個最優解，雖然每一步上都要保證能獲得局部最優解，但由此產生的全局解有時不一定是最優的，所以貪婪法不要回溯。

貪婪算法是一種改進了的分級處理方法。其核心是根據題意選取一種量度標準。然後將這多個輸入排成這種量度標準所要求的順序，按這種順序一次輸入一個量。如果這個輸入和當前已構成在這種量度意義下的部分最佳解加在一起不能產生一個可行解，則不把此輸入加到這部分解中。這種能夠得到某種量度意義下最優解的分級處理方法稱為貪婪算法。

對於一個給定的問題，往往可能有好幾種量度標準。初看起來，這些量度標準似乎都是可取的，但實際上，用其中的大多數量度標準作貪婪處理所得到該量度意義下的最優解並不是問題的最優解，而是次優解。因此，選擇能產生問題最優解的最優量度標準是使用貪婪算法的核心。

一般情況下，要選出最優量度標準並不是一件容易的事，但對某問題能選擇出最優量度標準後，用貪婪算法求解則特別有效。最優解可以通過一系列局部最優的選擇即貪婪選擇來達到，根據當前狀態做出在當前看來是最好的選擇，即局部最優解選擇，然後再去解做出這個選擇後產生的相應的子問題。每做一次貪婪選擇就將所求問題簡化為一個規模更小的子問題，最終可得到問題的一個整體最優解。

資源分享網址

http://www.madio.net/thread-92698-1-1.html

相關焦點

  • 玩轉算法「基礎篇」| 貪婪算法
    2.1  適用場景貪婪算法常用於尋求最優解問題。將問題分成若干個求解步驟，在每個步驟中都依據某個最優原則選擇當前狀態的最優解，以此希望最後得到的結果也是最優的。貪婪算法在迭代完一輪之後就不再進行回溯，簡單高效，這種只關注當前狀態最優解的方法，通常可能會錯過全局最優解。
  • 貪心算法與近似算法
    貪婪算法很簡單：每步都採取最優的做法。在這個示例中，你每次都選擇結束最早的課。用專業術語說，就是你每步都選擇局部最優解，最終得到的就是全局最優解。信不信由你，對於這個調度問題，上述簡單算法找到的就是最優解！顯然，貪婪算法並非在任何情況下都行之有效，但它易於實現！下面再來看一個例子。
  • 貪婪算法
    令人驚嘆，它完美地詮釋了貪婪算法的內涵，局部最優，最終未必最優，或者有時候可以不負責任而武斷地說，最終必定不最優。這個算法是有哲學意味在裡面的，映射了我們的人生，也許也是這樣，總在局部與全局中選錯了那個最優。
  • (十八) -- 從貪婪算法和動態規劃說起
    增強學習的最終目的,就是在和外界環境的接觸/探索/觀察的過程中,不斷改進策略,把長期的回報/利益最大化而已.        (2)增強學習的理論基礎, 要從運籌學裡的"貪婪算法" (Greedy Algorithm) 說起.
  • 程序算法與人生選擇
    比如，你的標準是：工資大於5000元&&業務前景長於3年的公司，你可以用這個標準來過濾你的選項。然後，你可以再調整這個標準再繼續遞歸下去。這個算法告訴我們，我們的選擇標準越清晰，我們就越容易做出選擇。這是排序算法中最經典的兩個算法了，面試必考。相信你已爛熟於心中了。所以，我覺得你把這個算法應用於你的人生選擇也應該不是什麼問題。關
  • 決策樹分類算法之ID3算法與C4.5算法
    分類作為一種監督學習方法，要求必須事先明確知道各個類別的信息，並且斷言所有待分類項都有一個類別與之對應。但是很多時候上述條件得不到滿足，尤其是在處理海量數據的時候，如果通過預處理使得數據滿足分類算法的要求，則代價非常大，這時候可以考慮使用聚類算法。
  • 算法是什麼:計算機領域中算法的科普
    所有這些都要感謝算法。每當你使用手機、計算機、筆記本電腦或計算器時，其實都在使用算法。那麼，什麼是算法？如果你想做數學運算，比如說兩個數字相乘（不使用任何電子設備），那麼你需要在紙上做乘法。你按照一定的規則獲得正確的答案。你也可以使用耗時更少的方法來做計算。這就是算法。算法是為執行特定的任務而設計的一組指令。
  • XGBoost之切分點算法
    前言上文介紹了XGBoost的算法原理並引出了衡量樹結構好壞的打分函數（目標函數），根據特徵切分點前後的打分函數選擇最佳切分點，但並未對節點的切分算法作詳細的介紹。本文詳細的介紹了XGBoost的切分點算法，內容參考陳天奇博士《XGBoost ：A scalable Tree Boosting System》。
  • 最全 Python 算法實現資源匯總!
    ，自己寫算法的過程可以幫助我們更好地理解算法思路，不要輕視每一個算法，一些雖然看似容易，但可能有很多坑。為了幫助大家在這個假期能提高學習效率，進階 Python 技能，筆者為大家推薦了一份用 Python代碼實現算法的資源帖，涵蓋從入門到高級的各類算法。下文中，筆者首先對項目的整體內容進行了一個歸納，之後為大家選取了幾個內容比較豐富的部分，供大家更高效地使用這一資源。
  • 示例說明算法和流程圖
    在此頁面中，我們將討論算法和流程圖之間的差異，以及如何創建流程圖以直觀地說明算法。       算法和流程圖是用於創建新程序（尤其是在計算機編程中）的兩種不同工具。算法是對過程的逐步分析，而流程圖以圖形方式解釋了程序的步驟。
  • 你不得不看的最重要的算法類型
    算法： 算法是解決問題的分步過程。一個好的算法應該在時間和空間上進行優化。不同類型的問題需要以最優化的方式解決不同類型的算法技術。世界上有很多類型的算法，但是本文將討論您必須知道的最重要和最基本的算法。
  • 評估算法及算法的時間複雜度
    文章導讀【對於一個給定的算法，通常要評估其正確性和運行效率的高低。算法的正確性評估不在本文範圍之內，本文主要討論從算法的時間複雜度特性去評估算法的優劣。】程序是用來解決問題的，是由多個步驟或過程組成的，這些步驟和過程就是解決問題的算法。
  • 10種算法一文打盡！基本圖表算法的視覺化闡釋
    算法：· 弗洛伊德循環檢測算法· 布倫特算法應用：· 用於基於消息的分布式算法· 用於使用集群上的分布式處理系統處理大規模圖表· 用於檢測並發系統中的僵局· 在加密應用程式中用於確定能夠將消息映射到相同加密值消息的密鑰
  • AI人工智慧的幾種常用算法概念
    PSO 算法屬於進化算法的一種，和遺傳算法相似，它也是從隨機解出發，通過迭代尋找最優解，它也是通過適應度來評價解的品質，但它比遺傳算法規則更為簡單，它沒有遺傳算法的交叉（Crossover） 和變異（Mutation） 操作，它通過追隨當前搜索到的最優值來尋找全局最優。這種算法以其實現容易、精度高、收斂快等優點引起了學術界的重視，並且在解決實際問題中展示了其優越性。
  • 資源分享:一本算法書下載和幾本算法書推薦
    仔細體味一下，在工作時、在生活中，先做什麼、後做什麼、怎麼做，我們是不是有意無意在使用算法。更不用說，作為程序靈魂的算法了。在這個正飛速智能化的時代裡，算法的重要性不言而喻。 今天給大家分享的是一本訓練算法思維的書——《算法之道》，講解了許多能夠展現算法思想的算法，算法分析及其背後的邏輯，給讀者以啟示。
  • 一個數據挖掘大牛,用程序算法做人生選擇
    貪婪算法所謂貪婪算法，是一種在每一步選擇中都採取在當前狀態下最好或最優（即最有利）的選擇（注意：是當前狀態下），從而希望導致結果是最好或最優的算法。貪婪算法最經典的一個例子就是哈夫曼編碼。對於人類來說，一般人在行為處事的時候都會使用到貪婪算法，比如在找零錢的時候，如果要找補36元，我們一般會按這樣的順序找錢：20元，10元，5元，1元。或者我們在過十字路口的時候，要從到對角線的那個街區時，我們也會使用貪婪算法——哪邊的綠燈先亮了我們就先過到那邊去，然後再轉身90度等紅燈再過街。這樣的例子有很多。
  • 經典算法設計方法
    算法常常含有重複的步驟和一些比較或邏輯判斷。如果一個算法有缺陷，或不適合於某個問題，執行這個算法將不會解決這個問題。不同的算法可能用不同的時間、空間或效率來完成同樣的任務。一個算法的優劣可以用空間複雜度與時間複雜度來衡量。算法的時間複雜度是指算法需要消耗的時間資源。
  • 資源 | 主要推薦系統算法總結及Youtube深度學習推薦算法實例概括
    在海量推薦算法中，數據科學家需要根據商業限制以及需求來選擇最佳算法。為使其簡單化，Statsbot 團隊為現有的主要推薦系統算法準備了一份概述。協同過濾協同過濾（CF）及其變式是最常用的推薦算法之一。即使是數據科學的初學者，也能憑之建立起自己的個性化電影推薦系統，例如，一個簡歷項目。
  • 人工智慧-啟發式算法(Heuristic Algorithm)簡談
    求解要選擇算法，只有我們對各種算法的優缺點都很熟悉後才能根據實際問題選出有效的算法。但是對各種算法都了如指掌是不現實的，但多知道一些，會使你的選擇集更大，找出最好算法的概率越大。大自然是神奇的，它造就了很多巧妙的手段和運行機制。受大自然的啟發，人們從大自然的運行規律中找到了許多解決實際問題的方法。
  • Machine Learning -- ID3算法
    對於決策樹來說，主要有兩種算法：ID3算法和C4.5算法。C4.5算法是對ID3算法的改進。今天主要先講ID3算法，之後會講C4.5算法和隨機森林等。 Contents     1.ID3算法介紹     3. 信息熵與信息增益     4. ID3算法的C++實現  1.