贪心算法及其应用

本文首先介绍了贪心算法的概念，然后指出其特性，然后再阐述证明贪心性质的一种方法。紧接着通过一些简单的例子来讲述贪心算法的应用，再通过几个较复杂的应用来体现贪心算法在解决某些问题时的优越性。     

基于贪心算法的智能RGV的动态调度策略

一种智能加工系统由8台计算机数控机床(CNC)、1辆轨道式自动引导车(RGV)、1条RGV直线轨道、1条上料传送带、1条下料传送带等附属设备组成。文章通过研究RGV的选择判断规律,以一道工序无故障情况为例,在RGV需要选择去向时采用贪心算法,这体现为RGV每次选择去向时选择运动时间与上下料时间之和最小的目标,将该过程定为所有判断的原则。故可得出动态调度后每个CNC的总等待时间最少,将机床工作效率最大化。从而给出最优动态调度策略。     

太阳能建筑物外观及表面光伏组件铺设优化

针对太阳能建筑物外观图的设计及外表面太阳能光伏组件铺设优化问题,首先通过建立以建筑物5个外表面全年总辐射量最大为目标的单目标规划模型,并考虑建筑物的设计要求,基于模拟退火法给出了建筑物的外观设计图,并根据电池性能的优劣顺序及限制条件,利用贪心算法得到建筑物外表电池铺设方案,最后给出了这种方案下的投资收回年限及寿命期内的经济效益。     

基于聚类分析和贪心算法的文件碎片拼接复原

针对文献修复中均匀碎片,以特征位置为基准,采用K-means算法进行聚类分析,对于每一类碎片运用贪心算法不断地取匹配度最高的碎片进行拼接,逐步自动复原整个文献。经计算机仿真证明:此方法能实现文献的快速拼接,有效地提高物证修复,碎片复原的工作效率。     

结合部件动态变化度求解最小碰集的GRASP算法

针对最小碰集求解问题,提出一种改进的GRASP算法。在算法构造解阶段,提出一种结合部件动态变化度d-covered的打分机制,用来选择可能是最小碰集的部件,避免非最小碰集部件的加入,并能较早地得到最小碰集;在算法局部搜索阶段,结合部件动态变化度drcovered给出锦标赛策略,进而从当前解对应的冗余部件中删除较可能是非最小碰集的部件。此外,还给出了完备算法和不完备算法的时间复杂度分析。实验结果表明:与现有完备算法相比,本文算法能够在较短的时间内找到最优解;与现有不完备算法相比,本文算法可以找到更短长度的最小碰集。     

道路交通网络中的关键节点识别方法研究

在现实世界中，大量复杂系统都可以通过抽象的节点和连边构成的网络来加以刻画。作为城市交通系统的重要组成部分，道路交通网络是一个典型的复杂系统，与人们的生活密切相关。道路交通网络中的关键节点识别问题是复杂网络领域研究中的一个经典难题。传统的度中心性算法和PageRank算法在复杂网络的关键节点的识别中具有较好的应用，考虑到道路交通网络中关键节点的特殊性和彼此关联性，在度中心性算法的基础上引入贪心算法的思想，提出了一个基于贪心策略的度中心性关键节点识别方法；同时，在PageRank算法的基础上引入贪心算法的思想，提出了一种基于贪心策略的PageRank关键节点识别方法，从而使道路交通网络中关键节点识别的结果更合理，在交通道路维护保养、规划设计，以及犯罪分子潜逃阻断等领域都有重要的应用价值。通过公开数据集与经典的关键节点识别方法做比较，验证了算法的有效性。     

社会网络中弱关系团队形成问题研究

随着在线社会网络的迅速发展,社会网络的团队形成问题逐渐成为研究热点。现有的社会网络中团队形成问题目标是寻找一个成员间沟通代价最小的团队。然而,实际应用中团队成员间的不紧密关系使得团队的观点多样化、多角度、无偏见,可以广泛应用于形成专家评审团队、大众评审团等。基于此需求,将社会学的弱关系概念引入团队形成问题中,提出了一种社会网络中弱关系团队形成问题。该问题旨在寻找成员间为弱关系,同时满足技能、经验值要求的一个团队,为NP-hard问题。提出了3类算法解决该问题,分别为贪心算法、精确算法、α-近似算法,每类算法有各自的特点与适用范围。利用ACM和DBLP两类真实的数据集进行实验,综合评估了各类算法的效率与求解质量,证明了提出算法的有效性。