資源描述：
《貪心算法論文終稿》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。
1、本科畢業(yè)論文（設計）題目貪心算法設計及其實際應用研究系別信息管理系專業(yè)計算機科學與技術年級2006級學號222006602054062姓名蔣遠麗指導教師汪維清成績_______________________二〇一〇年五月十五日nn目錄西南大學本科畢業(yè)論文（設計）任務書I文獻綜述i西南大學本科畢業(yè)論文（設計）開題報告-1-正文1摘要1第1章引言21.1研究背景21.2研究內(nèi)容21.3研究目標21.4研究意義21.5本文組織3第2章貪心算法的基本知識概述42.1貪心算法定義42.2貪心算法的基本思路及實現(xiàn)過程42.3貪心算法的核心42.4貪心算法的基本要素52.
2、5貪心算法的理論基礎62.6貪心算法存在的問題7第3章經(jīng)典問題解決及其優(yōu)缺點83.1哈夫曼編碼83.2單源最短路徑問題(Dijkstra算法)103.3最小生成樹問題(Prim算法、Kruskal算法)12第4章多處最優(yōu)服務次序問題154.1問題的提出154.2貪心選擇策略154.3問題的貪心選擇性質154.4問題的最優(yōu)子結構性質154.5算法結果分析16nn第5章刪數(shù)問題175.1問題的提出175.2貪心算法策略175.3問題的貪心選擇性質175.4問題的最優(yōu)子結構性質175.5編碼18第6章汽車加油問題196.1問題的提出196.2編碼分析196.3貪心算
3、法策略196.4貪心算法正確性證明206.5貪心算法時間復雜度分析20第7章最優(yōu)合并問題217.1問題的提出217.2原理分析217.3算法時間復雜度分析21第8章會場安排問題228.1問題的提出228.2編碼分析228.3貪心算法228.4最優(yōu)解證明238.5算法時間復雜度分析23第9章貪心算法的C++實現(xiàn)249.1C++語言概述249.2具體實現(xiàn)步驟259.3程序編碼與程序調(diào)試29第10章總結與展望3110.1總結3110.2展望31參考文獻32nn附錄33致謝41本科畢業(yè)論文（設計）指導教師評閱表a本科畢業(yè)論文（設計）交叉評閱表b本科畢業(yè)論文（設計）答辯
4、記錄cnnnn西南大學本科畢業(yè)論文（設計）任務書論文（設計）題目貪心算法設計及其實際應用研究系別、專業(yè)信息管理系計算機科學與技術學生姓名蔣遠麗學號222006602054062指導教師姓名汪維清開題日期2009年11月28日論文（設計）的主要內(nèi)容（技術指標）與要求：本文講述了貪心算法的含義、基本思路及實現(xiàn)過程，貪心算法的核心、基本性質、特點及其存在的問題。并通過貪心算法的性質，通過研究幾個經(jīng)典問題，將貪心算法應用到實際中。進度安排研究進度安排：2009年10月-2009年11月，根據(jù)課題研究的內(nèi)容，收集資料2009年11月-2009年12月，深入探討該算法中的
5、幾個經(jīng)典問題2009年12月-2010年1月，整理研究內(nèi)容，并作進一步的修改2010年1月-2010年2月，歸納總結，形成一份完整的課題論文系意見：注：1、任務書由指導老師填寫。2、任務書必須在第七學期13周前下達給學生。nnnnnn文獻綜述貪心算法設計及其實際應用研究蔣遠麗西南大學榮昌校區(qū)信息管理系，重慶榮昌402460摘要：在求最優(yōu)解問題的過程中，依據(jù)某種貪心標準，從問題的初始狀態(tài)出發(fā)，直接去求每一步的最優(yōu)解，通過若干次的貪心選擇，最終得出整個問題的最優(yōu)解，這種求解方法就是貪心算法。從貪心算法的定義可以看出，貪心法并不是從整體上考慮問題，它所做出的選擇只是
6、在某種意義上的局部最優(yōu)解，而由問題自身的特性決定了該題運用貪心算法可以得到最優(yōu)解。貪心算法所作的選擇可以依賴于以往所作過的選擇，但決不依賴于將來的選擇，也不依賴于子問題的解，因此貪心算法與其它算法相比具有一定的速度優(yōu)勢。如果一個問題可以同時用幾種方法解決，貪心算法應該是最好的選擇之一。本文講述了貪心算法的含義、基本思路及實現(xiàn)過程，貪心算法的核心、基本性質、特點及其存在的問題。并通過貪心算法的特點舉例列出了以往研究過的幾個經(jīng)典問題，對于實際應用中的問題，也希望通過貪心算法的特點來解決。關鍵詞：貪心算法；哈夫曼編碼；最小生成樹；多處最優(yōu)服務次序問題；刪數(shù)問題0引言
7、為了滿足人們對大數(shù)據(jù)量信息處理的渴望，為解決各種實際問題，計算機算法學得到了飛速的發(fā)展，線性規(guī)劃、動態(tài)規(guī)劃、貪心策略等一系列運籌學模型紛紛運用到計算機算法學中，產(chǎn)生了解決各種現(xiàn)實問題的有效算法。雖然設計一個好的求解算法更像是一門藝術而不像是技術,但仍然存在一些行之有效的、能夠用于解決許多問題的算法設計方法,你可以使用這些方法來設計算法,并觀察這些算法是如何工作的。一般情況下,為了獲得較好的性能,必須對算法進行細致的調(diào)整。但是在某些情況下,算法經(jīng)過調(diào)整之后性能仍無法達到要求,這時就必須尋求另外的方法來求解該問題。nn當一個問題具有最優(yōu)子結構性質和貪心選擇性質時，
8、貪心算法通常會給出一個簡單、直觀和高效
