贪心算法

摘要： 带有时序特征的知识图谱(KG)称为时序知识图谱,用来描述知识库中增量式的概念及其相互关系。知识随着时间推移而变化,将新增知识实时、准确地添加到时序知识图谱中,可以实时反映知识的演化更新。对此,给出时序知识图谱的定义,并基于TransH提出一种时序知识图谱的增量构建方法。为了将新增且相关的三元组准确地添加到当前知识图谱中,提出了三元组与当前知识图谱之间吻合度的计算模型,以及基于贪心思想的待添加到知识图谱中的最优三元组子集提取算法,进而将最优的三元组集合添加到当前知识图谱中,完成时序知识图谱的增量更新。实验结果表明,提出的增量构建方法能够快速地提取出最优三元组并有效地添加到知识图谱中,验证了方法的高效性和有效性。

摘要： 0-1背包问题作为经典的NP完全问题一直得到广泛的关注和研究。研究发现,经典回溯算法在解决0-1背包问题时的算法时间复杂度较高,尤其是在物品数量较多时,短时间内不能得到问题的解,导致算法的适用性较差。虽然经典贪心算法和现阶段涌现出的大量新型算法能够极大地缩减算法的运行时间,但普遍是以牺牲算法的准确性为代价的,不能保证可以找到问题的最优解。针对这些问题,提出一种融合贪心策略和剪枝策略的新型回溯算法。该算法将贪心算法得到的问题近似解用于剪枝策略的判断条件中,并在物品取舍时将当前的物品重量与背包的剩余容量进行比较,以避免重复计算,减少迭代次数,提高算法的执行效率。大量的仿真实验结果表明,在一定问题规模下,与经典回溯算法相比,所提出的新型回溯算法仍能够在短时间内准确找到问题的最优解,且具有更高的执行效率。

摘要： 1959年,计算机科学家E.W.Dijkstra提出了Dijkstra算法。Dijkstra算法是一种解决单源最短路径问题的贪心算法,其作用主要表现在解决有向图中的最短路径问题方面。但随着科学技术的发展,Dijkstra算法的应用领域得到了极大的扩展,“最短路径”也被赋予了全新的含义,不再单单指空间中的最短距离,同样也可以用来研究各种时间、经济、能量消耗问题。但是,随着研究问题的复杂化以及所研究数据规模的逐渐扩大,传统的串行Dijkstra算法计算量大、时间复杂度较高的问题也逐渐体现出来,影响着Dijkstra算法在诸多问题中的表现。而并行化计算不仅在计算大规模数据时表现优异,也非常契合Dijkstra算法的算法思想。

摘要： 在挖掘翻译语料库异质性特征时,现有方法易重复选择异质性特征,导致得到的特征节点偏移量过大。针对这一问题,基于贪心算法设计一种新的翻译语料库异质性特征自动挖掘方法。在特征选择的解空间中设定一个公共测试代价,将特异性特征定义为形式化的集合。在将该集合处理为节点集合后,采用贪心算法评估语料库节点影响潜力,并整合节点影响潜力为一个维度的样本集,然后构建一个激活函数,最终实现异质性特征的自动挖掘。对比实验结果表明:上述挖掘方法得到的特征节点偏移量最小,证明该方法的有效性较强。

摘要： 飞行器各油箱内油量的分布和飞行器供油策略将导致飞行器质心的变化,进而影响飞行器姿态控制。以某智能飞行器为研究对象,通过建立各飞行姿态下油箱质心位置与飞行器整体质心位置间联系的数学模型,将飞行器供油策略问题转化为使用贪心算法搜索每一时刻的最佳供油油箱及其供油速度的最优解问题。在各个油箱初始油量未知的条件下,选用收敛性好、运行效率高的LDM PSO算法(改进权重粒子群算法)进行供油策略求解,实现飞行器的质心平衡优化。所建立的算法有效解决了遍历规划的运算复杂性问题,为飞行器质心平衡供油策略规划提供参考。

摘要： 国家税务机关针对不同开票主体的经营规模,规定了不同发票类型的单张发票不含税金额上限,开票系统通常按照国家税务机关规定对开票申请进行自动拆分。拆分的原则通常需要保证两个维度,即开具发票的数量最小、发票金额准确。在实际开票操作中,根据不同业务场景,对发票拆分效果有着不同要求和侧重,如优先最小开票数量,又如优先金额取整等。针对实际需求,基于动态规划和贪心算法中局部最优解的思想,提出了多种发票拆分算法,可供用户通过算法配置实现不同的拆分效果。

摘要： 移动边缘计算技术随着科技的发展,面临着多设备多任务的能耗均衡的挑战。相关研究大多集中在如何利用边缘服务器的计算性能以减少移动设备在任务处理过程中的能耗和执行时间。但现有研究在多设备多任务的能耗均衡问题上还没有很好的解决方法。针对此类能耗均衡问题,改进了现有的边缘计算系统模型,并在此基础上,给出了多移动设备多任务的能耗均衡优化问题的计算模型,同时提出了一个贪心算法,并做出了相应的近似比分析。与总能耗优化算法以及随机算法进行对比,并进行了大量的仿真实验。实验结果证明,所提出的贪心算法的平均性能与随机算法相比在能耗均衡方面可进一步提升66.59%。通过与蛮力算法对比,在经典的任务拓扑下,当移动设备的最小传输功率分别为5 dBm和6 dBm时,贪心算法几乎获得最优解。

摘要： 本文主要研究由于瓷砖厂马赛克瓷砖颜色有限,而原始图像颜色过多产生的最优颜色瓷砖的替代问题。考虑到图像的表现力,只要瓷砖的RGB颜色点能够尽量均匀分布在空间中,找出与已定22种颜色组成后能最大限度拟合整个RGB色块的颜色。再将整个RGB块分割为8个区域,取每个色块顶点作为待选点,采用离散型选址问题,结合加权后的像素颜色欧式距离公式以及迭代算法计算出最优解,使得每增加一种颜色后,根据算法输出的颜色距离值最小的点即为增加的颜色点,再通过贪心算法得出需要增加的1~10种颜色。

摘要： 无人机与移动边缘计算技术的结合突破了传统地面通信的局限性。无人机所提供的有效视距信道可大大改善边缘服务器与移动设备之间的通信质量。为了进一步提升移动边缘计算系统的服务质量,设计了一种多无人机使能的移动边缘计算系统模型。在该系统中,无人机作为边缘服务器为移动设备提供计算服务,通过联合优化无人机部署与计算卸载策略实现平均任务响应时间的最小化。基于问题定义,提出了一种PSO-GA-G双层嵌套联合优化方法,该方法的外层采用了结合遗传算法算子的离散粒子群优化算法(Discrete Particle Swarm Optimization Algorithm Combined with Genetic Algorithm Operators,PSO-GA),实现了对无人机部署位置的优化;而该方法的内层则是采用了贪心算法(Greedy Algorithm),实现了对计算卸载策略的优化。大量仿真实验验证了所提方法的可行性和有效性。实验结果表明,相比其他基准方法,所提出方法可以实现更短的平均任务响应时间。

摘要： 以数据驱动的方式,首先通过分析北京市87辆私家车3个月的行驶轨迹记录,结合地图信息,对电动汽车充电需求进行量化分析,从而进行科学合理的充电站选址布局。根据每辆车车主的电动汽车使用习惯,提出了一种电动汽车充电概率计算模型,在此基础上利用P中值模型和贪心算法,以距离需求点之和最小为优化目标,得到了一种将电动汽车用户充电需求与充电站选址方法,从备选的56个停车场集合中得到了最为满足充电需求的15个停车场的集合。所用选址方法由真实数据驱动,可以助力未来北京市电动汽车充电基础设施建设。

摘要： 具有主动成像能力的视频成像卫星是一类新型对地观测卫星,依靠主动成像能力,它对地观测的成像时长是可变的.卫星可以获取地面目标一段时间内的连续图像信息,特别对于监视目标具有更强的观测能力.但新型的能力给卫星成像任务调度带来新的挑战,增加了任务调度问题求解的难度.本文将研究此类新型的更为复杂的卫星成像任务调度问题,提出一种成像时长计算方法.基于一类简单贪心算法,设计两类试验:单体试验和整体试验,详细分析任务成像时长变化的对卫星成像任务调度问题求解的影响,归纳一系列启发知识,并在贪心求解算法引入这些启发知识,分析算法的提升性.

摘要： 泛在电力物联网背景下,智能变电站中负责运行状态上传与控制命令下达的过程层网络负载将急剧升高.传统IEC61850标准协议中的高可用性无缝冗余(High-Availability-Reamless Redundancy,HSR)通信链路配置方法由于数据副本在存在环路的网络内循环产生额外流量与额外传输延时,存在信息传输实时性差的缺点.因此,提出基于贪心流量优化算法的过程层网络拓扑高冗余无缝配置方法.首先,在分析采用HSR技术的智能变电站过程层网络工作原理的技术上,提出两种高可用性无缝冗余配置方案:交叉(Cross-Links,CLs)方案与四连通环(Four-Connected Rings,FCRs)方案.其次,为避免过程层网络在流量汇聚时易产生拥塞导致传输时效性变差,提出基于贪心算法的流量调度策略.最后,基于Opnet的变电站仿真算例表明,与传统网络拓扑配置方案相比,所提方案的数据平均传输跳数与传统拓扑方案比下降50％,而采用贪心算法的过程层网络流量调度策略在数据拥塞时的传输延时、丢包率和吞吐量衰退服务分别降低32.7％,63.5％和33.3％.因此,所提方案能够显著提升智能变电站过程层网络性能.

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

摘要： 影响力最大化问题的研究为病毒式营销提供了潜在有效的解决方案.基于时间约束的影响力最大化问题IMTC定义为在时间约束条件下,如何在社会网络中定义和挖掘一部分初始用户,使得在影响力传播过程结束后,网络中被影响的节点的个数最大.现有的研究工作主要依据网络结构定义节点影响力,优化传统影响力传播模型,或改进启发式算法提高初始节点的选取质量,行为的执行与其影响作用生效之间的时间延迟特性以及影响力传播过程中的时间约束条件往往被忽略.针对这点不足,提出一种基于时间约束的信用分布模型CDTC,综合考虑用户之间的见面概率和先验激活概率对边缘概率进行计算,并对网络中的相邻节点之间分配的直接信用进行优化定义.同时结合用户行为日志,将见面与激活事件对信用分配的阻碍作用映射到行为传播路径长度的增量性测量和评估方面,并结合时间约束条件限定性地对路径中的节点逆向分配代表影响力大小的信用值,最后根据信用分布函数,使用基于时间约束的贪心算法GA-TC递归选取网络中边际收益最大的节点得到初始节点集合.实验结果表明在CDTC模型上使用GA-TC算法不仅能够保证初始节点选取的质量,而且由于其更高的执行效率以及更好的行为执行预测能力,方法对IMTC问题的适应性更强.

摘要： 针对天津电台音视频网站发布系统网络带宽分散、局部服务器压力过大的问题,对系统进行了升级改造.在该项目中整合了网络链路;利用流媒体日志数据的分析结果作为数据支持,以贪心算法的思想为核心,对发布点进行了合理的分配,使服务器的负载趋于均衡,解决了流媒体发布服务器局部压力过大的问题.

摘要： 在课题组开发的流场求解器HUNS3D的基础上发展了网格变形和气动弹性计算方法.对于物面网格节点数目较多的网格利用贪心算法在过程中进行数据精简从而有效减少计算量.由于结构表面网格相对于流体网格数量较少,故作为RBF的样本点来进行网格变形.气动弹性计算的每步循环中包含表面气动力和表面位移采用RBF作为子程序进行插值.为了证明程序的有效性,利用算例进行了验证.结果证明在基于CFD的气动弹性计算和任意变形分析中,利用贪心法改进的RBF插值方法与体网格大小无关,且在大变形下依然效果良好.

摘要： 营房物资是武誓部队遂行多样化任务重要保障物资,营房物资调度的迅速和准确与否影响着武警部队能否出色完成多样化任务.在当下,突发事件发生日益频繁,武警部队遂行救灾、反恐、维稳任务较多,因而营房物资的调度显得愈发重要.本文通过对武警部队营房物资调度的特点分析，建立了营房物资需求变化情况下，基于时间最小化和成本最小化的数学模型，并根据分层序列法确定第一目标，采用基于贪心算法的求解方法进行求解，得出优化目标，同时给出算例分析得出了相应的结论。综上表明，本文所采用的优化模型对于营房物资调度方案的制定具有积极意义。

摘要： 通讯延迟是衡量CAN网络实时性的重要指标,随着CAN总线在航空、医疗等领域的应用,人们对CAN总线数据传输的实时性提出了更高的要求.最小化CAN消息集平均延迟时间问题是NP难问题,本文旨在提出最小化消息平均延迟的近似算法.通过分析最坏情况下的消息延迟时间的数学模型,得到了优先级分配时影响消息通信延迟的关键因素.基于最优的优先级分配算法Audsley算法,本文提出了四种通讯延迟感知的优先级分配算法:TMPA,UMPA,GTMPA和GUMPA.实验结果表明,与传统的算法相比,TMPA,GTMPA和GUMPA算法能够有效减少消息的平均延迟时间.

摘要： 通讯延迟是衡量CAN网络实时性的重要指标,随着CAN总线在航空、医疗等领域的应用,人们对CAN总线数据传输的实时性提出了更高的要求.最小化CAN消息集平均延迟时间问题是NP难问题,本文旨在提出最小化消息平均延迟的近似算法.通过分析最坏情况下的消息延迟时间的数学模型,得到了优先级分配时影响消息通信延迟的关键因素.基于最优的优先级分配算法Audsley算法,本文提出了四种通讯延迟感知的优先级分配算法:TMPA,UMPA,GTMPA和GUMPA.实验结果表明,与传统的算法相比,TMPA,GTMPA和GUMPA算法能够有效减少消息的平均延迟时间.

摘要： 通讯延迟是衡量CAN网络实时性的重要指标,随着CAN总线在航空、医疗等领域的应用,人们对CAN总线数据传输的实时性提出了更高的要求.最小化CAN消息集平均延迟时间问题是NP难问题,本文旨在提出最小化消息平均延迟的近似算法.通过分析最坏情况下的消息延迟时间的数学模型,得到了优先级分配时影响消息通信延迟的关键因素.基于最优的优先级分配算法Audsley算法,本文提出了四种通讯延迟感知的优先级分配算法:TMPA,UMPA,GTMPA和GUMPA.实验结果表明,与传统的算法相比,TMPA,GTMPA和GUMPA算法能够有效减少消息的平均延迟时间.

摘要： 本发明属于计算机无线通信技术领域，涉及在基站集成无线网络环境下,一种基于新效用函数贪心策略的按需服务数据包调度贪心算法。首先我们建立该环境下数据包调度问题的数学模型，包括时隙模型和报文请求模型，将原问题转化为整形规划问题，这种整形规划问题可以证明为NP问题，在线性时间内不能找到其最优解，根据模型的特殊情况，可以将问题转化为0‑1整形规划问题，这样可以大大的减少求解问题的复杂性。在实际的online条件(即当前只有部分信道情况已知，部分待调度报文到达)下，基于本文提出的效用函数函数值的贪心策略比基于现有效用函数的贪心策略具有更好的仿真效果，能够提高分配报文的总效益。

摘要： 本发明公开了一种基于贪心算法的星座区域目标侧摆角调度方法，包括以下步骤：S1、确定星座构型；S2、建立简化卫星轨道外推模型；S3、计算星下点位置；S4、计算卫星覆盖条带；S5、设置目标区域并进行网格化处理；S6、添加约束条件；S7、利用贪心算法计算载荷侧摆角度；S8、输出仿真结果；能够根据目标区域自动调整卫星侧摆角度，解决覆盖条带缝隙不能有效覆盖问题，有效缩短区域全覆盖所用时间。

摘要： 本发明提供一种基于有界渗流‑贪心算法的病毒传播控制方法。首先，提取目标网络信息，了解目标网络节点及连边属性；然后，基于渗流理论，在目标网络上不断占据特定节点，实现移除关键节点的逆向过程；每次占据使目标函数最小的节点，限制最大连通分量的大小和剩余网络节点度数，控制病毒传播；设置关键指标界值，当所有候选节点的关键指标超出界值时，更新界值以占据更多候选节点；最后，利用序参量、网络韧性表示控制病毒传播的效果。本发明可以实现大型网络的快速高效分解，从而及时控制病毒传播，降低其造成的损失。

摘要： 本发明公开了一种基于比例化贪心算法和ACE‑PTS的子载波分配方法，旨在解决抑制OFDM系统峰均比中损耗系统速率的问题，以及子载波分配过程中复杂度较高的问题。该子载波分配方法的步骤为：1)利用比例化贪心算法预分配子载波；2)正交调制子载波；3)利用ACE‑PTS方法对子载波序列分配位置次序；4)优化重组子载波序列。本发明能有效抑制信号峰均比，实现系统吞吐量最大化，降低子载波分配的复杂度，可用于正交频分复用OFDM系统中的子载波分配。

摘要： 本发明涉及生物信息学分析技术领域，具体涉及一种基于CPE和CPD实现高效个体识别位点筛选的贪心算法，包括：S1、变量声明与专有名词设置：S11、寻找一个有效的STR位点集合：L；S12、一个位点l的辨别能力(PD)：dl；S13、L的联合辨别能力(CPD)：DL。本发明，CODIS主要是针对美国人群，而本算法适用于不同的人群，由于这一算法是在假设数据中的个体在生物学上无关的情况下提出的，因此还可以用于其他人种甚至物种的个体识别，同时，本算法的效果好，所选位点在身份鉴定中具有较高的联合鉴别能力，在亲子鉴定中具有较高的联合排除概率。在我们的模拟中，所选的STRs在统计学上优于CODIS的STRs，错误包含和排除的概率较低。

摘要： 本发明公开了一种基于顶点判别和贪心算法的LLC变换器鲁棒性设计方法，包括步骤：1)在输入电压最小、负载最大的条件下建立K‑Cr平面，依据约束条件，在K‑Cr平面上确定可行解集域的范围；2)由于电容和电感在实际应用中存在容差，K‑Cr平面上的点转化为矩形区域，采用顶点判别法确定最终的可行解集域；3)寻找矩形区域内效率最低的一个点，将该点定义为区域效率最低点(LFE点)；4)依据LFE点定义最优区域，采用贪心算法在可行解集域内寻找最优参数解。本发明依据顶点判别法，确定最终的可行参数解集域，并采用贪心算法，寻找考虑元件容差后的最优参数组，以效率最优为设计目标提供了全新的频率调制LLC谐振变换器鲁棒性设计方法。

摘要： 本发明公开了一种在弱感知条件下基于贪心算法的快速目标搜索方法，该方法包括步骤1、根据城市地图中的路口得到节点集合N＝{i|i＝1,2,...,n}，n表示全部节点数量；步骤2、在从出发点位置向最近的所述节点运动时，根据信号强弱得到当前位置与目标节点的相对位置；步骤3、到达下一个所述节点后，基于当前节点与所述目标节点的相对位置，对所有所述节点的概率进行更新，以得到概率更新后的结果；步骤4、根据所述概率更新后的结果得到所述目标节点的位置。本发明的方法实现了在弱感知条件下对目标的快速搜索，特别是引入的概率地图加速了算法收敛速度，从而能够快速准确的搜索出目标的具体位置。

摘要： 本发明公开了一种基于随机贪心算法的横向联邦梯度提升树优化方法，包括如下步骤协调方设置梯度提升树模型相关参数，包括但不限于决策树最大数量T、树最大深度L、初始预测值base等，并下发到各个参与方p

摘要： 基于带扰动贪心算法的水下导弹发射时序快速确定方法，属于时序规划领域。为了解决现有的水下导弹发射时序确定方法并没有考虑扰动因素而导致影响发射效果的问题。本发明由影响函数及给定的影响限制计算第K发弹下所有备选弹的时间间隔，根据前一发弹的时间间隔以及扰动策略选择此发弹的发射方案；扰动策略中，当K为中间弹时，如果前两发弹时间间隔上临界时间间隔，随机挑选上游的发射方案；否则，逐个确定每发弹的位置和发射时刻，得到发射位置和时间序列；影响函数为前K‑1发弹发射后尾涡与第K发弹的间距对第K发弹的影响。主要用于水下导弹发射时序的快速确定。

摘要： 本发明公开了一种基于Epsilon贪心算法监测人工流量作弊的方法及装置，所述的方法包括，(一)对原始数据预处理：将原始数据集，进行PCA降维处理，筛选出空间特征数据集和时间特征数据集；(二)从空间特征判断，判断是否为空间特征作弊流量；(三)从时间特征判断，判断是否为时间特征作弊流量；(四)将空间特征作弊流量和时间特征作弊流量融合并最终分类。本发明的基于Epsilon贪心算法监测人工流量作弊的方法及装置，可有效识别人工点击方式生成的作弊流量，从而让厂商规避广告成本增加的风险。并且间接提高了厂商服务器的可用性和可靠性。