下载文档原格式
湖南理工学院课程论文论文题目贪心法的应用课程名称算法设计与分析姓名学号专业计算机科学与技术年级学院计算机日期（2014年4月10日）课程论文评价标准贪心法的应用摘要：在解决问题的过程中，通过逐步获得最优解从而获得整体最优解的策略就是贪心策略，在已经学会在解的范围可以确定的情况下，可以采用枚举或递归策略，一一比较它们最后找到最优解；但当解的范围非常大时，枚举和递归的效率会非常低。
这时就可以考虑用贪心策略。
贪心算法没有固定的框架，算法设计的关键是贪心策略的选择，贪心策略要具有无后向性，即某阶段状态一旦确定以后，不受这个状态以后的策略的影响。
当一个问题有好几种解决方法时，贪心法应该是最好的选择之一。
本文讲述了贪心算法的含义、基本思路以及贪心算法在实例中的应用。
关键词：贪心算法；删数问题；最小生成树一、引言在平时解决问题的过程中，当一个问题就有无后向性和贪心选择性质时，贪心算法通常会给出一个简单、直观和高效的解法。
贪心算法通过一系列的选择来得到一个问题的解。
它所做的每一个选择都是当前状态下就有某种意义的最好选择，即贪心选择；并且每次贪心选择都能将问题化解为一个更小的与原问题具有相同形式的子问题。
尽管贪心算法对于很多问题不能总是产生整体最优解，但对于最短路径、最小生成树问题，以及删数问题等却可以获得整体最优解，而且所给出的算法一般比动态规划算法更为简单、直观和高效。
二、贪心算法的含义和特点（一）贪心算法的含义贪心算法是通过一系列的选择来得到问题解的过程。
贪心算法是一种能够得到某种度量意义下的最优解的分级处理方法，它总是做出在当前看来是最有的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解算法。
（二）贪心算法的特点1、从全局来看，运用贪心策略解决的问题在程序运行过程中无回溯过程，后面的每一步都是当前看似最佳的选择，这种选择依赖已作出的选择，但并不依赖未作出的选择。
2、不能保证最后求出的解是最佳的。
“算法分析与设计”教学模式探索摘要：分析了“算法分析与设计”教学中存在的问题。
结合多年来从事“算法分析与设计”课程教学的经验，从构建主义学习理论的角度，以增加学生主观能动性为出发点，提出了一种综合性互动教学模式，并给出了该模式下的实践措施。
教学实践表明，该模式有利于培养学生的互动能力、逻辑思维能力和实践动手能力，在实际教学过程中取得了较好的效果。
关键词：算法分析与设计；教学模式；互动计算机算法是计算机科学和计算机应用的核心，无论是计算机系统、系统软件的设计，还是为解决计算机的各种应用课题p算法分析与设计课程需要较强的逻辑性、抽象性和较好的数学基础，很多学生在学习过程中，感觉算法内容理解难度较大，部分学生虽然清楚了整个算法思想，却无法读懂程序伪代码和源代码。
此外，不少学生对该门课程不够重视，存在着混学分的思想，导致了学习积极性不高。
造成以上现象的原因可以总结为以下几点：(1)学生对该课程的基础课程学习不扎实。
算法分析与设计的基础课程包括C语言(或VC++)、数据结构和离散数学等，而C语言和数据结构一直都是很多学生学习的一个软肋。
此外，对于一些非计算机专业的学生，他们在学习算法分析与设计课程之前，甚至没有学习过离散数学课程，这更加增加了他们学习的难度。
(2)学生对该课程重视程度不够。
一些学生思想上带有功利的成分，对所学内容在实际中的应用特别关注。
例如，设计了一个网站、一个管理系统或者一个嵌入式程序，学生可能觉得将来可以用于找工作，而算法分析与设计课程的内容显得与实际工作关系不大，因此，只抱着混学分的态度，及格就行。
(3)教师与学生的互动性不强。
在算法分析与设计的课程教学中，容易形成从教师至学生的单向灌输的局面，学生只是应付，没有兴趣去主动思考，以至形成“课堂纪律非常好，但是教师提问无人回答”的情形。
此外，很多教师使用了多媒体教学，虽然采用了信息化手段，但是多媒体课件响应速度快，超越了学生思考能力，阻碍了教师与学生之间的互动性。
《算法设计》课程论文题目针对UBQP问题的量子文化基因算法学生姓名学号院系计算机与软件学院专业计算机科学与技术指导教师刘文杰2015年6 月30 日目录1 引言 (2)2 ** 算法简介 (3)3 针对UBQP问题的量子文化基因算法（QEA-TS） (3)3.1算法思想 (3)3.2算法流程 (3)3.3算法过程描述 (5)3.3.1输入权值矩阵 (5)3.3.2 量子染色体初始化 (5)3.3.3 染色体观测 (5)3.3.4禁忌搜索 (6)3.3.5评估适应度值 (7)3.3.6 量子旋转门和更新 (7)3.3.7算法终止条件 (10)3.4本章小结 (11)4代码实现与结果分析 (11)4.1代码实现 (11)4.2运行结果分析与比较 (12)4.2.1参数设置 (12)4.2.2运行结果分析与比较 (12)5 小结 (14)针对UBQP 问题的量子文化基因算法1 引 言无约束0-1二次规划问题（Unconstrained Binary Quadratic Problem ，UBQP ）是一类选取合适的二进制决策变量，使得二次目标函数值极大化的优化问题，该问题用数学表达式可以写成UBQP ：QX X x f T =)(（1）的形式，其中Q 是一个n n ⨯对称矩阵，一般写成上三角的形式，是常量，X 是n 维二进制向量（每个分量都是0或者1），即需要求的解。
这是一个典型的NP （Non-deterministic Polynomial ）难题，它有许多方面的应用，如计算机辅助设计，社会心理学，交通管理，金融分析，机器调度等等。
同时，UBQP 问题是组合优化问题的一种通用模型，大多数组合优化问题都能够转化成该问题后进行求解，如图着色问题，多维背包问题，最大团问题，集合分割问题等等。
同时UBQP 问题是一个多峰值函数问题，在它的函数图像中具有很多山峰一样的极值点。
对这一问题，学者们提出了多种求解的算法，这些算法大致可以归结为两大类：完整算法和启发式算法。
计算机教学论文：聚焦计算思维的算法分析与设计课程教学改革0 引言算法是计算机科学中最具方法论性质的核心概念，被誉为计算机学科的灵魂。
图灵奖获得者Niklaus Wirth提出：算法+数据结构=程序，强调了算法在计算机领域的重要性。
在现实生活中，算法、算据和算力组成了人工智能技术的三要素；算法的新颖性和性能决定了学术论文在高水平期刊或会议上发表的可能性；算法能力测试是研究生复试和求职面试等场合常见的环节。
因此，学习并掌握好算法相关知识，对一名本科生的综合能力培养和职业发展来说非常重要。
国内外各大高校计算机专业在培养方案中，普遍开设了算法分析与设计（以下简称算法）课程，该课程以高级程序设计和数据结构为先导课程，又为人工智能等专业课程提供算法支撑，是培养方案的重要枢纽之一。
算法课程既包含抽象的理论，又强调算法的实践，对学生的逻辑思维和计算建模等能力有较高的要求，因此有必要聚焦计算思维，开展面向能力提升的课程教学改革。
1 课程教学和改革现状1.1 共性问题目前，采取小班化策略开展算法课程教学已比较普遍；多数高校选用MIT经典书籍《Introduction to Algorithms》作为教材；依托在线平台开展编程训练取得了良好的教学效果。
但在教学过程中，还存在一些共性问题。
（1）学生在理论学习时普遍存在畏难心理。
算法要求学生不仅掌握算法的实施，更强调对算法原理的理解；一些关键的算法要进行证明，如主方法、最优前缀码等，这需要大量的理论知识，涉及不少数学符号，学生容易感到枯燥和抽象，降低了学习兴趣。
（2）学生难以灵活运用算法解决实际问题。
学生往往能够较好地掌握教材中的经典问题和相应的算法，并完成课后习题和部分在线训练题，但遇到复杂的现实问题或工程问题时，要么没有思路，要么依赖直觉，无法准确构建输入输出间的解析关系。
（3）学生的基础水平和学习需求差异明显。
修读课程的学生水平参差不齐，学习动力和学习方法也各不相同，因此处在两极的学生的学习需求通常难以得到精细满足；另外，创新实验活动和程序设计竞赛吸引了部分学有余力的学生，但课程教学和第二课堂缺乏深度结合。
算法设计与分析课程论文论文名称 24计算问题学院教育信息技术学院学生姓名莫怡琳、阮淑贞、陈鑫奕学号2014210972、2014210970、2014210946 2017 年 1 月 3日目录一、问题描述 (1)二、前端分析 (1)1、功能需求 (1)2、工具选择 (1)三、详细设计及说明 (1)四、算法设计思想 (4)核心算法 (4)辅助算法 (5)五、问题及解决 (6)六、总结反思 (7)七、小组分工 (7)八、小组互评 (7)九、编程日记 (8)11月29日编程日记 (8)12月6日编程日记 (8)12月7日编程日记 (9)十、源代码 (9)24计算问题一、问题描述24点游戏是指任意输入1-9的四个数，通过加减乘除四则运算连接，使得计算结果为24，而使用计算机模拟该游戏，就是让程序随机产生数字，由用户组合成表达式，交给程序进行结果判断。
二、前端分析1、功能需求（1）模式选择：根据玩家人数选择单人模式或者双人模式（2）用户登录/注册：允许用户登录、注册，确保账号安全（3）随机：自动产生随机数，供用户选择（4）验证：对用户输入的表达式进行判断（5）计算：对随机产生的数字求解，得出符合要求的表达式（6）记录：能够根据玩家的输赢情况，实时更新玩家等级（7）存储：存储并动态更新用户的相关信息，包括用户名、密码、游戏等级2、工具选择工具：DW，语言：php，用本机localhost做服务器和测试端（1）交互性强，用户能够通过鼠标、键盘等输入与网页进行交互（2）界面编写容易，div+css可以实现网页布局（3）数据存储读取方便，能够实时与AppServ自带的数据库链接（4）24点游戏本身适合做成网页版三、详细设计及说明1、模式选择：选择不同的模式将会跳转至不同游戏界面单人模式双人模式帮助：游戏规则：选择单人模式将独自完成任务，每完成一关将会上升一个等级,回答错误将会下降一个等级；选择双人模式胜利者将上升一个等级，失败者将下降一个等级。
本科计算机毕设算法类全文共四篇示例，供读者参考第一篇示例：本科计算机毕业设计（算法类）是计算机科学与技术专业学生进行的一项重要的学术项目。
在这个项目中，学生需要通过研究和实践，运用所学的计算机算法知识，设计和实现一个具有一定规模和挑战性的算法系统。
该项目旨在让学生将所学的理论知识应用到实际项目中，培养学生的分析和解决问题的能力，提高他们的创新意识和实践能力。
在进行本科计算机毕业设计（算法类）时，学生可以选择不同的研究方向和课题内容。
学生可以选择研究排序算法、图算法、字符串匹配算法、动态规划算法等方面的内容。
通过对算法的研究和实践，学生可以更好地理解算法的运行原理和优化方法，提高对算法效率和性能的理解和应用能力。
在进行本科计算机毕业设计（算法类）的过程中，学生需要经历以下几个阶段：1. 选题阶段：学生可以选择自己感兴趣的研究方向和课题内容，并与导师进行深入的讨论和交流，确定最终的毕业设计课题。
在选题阶段，学生可以根据自己的兴趣和能力来选择适合自己的课题。
2. 研究阶段：在选题确定后，学生需要对相关领域的研究现状和发展趋势进行深入的研究和分析，了解该领域的前沿技术和问题，为设计和实现算法系统提供理论基础和参考依据。
3. 设计阶段：在研究阶段完成后，学生需要对算法系统进行详细的设计和规划，包括算法的整体架构、数据结构的选择和算法实现的步骤等内容。
设计阶段是整个毕业设计的核心部分，决定了最终算法系统的实现效果和性能表现。
4. 实现阶段：在设计阶段完成后，学生需要按照设计方案，利用计算机编程工具和技术，对算法系统进行具体的实现和开发。
在实现阶段，学生需要解决实际中遇到的问题和挑战，不断优化和改进算法系统的性能和功能。
5. 测试阶段：在实现阶段完成后，学生需要对算法系统进行全面的测试和评估，包括功能测试、性能测试、可靠性测试等内容。
通过测试阶段，学生可以对算法系统的实际表现和问题进行全面地了解，为最终的论文撰写和答辩做准备。
课程名称：算法分析及设计课程编码：C201课程学分：2适用学科：计算机应用技术算法分析及设计Design and Analysis of advancedAlgorithms教学大纲一、课程性质算法的设计与分析是计算机科学的核心问题之一，是计算机科学与工程各专业学生及研究生的一门重要的专业基础课。
其内容是研究计算机领域及相关领域中的一些常用的算法设计方法及算法的复杂性分析方法。
同时，通过讲授NP 理论的主要概念及一些近似算法，为学生从事计算机算法的研究工作奠定基础。
学习和掌握这些知识不仅对计算机专业的技术人员，而且对使用计算机的其他各专业技术人员都是必不可少的。
二、课程教学目的通过本课程的学习，应使学生掌握算法设计的常用方法，以便能够运用这些方法设计解决计算机应用中的实际问题的有效算法，并能够利用已有算法去解决实际问题。
此外还要使学生学会分析算法，估计算法的时空复杂性，从而对算法做出科学的评价。
三、教学基本内容及基本要求第一章绪论1、算法定义（了解）2、算法特征3、计算机求解问题过程4、算法描述语言5、算法分类第二章算法复杂性分析（要求全部掌握）1、算法复杂性2、算法复杂性计量3、复杂性的渐进形态4、渐进分析5、递归方程解的渐进阶第三章算法设计的基本方法（要求全部掌握）1、贪心法2、分治法3、动态规划4、回溯法5、分支限界法第四章图和网络算法（要求全部掌握）1、基本概念2、树的算法3、路的算法4、流的算法第五章计算几何（要求全部掌握）1、相交问题2、求夹角3、求凸包4、判断一点在几何体内部5、Voronoi图第六章概率算法（要求全部掌握）1、概率算法简介2、随机数3、素数的概率算法4、线性时间选择算法5、平面点集最近点对概率算法第七章 NP完全性理论及近似算法（要求全部掌握）1、确定性图灵机2、非确定性图灵机3、P类与NP类4、Cook定理与NP完全问题5、NP完全问题近似解法第八章新技术综述（一般了解）四、本课程与其他相关课程的联系与分工先修课程：程序设计，数据结构，离散数学等。
本科毕业论文算法算法（Algorithm），通常翻译为“算法”、“演算法”或“算法”等，指的是一种解题方案的规范和步骤，是一种具有一定规律性的操作方法。
算法是计算机科学的重要分支，能够解决许多问题，如排序、查找、最短路径等。
本篇论文将从算法的概念、分类、设计和分析等方面进行探讨，希望读者能对算法有一个全面的认识。
一、算法的概念算法指的是一种用于求解问题的有限步骤。
它是一个自动化过程，任何可以被计算机执行的任务都可以表示为一个算法，而大部分计算机程序都是算法的实现。
通常情况下，算法应具备以下要素：1.输入：算法要求有输入，通常是一个问题或一串数据。
2.输出：算法必须有输出，即针对输入生成相应的结果。
3.明确性：算法需要具有明确的步骤和操作方式。
4.有限性：算法应具备有限步骤，不应出现无限循环或死循环。
5.有效性：算法应能够在合理的时间内完成任务。
二、算法的分类算法可分为以下几种类型：1.穷举算法：这种算法通常应用于搜索问题。
它通过尝试所有可能的搜索路径来找到问题的解决方案，因此也称为暴力搜索。
2.贪心算法：贪心算法的核心思想是选择最优解。
在每个步骤中，该算法都选择自己认为最好的决策，从而最终得到最优解。
3.分治算法：这种算法将问题分为多个子问题，递归地解决每个子问题并将它们合并为最终解决方案。
分治算法通常应用于求解类似于快速排序和归并排序之类的排序算法。
4.动态规划算法：这种算法通常应用于求解具有最优化性质的问题。
它将问题分解为多个子问题并逐步求解各个子问题，然后将子问题的解决方案综合起来得到最终的解决方案。
5.回溯算法：这种算法思想是从一组可能的解决方案中选择一个，然后检查它是否满足要求。
如果没有满足，那么就回溯并选择下一个可行的解决方案，如此重复，直到找到符合要求的解决方案。
三、算法的设计算法设计是指将一个问题转化为可理解的算法步骤，然后将其实现为计算机程序的过程。
算法设计过程中通常需要进行以下几个步骤：1.问题定义：将问题抽象化，定义问题的输入和输出以及问题所需的约束条件。
大学计算机数据结构与算法设计期末结课论文随着信息时代的到来，计算机科学领域的发展日新月异。
计算机数据结构与算法设计作为计算机科学的核心领域之一，扮演着重要的角色。
本文将探讨大学计算机数据结构与算法设计的相关内容，深入研究其重要性以及在计算机科学中的应用。
## 一、引言计算机数据结构与算法设计是计算机科学课程中的基石。
数据结构是一种组织和存储数据的方式，而算法则是解决问题的方法。
这两者共同构成了计算机程序的基础。
在大学计算机科学的课程中，数据结构与算法设计通常是一门重要的必修课程，学生必须深入理解和掌握这些概念。
## 二、数据结构### 2.1 数组数组是一种基本的数据结构，它将数据存储在连续的内存位置中。
数组的访问速度很快，但插入和删除元素的操作可能比较慢。
了解如何正确使用数组是计算机科学学生的必备知识。
### 2.2 链表链表是一种动态数据结构，它由节点组成，每个节点都包含了数据和指向下一个节点的指针。
链表的插入和删除操作非常高效，但访问元素需要遍历链表。
学习链表的设计和操作是数据结构课程的重要一部分。
### 2.3 栈和队列栈和队列是两种常见的数据结构，用于管理数据的存储和访问。
栈采用后进先出（LIFO）的原则，而队列采用先进先出（FIFO）的原则。
它们在许多实际应用中都有广泛的应用，如操作系统的进程管理和图形算法。
## 三、算法设计### 3.1 排序算法排序算法是计算机科学中的经典问题之一。
它们用于按照特定的顺序排列数据。
常见的排序算法包括冒泡排序、快速排序和归并排序。
了解不同排序算法的性能和适用场景对于优化程序至关重要。
### 3.2 查找算法查找算法用于在数据集中查找特定元素。
二分查找、线性查找和哈希查找是常见的查找算法。
这些算法在数据库管理系统和搜索引擎中有广泛的应用。
### 3.3 图算法图算法用于解决与图相关的问题，如最短路径、最小生成树和网络流。
它们在社交网络分析、地理信息系统和交通规划等领域发挥着关键作用。
理工学院课程论文论文题目贪心法的应用课程名称算法设计与分析姓名学号专业计算机科学与技术年级学院计算机日期（2014年4月10日）课程论文评价标准贪心法的应用摘要：在解决问题的过程中，通过逐步获得最优解从而获得整体最优解的策略就是贪心策略，在已经学会在解的围可以确定的情况下，可以采用枚举或递归策略，一一比较它们最后找到最优解；但当解的围非常大时，枚举和递归的效率会非常低。
这时就可以考虑用贪心策略。
贪心算法没有固定的框架，算法设计的关键是贪心策略的选择，贪心策略要具有无后向性，即某阶段状态一旦确定以后，不受这个状态以后的策略的影响。
当一个问题有好几种解决方法时，贪心法应该是最好的选择之一。
本文讲述了贪心算法的含义、基本思路以及贪心算法在实例中的应用。
关键词：贪心算法；删数问题；最小生成树一、引言在平时解决问题的过程中，当一个问题就有无后向性和贪心选择性质时，贪心算法通常会给出一个简单、直观和高效的解法。
贪心算法通过一系列的选择来得到一个问题的解。
它所做的每一个选择都是当前状态下就有某种意义的最好选择，即贪心选择；并且每次贪心选择都能将问题化解为一个更小的与原问题具有相同形式的子问题。
尽管贪心算法对于很多问题不能总是产生整体最优解，但对于最短路径、最小生成树问题，以及删数问题等却可以获得整体最优解，而且所给出的算法一般比动态规划算法更为简单、直观和高效。
二、贪心算法的含义和特点（一）贪心算法的含义贪心算法是通过一系列的选择来得到问题解的过程。
贪心算法是一种能够得到某种度量意义下的最优解的分级处理方法，它总是做出在当前看来是最有的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解算法。
（二）贪心算法的特点1、从全局来看，运用贪心策略解决的问题在程序运行过程中无回溯过程，后面的每一步都是当前看似最佳的选择，这种选择依赖已作出的选择，但并不依赖未作出的选择。
2、不能保证最后求出的解是最佳的。
由于贪心策略总是采用从局部看来是最优的选择，并不从整体上加以考虑。
另外贪心算法只能用来求某些最大或最小解的问题，因为当遇到求解权值最小路径等问题采用贪心算法得到的结果并不是最佳。
二、贪心算法在实例中的应用（一）删数问题给定n位正整数a，去掉其中任意k≤ｎ个数字后，剩下的数字按原次序排列组成一个新的正整数。
对于给定的ｎ位正整数ａ和正整数ｋ，设计一个算法找出剩下数字组成的新数最小的删数方案。
１、算法原理从最高位开始，依次向低位搜索，一旦遇到前一位（高数）的数大于当前位，则删去前一位，直到删除ｋ个数，如果到达末尾还没有删除ｋ个，则说明现在这个数已经是从小到大排列了，则从最低位开始删除要求的位数。
２、过程分析ｎ１＝＂１２４３５８６３＂ k=3４比３大删除＂１２３５８６３＂８比６大删除＂１２４３５６３＂6比3大删除＂１２４３５８３＂只看这个实例，有可能归纳不出正确的算法，看下一个实例，再进一步解释。
n2=＂2 ３１１８３＂ k=33比1大删除＂2 １１８３＂2比1大删除＂１１８３＂8比3大删除＂１１３＂由实例n1，相邻数字只需从前向后比较；而从实例n2中可以看出当第i位与第i+1位比较，若删除第i位后，必须向前考虑第i-1位与第i+1位进行比较，才能保真结果的真确性。
（二）最小生成树设G = (V, E)是一个无向连通带权图，即一个网络。
E的每条边(v, w)的权为c[v][w]。
如果G的一个子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。
生成树的各边的权的总和称为该生成树的耗费。
在G的所有生成树中，耗费最小的生成树称为G的最小(优)生成树。
1、算法原理（1）Prim算法基本思想：在保证连通的前提下依次选出权重较小的n – 1条边。
G=(V, E)为无向连通带权图，令V={1, 2, …, n}。
设置一个集合S ，初始化S = {1}，T = Φ。
贪心策略：如果V–S中的顶点j与S中的某个点i连接且(i, j)是E中的权重最小的边，于是就选择j(将j加入S)，并将(i, j) 加入T中。
重复执行贪心策略，直至V–S为空。
（2）Kruskal算法基本思想：在保证无回路的前提下依次选出权重较小的n – 1条边。
贪心策略：如果(i, j)是E未被选中的边中权重最小的，并且(i, j)不会与已经选择的边构成回路，于是就选择 (i, j)。
若边(i, j) 的两个端点i和j属于同一个连通分支，则选择(i, j) 会造成回路，反之则不会造成回路。
因此初始时将图的n个顶点看成n个孤立分支。
（3）两种算法的异同两种算法不同之处在于，Prim算法是在在保证连通的前提下依次选出权重较小的n – 1条边。
而Kruskal算法在保证无回路的前提下依次选出权重较小的n – 1条边。
两种算法的相同之处在于都是在各自的前提条件下采取依次取出权值最小n-1条边的贪心策略。
2、分析过程（1）Prim算法给定一个联通带权图如下：初始时S={1}，T= Φ；第一次选择：(1,3)权最小， S={1,3}， T= {(1,3)} ；第二次选择：(3,6)权最小， S={1,3,6}， T= {(1,3)（3,6）} ；第三次选择：(4,6)权最小， S={1,3,6,4}， T= {(1,3)（3,6）（6,4）} ；第四次选择：(2, 3)权最小， S={1,3,6,4,2}， T= {(1,3)（3,6）（6,4）（2,3）} ；第五次选择：(2,5)权最小， S={1,3,6,4,2,5}， T= {(1,3)（3,6）（6,4）（2,3）（2,5）} ；（2）Kruskal算法给定一个联通带权图如下：初始时为六个孤立的点，选择了1，于是1、3点合并为同一个集合；选择了2，于是4、6点合并为同一个集合；选择了3，于是2、5点合并为同一个集合；选择了4，于是1、3、4、6点合并为同一个集合；考察边5，因为1、4为同一集合，故被放弃；选择了6，于是1、3、4、6、2、5点合并为同一个集合；选择了1，于是1、3点合并为同一个集合；已经选择边了n–1条边，算法结束。
结果如图所示：3、算法设计（1）Prim算法Prim(int n, Type **c) {int j = 1; s[j] = true;//初始化将节点1放入s并初始化closest[]和lowcost[]for (int i = 2; i <= n; i++){closest[i] = 1; lowcost[i]=c[1][i]; s[i]=false;}for (int i = 1; i < n; i++) { / /执行以下操作n-1次min= inf;for (int k = 2; k <= n; k++) {//依据lowcost[]找出与s最近的点j并放入Sif (lowcost[k]<min&&!s[k]){min = lowcost[k]; j = k}s[j] = true; }}for (int k = 2; k <= n; k++) { //调整closest[]和lowcost[]if (c[j][k]< lowcost[k]&&!s[k]){lowcost[k] = c[j][k]; closest[k] = j}}}（2）Kruskal算法Kruskal(int n, **e) {Sort(e, w); //将边按权重从小到大排序initialize(n); //初始时每个顶点为一个集合k = 1; //k累计已选边的数目，j = 1; //j为所选的边在e中的序号while (k < n) //选择n – 1条边{a = Find(e[j][u]); b = Find(e[j][v]);//找出第j条边两个端点所在的集合if (a != b) {t[k++] = j; Union(a, b)}//若不同，第j条边放入树中并合并这两个集合j++ }} //继续考察下一条边4、Prim和kruskal算法两者的复杂性Prim算法为两重循环，外层循环为n次，层循环为O(n)，因此其复杂性为O(n2)。
Kruskal算法中，设边数为e，则边排序的时间为O(e)，确定边的时间为O(loge)，所以整个时间复杂性为O(eloge)。
当e = Ω(n2)时，Kruskal算法要比Prim算法差；当e = ο(n2)时，Kruskal算法比Prim算法好得多。
三、总结与展望（一）总结贪心算法是很常见的算法，贪心策略是最接近人的日常思维的一种解题策略，虽然它不能保证求得的最后解一定是最佳的，但是它可以为某些问题确定一个可行性围。
贪心算法所作的选择依赖于以往所作过的选择，但决不依赖于将来的选择，这使得算法在编码和执行过程中都有一定的速度优势。
对于一个问题的最优解只能用穷举法得到时，用贪心算法是寻找问题最优解的较好算法。
对一个问题可以同时用几种方法解决，贪心算法并不是对所有的问题都能得到整体最优解或是最理想的近似解时，就需判断贪心性质的正确性了。
与回溯法、动态规划法等比较，它的适用区域相对狭窄许多。
总之，如果一个贪心解决方案存在，就可以使用它。
（二）展望对于贪心算法的应用，如果某个问题具有贪心算法的贪心选择性质和最优子结构性质，那么，它就可以采用贪心策略进行分析，进而求解，贪心算法的应用举例不仅只有本论文中的那几个，他对于背包问题、最优装载问题、硬币找钱问题等都是十分方便有效的算法，贪心算法在科学计算和工程中的应用也越来越广泛，例如用贪心算法进行三角剖分的指纹匹配方法、贪心算法在竞赛中的应用、贪心算法在排课系统中的应用、贪心聚类算法及其在遥感图像分类和压缩中的应用等等，在未来出现的一些问题中，只要符合贪心算法的贪心策略性质，就可以用贪心算法求解，让贪心算法能够应用到更广更多的问题中去吧！【参考文献】[1]吕英国.任瑞征.钱宇华.算法设计与分析[M].:清华大学.[2]URL wenku.baidu./view/f11d5d2a3169a4517723a341.html.。
