导读:本文包含了最小集合覆盖论文开题报告文献综述及选题提纲参考文献,主要关键词:订单拆分,订单分配,最小集合覆盖,改进蚁群算法
最小集合覆盖论文文献综述
韩曙光,章园园[1](2019)在《基于最小集合覆盖的电商订单拆分及配送方式》一文中研究指出订单履约的效率是影响自营型电商平台运营成本与顾客满意度的一个重要指标。传统的拆单方式会导致订单积压,订单履约效率低下。基于电子商务订单的特性,对订单的拆单方式以及后续的配送路径进行研究,建立了非线性整数规划模型,并采用两阶段法的求解思想,将模型分为覆盖订单部分与路径规划部分,以经典最小集合覆盖思想与改进的蚁群算法的联合方法为模型求解算法,对该模型进行求解分析。算例表明,该模型与算法具有有效性和适用性。(本文来源于《浙江理工大学学报(社会科学版)》期刊2019年06期)
徐畅[2](2019)在《基于数据源相关的最小集合覆盖本地化差分隐私保护算法》一文中研究指出随着数据挖掘技术的进步和大量的数据共享,通过多个数据源信息的挖掘,和敏感数据相关联的数据造成隐私泄露的风险大大增加了。本文对多数据源中隐私泄露问题进行研究,基于现有的隐私保护机制,结合集合覆盖问题提出了一种新的隐私保护机制SC-DP,并通过实验证明了该算法的可用性。(本文来源于《科学技术创新》期刊2019年03期)
张育柏[3](2018)在《最小赋权连通集合覆盖问题的近似算法》一文中研究指出集合覆盖问题是组合优化领域中的经典问题,它指的是在给定的集族中选一个阶数最小子集族来覆盖所有给定的元素.该问题不仅具有很高的理论价值,随着无线网络的发展更具有了越来越广泛的应用背景.本文主要研究的是集合覆盖的两种变形:最小赋权部分连通集合覆盖问题(MVW PCSC)和在线3-路点覆盖问题(online VCP3).对于MWPCSC问题,给定元素集合U,集合族S,权函数c:S → Q+,以集合族中集合作为点集的连通图GS,正整数k≤|U|,其目标是找到一个最小权的子集族S'(?)S使得由S'导出的子图连通,且|US∈S'S|≥k.当GS满足任意两个有公共元素的集合在Gs中的跳数(hop distance)不超过r时,这个问题被称为r-hopPCSC.对最小权的1-hopPCSC,我们给出了一个O(ln(m+ n)-近似算法;对最小基数下r-hopPCSC,我们给出了一个O(ln(m + n))-近似算法.和前人的结果比较,我们的方法要简单的多.对于特殊集合覆盖问题——3-路点覆盖,给定图G(V,E),当图G中的每一条3个点的路至少有一个点在C中时,我们称C是一个3-路点覆盖.本文考虑的是在线3-路点覆盖模型:图G的信息,它通过逐点显现的方式呈现出来,当一个新的点出现时,我们必须做出决策,判断它是否需要被选入C中.我们给出了一个自然的算法,其近似比不会超过图G的最大度△,并给出了该近似比的紧例子.(本文来源于《浙江师范大学》期刊2018-03-01)
王练,梁申虎,陈巧,彭代渊,梁宏斌[4](2018)在《中继协作多播网络中基于最小集合覆盖的编码重传方案》一文中研究指出为提高单中继协作多播传输效率,本文提出一种基于最小集合覆盖的分类网络编码重传方案.该方案充分利用中继节点协作传输的优势,将接收端的丢包按中继节点的接收状态分为两类,并按类先后进行编码重传.在各类丢包内部,根据对应的状态反馈矩阵寻找编码机会生成编码包,并将编码包的选择过程抽象为集合覆盖问题,通过求最小集合覆盖使重传次数逼近最小值.此外,在不增加所得前类编码包数的前提下,利用两类丢包之间的编码机会进一步生成新编码包,以减少重传编码包数,从而提高重传效率.分析与仿真结果表明了该方案的有效性.(本文来源于《电子学报》期刊2018年01期)
张立群[5](2015)在《求解拟阵约束下下模函数最小集合覆盖的贪婪算法及其性能保证》一文中研究指出组合优化问题是在一些约束条件下给定的有限集合中,根据某一目标找出一个最符合要求的最优解的这么一类数学规划问题,也称为组合规划。组合优化都是在由有限个方案构成的集合中,选择能够使目标函数达到最优解的最优子集。组合优化问题的发展在生产生活等各个领域有着广泛的应用,例如在商品生产,交通运输航线问题,装箱问题,工作指派问题等。等到拟阵理论进入到组合优化问题的研究领域中,得到了很多理论成果,比如推销问题,最短路问题和最大支撑树问题。下模函数作为一类特殊的实值函数,并且是被定义在幂集上。下模函数的变量是离散的不是连续的。由于这种特殊的性质使得下模函数在求解最优化问题中起到了重要作用。在组合优化中,下模函数最大值问题的求解被当做一个中心问题,我们可以把很多组合优化问题最优值的求解转化成求解下模函数的最大值问题,这使得组合优化问题都可以认为是求解下模函数的最大值问题,归纳出很多重要问题比如最大割、最大熵采样、最大设施选址和集合覆盖的问题。因此我们研究下模函数的最值问题就有非常特殊的理论价值和实践应用价值。然而,求解下模函数是一个NP-难问题,人们不断地寻找有效的多项式算法。本文主要介绍了如何求解下模函数的最优值理论和如何在求解下模函数最大值问题当中应用贪婪算法。我们主要给出一个近似贪婪算法,并将这个贪婪算法运用在被多重拟阵约束下任意非负的下模函数最大值问题。最后介绍了下模函数的最值被k维背包约束下的求解问题。并把各种算法进行了比较全面的理论分析进而得出其性能保证。本文一共分为五章,第一章首先介绍了最优化理论问题的起源与发展和贪婪算法,以及针对不同的算法如何分析它们的性能保证,接着给出了这篇文章研究的背景,最后介绍了这篇文章的任务以及要解决什么样的问题。第二章综述了下模函数的概念及相关定理,以及贪婪算法解决最小集合的覆盖问题,并给出了此贪婪算法的性能保证。第叁章主要详细介绍如何用近似贪婪算法和局部搜索程序对于下模函数最大值被k个拟阵约束下的求解问题,并证明了贪婪算法的近似度为()111 k2ke??+++?÷è?第四章主要介绍了近似算法对于下模函数最大值被k维背包约束下的求解问题,并且证明此算法可以得到一个12 n?e?-?÷è?的近似解。第五章全面的对论文进行了总结、展望。(本文来源于《兰州交通大学》期刊2015-04-01)
张馨,薛质,范磊[6](2012)在《基于最小集合覆盖的网络连通性自动化测试》一文中研究指出网络规模的增长加大了分布式网络管理与测试的难度。为此,提出一种优化的全连通自动化测试用例集生成算法。在最小集合覆盖理论的基础上,引入空间因子参数,优先选取搜索空间中起点或终点被选取次数最多的测试路径进入解集,以减少测试点数。实验结果表明,该算法在空间因子为4的情况下,比贪心搜索算法减少约20%的测试点数,比GRASP算法缩短约99.9%的测试时间,具有较高的测试效率。(本文来源于《计算机工程》期刊2012年24期)
臧文科,刘希玉,刘文菊[7](2012)在《基于面上DNA计算求解最小集合覆盖问题》一文中研究指出利用DNA分子结构推得DNA计算机理及实现方式,提出用面上DNA计算模型求解最小集合覆盖问题,给出了具体应用和算法评价;在计算模板表面穷举了所有可能的结果,同一时间验证结果是否满足条件,实现DNA计算的强大并行性;同时在互补的寡聚核苷酸片段发生退火反应时,通过催化剂来决定是否杂交,减少人工参与、提高计算效率。最后,通过计算机仿真模拟验证了本模型的可行性。(本文来源于《计算机应用研究》期刊2012年04期)
张文鹏,李红婵,王兴[8](2011)在《结合类内集中度和最小集合覆盖的特征选择》一文中研究指出特征选择是文本分类中的核心研究课题之一。简单分析了词频和文档频,在此基础上提出了类内集中度,把集合覆盖的思想引入粗糙集并提出了一个基于最小集合覆盖的属性约简算法,把该属性约简算法同类内集中度结合起来,提出了一个新的特征选择方法。该方法利用类内集中度进行特征初选以过滤掉一些词条来降低特征空间的稀疏性,利用所提约简算法消除冗余,从而获得较具代表性的特征子集。实验结果表明此种特征选择方法效果良好。(本文来源于《计算机工程与应用》期刊2011年28期)
吴晨辉[9](2010)在《无线传感器网络最小集合覆盖问题的DNA算法研究》一文中研究指出无线传感器网络(Wireless Sensor Network, WSN)是一种新兴的科学技术网络,最早的研究来源于美国军方。网络覆盖问题是无线传感器网络研究和应用的关键性基础问题,直接影响着网络的使用性能。无线传感器的超大规模、节点自由密集分布、通信能力受限、计算和存储能力受限以及网络覆盖范围无人职守,恶劣的应用环境给网络覆盖带来了很大的挑战。特别是传感器中大部分节点的能量靠电池提供,而由于条件受限,很难在使用过程中给节点更换电池。所以传感器节点的能量限制是整个无线传感器网络设计的瓶颈。因此,在保证网络覆盖及网络通畅的基础上,如何延长网络工作时间,是目前无线传感器网络研究领域的一个重要方面。本文提出把无线传感器覆盖范围问题转化成图论中的组合优化问题-最小集合覆盖问题,把实际应用问题转化成数学模型,对无线传感器网络区域覆盖进行数学建模。然后运用DNA计算模型中的粘贴模型算法来求解最小集合覆盖问题。并且在最小集合覆盖问题的基础上,提出并解决κ层纵向覆盖问题,从而使无线传感器网络的运行生存时间提高至κ倍。本文创新点在于是应用基于生物技术的DNA算法来解决无线传感器网络区域覆盖问题。该DNA算法将分子生物计算与数学领域、无线传感器网络领域的相关问题融合起来,其巨大的并行计算能力为无线传感器网络覆盖问题的节能优化设计提供了一个新颖有效的方法。(本文来源于《华东理工大学》期刊2010-12-25)
刘敏,段富,刘超慧[10](2008)在《基于最小集合覆盖的属性约简算法》一文中研究指出在粗糙集理论的各种应用中,属性约简算法具有重要的意义,因而对属性约简算法的研究一直是粗糙集理论研究中的重点问题之一。在对属性约简算法充分研究的基础上提出一种基于最小覆盖集的粗糙集属性约简算法,即通过构造知识系统的一种改进的相关矩阵将属性约简简化为最小覆盖问题。将该算法与文献[7]中的算法进行实验比较并对结果进行分析,实验结果表明,当随着数据量增大时该算法具有更小的时间复杂度。(本文来源于《电脑开发与应用》期刊2008年08期)
最小集合覆盖论文开题报告
(1)论文研究背景及目的
此处内容要求:
首先简单简介论文所研究问题的基本概念和背景,再而简单明了地指出论文所要研究解决的具体问题,并提出你的论文准备的观点或解决方法。
写法范例:
随着数据挖掘技术的进步和大量的数据共享,通过多个数据源信息的挖掘,和敏感数据相关联的数据造成隐私泄露的风险大大增加了。本文对多数据源中隐私泄露问题进行研究,基于现有的隐私保护机制,结合集合覆盖问题提出了一种新的隐私保护机制SC-DP,并通过实验证明了该算法的可用性。
(2)本文研究方法
调查法:该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法:用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法:通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法:通过调查文献来获得资料,从而全面的、正确的了解掌握研究方法。
实证研究法:依据现有的科学理论和实践的需要提出设计。
定性分析法:对研究对象进行“质”的方面的研究,这个方法需要计算的数据较少。
定量分析法:通过具体的数字,使人们对研究对象的认识进一步精确化。
跨学科研究法:运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法:这是社会科学用来分析社会现象的一种方法,从某一功能出发研究多个方面的影响。
模拟法:通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
最小集合覆盖论文参考文献
[1].韩曙光,章园园.基于最小集合覆盖的电商订单拆分及配送方式[J].浙江理工大学学报(社会科学版).2019
[2].徐畅.基于数据源相关的最小集合覆盖本地化差分隐私保护算法[J].科学技术创新.2019
[3].张育柏.最小赋权连通集合覆盖问题的近似算法[D].浙江师范大学.2018
[4].王练,梁申虎,陈巧,彭代渊,梁宏斌.中继协作多播网络中基于最小集合覆盖的编码重传方案[J].电子学报.2018
[5].张立群.求解拟阵约束下下模函数最小集合覆盖的贪婪算法及其性能保证[D].兰州交通大学.2015
[6].张馨,薛质,范磊.基于最小集合覆盖的网络连通性自动化测试[J].计算机工程.2012
[7].臧文科,刘希玉,刘文菊.基于面上DNA计算求解最小集合覆盖问题[J].计算机应用研究.2012
[8].张文鹏,李红婵,王兴.结合类内集中度和最小集合覆盖的特征选择[J].计算机工程与应用.2011
[9].吴晨辉.无线传感器网络最小集合覆盖问题的DNA算法研究[D].华东理工大学.2010
[10].刘敏,段富,刘超慧.基于最小集合覆盖的属性约简算法[J].电脑开发与应用.2008