毕业设计（论文）-贪婪算法系统设计.docx

贪婪算法
摘要
在求最优解问题的过程中，依据某种贪婪标准，从问题的初始状态出发，直接去 求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解 方法就是贪婪算法。
从贪婪算法的定义可以看出，贪婪法并不是从整体上考虑mization problems; greedy algorithm;greedy select;optimal solution
1 1
1
1
1
2
2
3
2贪婪算法的知识概述 4
2. 1贪婪算法的柢念 4
2. 2贪婪算法的思路及实现过程 4
2. 4
2. 2. 2实现过程 4
2. 3贪婪算法的核心 5
5
2. 5
2. 4. 2 就子结构性质 5
5
5
2. 5. 2贪婪算法解向量 6
2. 5. 3贪婪算法框架描述 6
6
6
2. 6. 2最小生成树问题（Prim算法、Kruskal算法） 8
7 Java语言的概述 9
. 1 Java语言基本概念 9
2. 7. 2历史起源 9
2. 7. 3基本组成 10
2. 10
7. 5 与 C/C++的差异 11
3会场活动安排的问题 13
问题的提出 13
2编码原理 13
3. 3贪婪算法 13
13
3. 2贪婪策略 13
3. 3. 3贪婪算法核心部分 13
3. 3. 4算法流程图 15
15
3. 15
3. 4. 2无序的结束时间 16
4. 3算法分析 16
4找零钱间题 17
1问题的提出 17
17
17
17
4. 3. 2贪婪策略 17
17
4. 4. 1最优解的说明 17
4. 4. 2最优解的证明 18
4. 4. 3我零问题的核心代码 18
18
5 —般背包问题 19
1问题的提出 19
19
19
3. 1贪婪策略 19
5. 3. 2贪婪策略实现思想 19
5. 3. 3算法流程图 20
3. 4背包问题的核心算法 20
21
6五子棋游戏 23
1可行性研究 23
23
23
23
6. 2. 1概要设计 23
6. 2. 2详细设计 24
26
6. 26
6. 3. 2贪婪算法的体现 26
6. 26
7贪婪算法实现语言及结果 27
6S 番 E SS 蕾罢 奇 i..... ss 径权神a 斜 恕崩 IS IS 费噩coCSIL OS WL OS 善集- z .z OS 馅哽唾星景z L 6E sss^ g・ 6Z 虞Is肇邸卷姐寸」l< 8E 8®n« 8Z 菁监CN• K 瞟蛰懿姒-•-(< R 耄寮岳囊噩L .z
蜻K(«3e44SHFfif鞘-KHI!幽-K
1绪论

为了满足人们对大数据量信息处理的渴望，为解决各种实际问题，计算机算法学得 到了飞速的发展，线性规划、动态规划、贪心策略等一系列运筹学模型纷纷运用到计 算机算法学中，产生了解决各种现实问题的有效算法。虽然设计一个好的求解算法更 像是一门艺术而不像是技术，但仍然存在一些行之有效的、能够用于解决许多问题的 算法设计方法，你可以使用这些方法来设计算法，并观察这些算法是如何工作的。一 般情况下，为了获得较好的性能，必须对算法进行细致的调整。但是在某些情况下， 算法经过调整之后性能仍无法达到要求，这时就必须寻求另外的方法来求解该问题。
当一个问题具有最优子结构性质和贪心选择性质时，贪婪算法通常会给出一个简 单、直观和高效的解法。贪婪算法通过一系列的选择来得到一个问