貪婪式演算法 (Greedy Algorithm) 的簡介與實作

最佳化方法 簡介 歷史 確定性搜尋 基本搜尋法 逐漸深入法 α-β 修剪 A* 搜尋法 隨機搜尋 單粒子隨機搜尋 貪婪演算法 爬山演算法 模擬退火法 禁忌搜尋法 多粒子隨機搜尋 演化策略 鳥群演算法 蟻群演算法 蜂群演算法 程式實作 基本搜尋法 爬山演算法 基因演算法 鳥群演算法 訊息 相關網站 參考文獻 最新修改 簡體版 English

文章 貪婪式演算法的原理 Greedy Algorithm 是一種尋找最佳解的方法，其尋找方法為從某一起點開始，不斷的改進該解答，（尋找周圍的更佳解，然後移到該更佳解上），直到無法改進為止，以下是一個抽象的貪婪演算法。 Algorithm GreedyAlgorithm solution.initialize while not isGoodEnough solution.improve() end End of Algorithm 貪婪式演算法的範例 範例一 : 如何找出二次曲線 y=f(x) 的最低點 演算法 Algorithm GreedyMinimizer(f, x, y) x = 0 y = f(x) while not isGoodEnough improve(f, x, y) End of Algorithm Function improve(f, x, y) if (random(2) = 0) then xNew = x-0.1 else xNew = x+0.1 endif yNew = f(xNew) if (yNew < y) then x = xNew; y = yNew; endif End of Algorithm Java 版程式 — GreedyAlgorithm.java 範例二 : 如何利用 Greedy Algorithm 做排序. Algorithm GreedySorter(a[]:array) while not isGoodEnough improve(a) End of Algorithm Function improve(a[]:array) for i=1 to a.size if a[i] < a[i+1] swap(a[i], a[i+1]) End of Algorithm 結語 以上所舉的僅僅是貪婪演算法的一些範例而已，貪婪演算法機乎可以解決大部份的最佳化問題，包含最小擴展樹 (Minimal Spanning Tree)、最大網路流、解平方根、解聯立方程式、解決機器學習問題，類神經網路的改良等等，都是其應用範圍。 Facebook 留言 Facebook Wikidot Post preview: Close preview or Sign in as Wikidot user (will not be published) - + Help: wiki text quick reference 授權 本網頁的作者、授權與引用方式 作者 陳鍾誠，於金門大學資訊工程系，電子郵件：wt.ude.uqn|ccc#wt.ude.uqn|ccc，網站：http://ccckmit.wikidot.com。 授權 本文採用創作共用 (Creative Common) 3.0 版的 姓名標示─非商業性─相同方式分享 授權條款，歡迎轉載或修改使用，但若做為商業使用時必須取得授權，引用本文時請參考下列格式。 中文版 (APA格式) 陳鍾誠 (13 Oct 2009 00:42)，(網頁標題) 貪婪式演算法 (Greedy Algorithm) 的簡介與實作，(網站標題) 陳鍾誠的網站，取自 http://ccckmit.wikidot.com/so:greedyalgorithm ，網頁修改第 7 版。 英文版 (APA格式) Chung-Chen Chen (13 Oct 2009 00:42), Retrieved from http://ccckmit.wikidot.com/so:greedyalgorithm , Page Revision 7.