一、贪婪算法与最坏性能比分析（论文文献综述）
熊凯[1]（2021）在《面向交通出行的车联网资源调度策略研究》文中研究指明近年来,随着第五代移动通信技术（The Fifth Generation,5G）与车联网业务的蓬勃发展,车辆通信技术繁多,新型车联网接入方式呈现异构特点（专用短程通信、蜂窝通信、毫米波通信等）;业务流量出现指数式增长,车联网业务呈现多样化特性（车协同驾驶、自动驾驶、安全告警信息投递等）。然而,作为5G垂直服务的重要领域,现有车联网研究大多仅从通信业务角度为车联网分配网络资源,没有从车联网改善交通出行的角度优化网络配置。目前的车联网架构也忽略了以交通出行为主的业务特性,因此难以应对具有交通出行需求的业务场景。在新兴的5G车联网场景中,车联网技术不单单是保证车联网业务需求,同时也要服务于交通出行的各项性能指标,例如:行车安全、交通吞吐率、车流稳定性等。梳理清楚车联网资源（通信与计算资源）对各项交通指标的作用关系、以及各个交通指标间的相互制约关系对车联网资源优化至关重要。然而,受限于车载计算能力的约束,以及云计算平台的长距离回传限制,传统云计算模式无法满足交通出行严苛的时延需求。对此,边缘计算技术将计算资源部署在最贴近交通业务产生的地方,采用多样化接入方式选择最适合的通信技术去高效完成业务的计算卸载。这种新兴的计算模式为交通出行业务的实时性传输和多样化计算服务提供了技术支撑。此外,时变的业务需求、高动态的路网环境等车联网固有问题,也为交通出行业务的资源管理带来了极大的挑战。针对上述挑战,本文提出了雾化车联网架构,能够在网络边缘侧提供更加智能化的接入决策。针对车联网与交通协同优化所面临的问题,本文致力于结合人工智能技术,通过研究异构接入选择、交通性能指标优化和基于网络切片的资源部署等方案,来满足车联网场景中的高动态交通业务要求。本文主要分为以下四个部分:1)车联网资源辅助下的交通性能分析;2)基于边缘计算的5G异构车联网接入选择研究;3)面向车队出行的动态资源管理策略;4)面向交通性能的网络切片资源管理。第一部分研究了车辆出行安全、交通吞吐率、以及车流稳定性三者同车联网资源的定量关系。根据车辆跟随模型,本文首先得出了行车安全同车联网资源的定量关系。在此基础上,揭示了V2X通信范围对交通吞吐率的影响。本文通过车流动力学模型分析了车联网资源对车流稳定性的影响。每一项交通指标均对应着一定资源需求。为了满足差异化高动态的交通业务需求,本文设计了一个雾化车联网架构,利用差异化的车队、基站等资源分层次地服务于差异化的高动态业务。第二部分为了减少卸载失败概率与车联网资源开销,同时满足业务服务时延需求,本文将异构车联网场景中计算卸载问题建模为车联网通信技术选择问题。由于不同的通信技术组合将带来差异化的传输失败概率与计算中断概率,因此,本文首先根据随机网络演算得出在不同通信方式下的卸载时延上界和对应的卸载失败概率。在此基础上,本文提出了一种基于联邦学习的智能卸载方案,用以最小化业务卸载失败（通信传输失败和计算中断）,同时降低通信与计算资源成本。仿真结果表明,与已有算法对比,本文提出的联邦学习策略能更好地降低系统的业务卸载失败与资源开销。同时,仿真得出将C-V2V通信技术应用于交通业务,相较于其他车-车通信技术可以获得最佳交通吞吐率。第三部分研究了面向车队出行的动态资源管理策略。由于车队的组建能够有效降低道路上的平均车间间距,提升交通通行效率,同时在高业务负载的车联网环境中,资源丰富的车辆可以聚合呈车队的形式,提供车辆边缘计算资源以减轻边缘基础设施的沉重业务负担。因此,车队的组建将为交通系统将带来很多益处。本文提出了低复杂度的公平候选组队策略,用以将多个车辆组建为车队。由于车队自身的不稳定特性又使得传统的业务卸载难以有效完成。为解决车队成员高动态的问题,本文基于网络演算理论确定出车队中V2V竞争信道下的卸载时延上界,将该上界作为业务卸载的参考指标。据此,本文提出了基于多臂树方案的车队边缘计算策略。与已有的算法相比,所提出的卸载策略不仅提高了车联网业务接收率,而且降低了系统开销和卸载时延,同时兼具低复杂度的特性。第四部分研究了面向交通性能的网络切片资源管理。首先,为了得到当前最佳交通性能所需的通信与计算资源,本文采用ADMM算法对多个路段进行安全距离调整,在满足行车安全的同时兼顾交通吞吐率与车流稳定性以获得最佳交通性能。为了实现切片资源与高动态业务需求的匹配,本文创新性的引入交叉熵来度量网络切片资源分布与动态业务需求之间的不匹配程度。该度量可用于基于交叉熵的MCTS-RAVE算法来指导面向网络切片的资源调度。仿真实验表明,车联雾与网络切片之间的高度连接可使车联网业务吞吐量和处理时延方面有了明显的提高。
刘贵燕[2]（2020）在《软件定义网络中的流量矩阵估计和网络流量调度》文中进行了进一步梳理流量工程是软件定义网络（Software Defined Networking,简称SDN）的一类典型应用,主要研究网络流量的测量和管理,通过设计可行的路由机制,优化网络流量调度,从而提高网络资源利用率并满足服务质量。但是随着云计算和物联网的不断扩展和应用,基于传统网络技术的流量工程具有局限性。网络规模的扩大导致难以在封闭的网络设备中部署新的协议,增加了网络运营商定制化网络服务的难度。用户对服务需求的增加以及各种新型服务的出现,也增加了运维的成本和网络功能管理的难度。SDN和网络功能虚拟化技术（Network Function Virtualizaiton,简称NFV）是数据中心网络（Data Center Networs,简称DCNs）中大数据计算、存储、分析等核心功能的高效运转的关键。与传统网络相比,SDN控制转发解耦和NFV软件硬件分离的特点在支持流量工程中具有巨大的优势。虽然SDN扩展了网络资源的范畴,但是带宽和流表成为有限的网络资源,这对精确的网络流量测量和高效灵活的调度网络资源、网络功能提出了更高的要求。随着SDN和NFV技术的发展,开展SDN的流量工程研究具有很大的现实意义与应用价值。本文结合该方向的最新研究成果,主要研究了软件定义网络中的流量矩阵估计和网络流量调度。本文的主要工作与贡献包括以下三个方面:第一,研究了大流识别的SDN流量矩阵（Traffic Matrix,简称TM）估计。主要通过将SDN提供的部分直接测量信息与推理技术相结合得到混合网络的测量方案。首先采用梯度增强机（Gradient Boosting Machine,简称GBM）从多个历史TM识别大流,找到大流采样源-目的对（Origin to Destination pair,简称OD对）,然后针对有限的流表资源,提出了一种贪婪启发式算法,解决SDN使能交换机（SDN-enabled switches）的选择问题,确保选择的大多数的大流采样OD对能被跟踪监测,其次还提出了一种基于源节点前缀树的位合并聚合方案（Source Node Prefix Tree Based Bit Merge Aggregation,简称SPTBMA）,通过设计可行的转发规则为大流采样OD对保留更多的流表空间,进而提高TM估计的精确度;最后,基于大量真实流量数据集的仿真实验,结果表明提出的方案在提高TM估计精度和克服有限流表资源方面优于现有的算法。第二,研究了分布式SDN中联合流量感知的中间件选择和路由。在静态配置机制的SDN中,流量的动态变化不仅会影响数据平面中的链路负载,还会影响控制器之间的负载。SDN和NFV可以灵活管理基于软件中间件（Middlebox）的服务,但是中间件中不同的虚拟网络功能会改变已处理流量的大小,当没有联合处理好中间件选择和流量路由时,特定的瓶颈链路会产生高度拥塞。为确保控制平面和数据平面有更好的服务质量,该问题首先表述为一个具有流量感知的联合中间件选择和路由问题,随后设计了一个两阶段算法解决这个NP-hard问题,其中第一阶段是用通配符规则重定向选定的流的路由,第二阶段是用基于凑整的方法来寻找细粒度的路由路径,最后实验结果表明,提出的方法比现有算法更接近最佳的控制器负载和链路负载均衡性能,且控制器响应时间减少了2-5倍。第三,研究了面向5G网络切片的服务功能链（Service Function Chain,简称SFC）重新配置。越来越多的用户随时随地尝试在5G网络中访问其定制的服务,SFC请求将根据不断变化的流量需求和可用资源进行动态和自适应地重新配置,但是SFC重新配置涉及流重新路由,虚拟网络功能（Virtual Network Functions,简称VNFs）实例缩放和迁移等问题,这会消耗额外的资源并导致服务中断,进而降低用户体验。为了解决这个问题,首先针对现有资源和扩展资源两种应用场景构建了最大接受比率最小重新配置开销的优化问题,现有资源下的目标是以最小重构开销执行重新配置,而扩展资源下的目标是接受具有正收益的SFC请求来获取利益,随后,设计了一个低复杂度的启发式算法解决这个NP-hard问题,最后,实验结果表明,该算法可以提高请求的接受比率和降低重配置开销。
廖宝玉[3]（2020）在《考虑恶化或学习效应的分组批调度方法研究》文中提出随着新一代信息技术与制造业不断融合,企业制造模式和生产组织方式发生了深刻的变革,制造业生产效率得到显着提升。传统制造业的大批量、少品种的生产制造模式已难以满足日益增长的个性化消费需求。近年来,越来越多的企业纷纷投资和引入基于分组制造和批加工模式的智能调度系统,并采用更加柔性的动态资源模型与方法进行精准排产,从而更好地适应多品种、小批量和个性化定制的生产特点。其中,在动态资源建模中,生产资源的恶化或学习效应被认为是最显着的动态模型特征之一,也是影响智能制造系统稳定性的重要因素。考虑生产资源恶化或学习效应的分组批调度问题已逐渐成为近年来学术研究领域的热点方向。本文以汽车零部件及半导体等离散制造业实际生产过程为背景,面向新一代智能制造系统,基于分组批加工模式,考虑制造资源的恶化或学习效应,系统地分析了企业在单客户和多客户情形下的多种分组批调度问题。根据实际生产特点,在以单一客户订单为主要目标的生产实践中,企业生产线一般较为成熟,生产机器的恶化效应表现明显;而在以多客户订单为目标的情况下,企业往往需要临时增加新的产线以适应动态变化的订单需求,其中成熟产线的机器恶化效应表现明显,而新增产线的工人学习效应则更加突出。基于此,本文重点研究了单客户情形下考虑恶化效应、单客户外包情形下考虑恶化效应、多客户情形下考虑恶化效应和多客户情形下考虑学习效应四个方面的分组批调度问题。本文致力于对这些源于实际的复杂调度问题进行深入的分析,并抽象出高效可用的调度模型,设计出有效的启发式调度规则与智能化调度算法。本文主要研究成果和创新点如下:（1）针对单客户情形下考虑恶化效应的分组批调度问题,构建了单机和多机两种情况下的最优调度规则。其中,对于单机问题,推导出了高效的单机调度算法;对于多机调度问题,利用所提出的最优结构属性和批处理规则,设计了一种混合AIS-VNS算法,该算法结合了人工免疫系统算法（AIS）和变邻域搜索算法（VNS）的各自优点。实验结果表明,该算法在效率和解决方案质量方面相比传统算法都表现出了很好的优势。（2）针对单客户外包情形下考虑恶化效应的分组批调度问题,讨论了特定情况下的该类问题的结构模型,并基于此模型提出了一种有效的混合VNSNKEA算法来解决此类型问题。该算法充分借鉴了基于邻域的进化算法（NKEA）和变邻域搜索算法（VNS）的各自特点,能够高效地求解此类型问题。实验结果表明,混合VNS-NKEA算法可以有效地解决所研究的问题,并表现出更高的求解性能。（3）针对多客户情形下考虑恶化效应的分组批调度问题,构建了基于该类型问题关键结构性质的优化模型,并基于这些结构模型设计了嵌入相关调度规则的决策流程图。同时,进一步提出了一种有效的改进差分进化（DE）搜索算法。该算法借鉴了变邻域搜索算法（VNS）的局部操作策略,可以有效地解决连续批处理机上的该类型调度问题。实验结果表明,改进的DE算法（IDE）相较于其他同类算法,在性能上更加有效和稳定。（4）针对多客户情形下考虑学习效应的分组批调度问题,构建了针对不同工件组的学习效应模型,并提出了针对单机和多机两种情形的批调度规则。其中,对于单机问题,设计了相应的最优化调度算法;对于多机调度问题,设计了一种有效的基于“少即是多（Less is more）”的迭代参考贪婪算法（LIMA-IRG）。该算法通过剔除传统复杂算法效率较低的步骤,提高了求解问题的效率。实验结果表明,相比传统算法,LIMA-IRG算法具有更高的求解效率。最后,基于所研究的核心问题与基本框架,本文还对同时考虑恶化效应和学习效应、考虑更多生产特征及考虑多目标优化等复杂调度问题进行了下一步研究展望。
董奇[4]（2020）在《遗憾最小化查询近似算法研究》文中研究表明从大量数据中查找用户所需信息来协助用户制定多目标决策是数据库领域中一个重要的研究方向。Top-k查询和Skyline查询被广泛用来解决此类问题,但是它们有着本质的缺陷。遗憾最小化查询也能够很好地解决此类问题,它综合了Top-k查询和Skyline查询的优点,但是现有的遗憾最小化查询算法效率不高或者缺乏理论保证。论文针对已有算法存在的缺陷,设计出具有理论保证的高效的近似算法。论文主要工作和创新点如下:（1）研究基于采样技术的高效的遗憾最小化查询算法。针对已有的遗憾最小化查询算法效率较低或在某些场景下无法工作等缺陷,论文首先将遗憾率函数转化成开心度函数,并重新设计经典的贪婪算法,详述算法线性规划的计算方式,并论证改进后的算法的选点正确性。为了进一步提高算法的运行效率,利用随机采样技术设计出更高效的算法。大量实验表明基于采样的算法的运行效率较高的同时最大遗憾率也较小,并且算法在不同场景下都能够很好地运行。（2）研究利用子模理论证明算法的近似率。论文首先介绍子模函数的定义,然后论述开心度函数和最小开心度函数的性质,以及它们与子模函数之间的联系。通过引入子模率和曲率的概念,结合基于开心度的贪婪算法,证明算法的近似率,补足经典贪婪算法没有理论保证的缺陷。此外,基于采样的算法的近似率也通过子模率和随机采样理论给出。（3）研究基于单调性和采样的高效的k-遗憾最小化查询算法。论文首先说明了遗憾率函数在某些情况下可能不太适用,因此将研究拓展到k-遗憾率函数上,相关的查询也变为k-遗憾最小化查询。之后论述此类问题是NP难题,并针对已有算法的低效性,提出高效的贪婪算法,同时利用函数单调性对算法进行加速。此外,将随机采样技术加入到算法中,提出基于采样的贪婪算法,并分析与先前贪婪算法的结果集之间的联系。实验表明论文中设计的算法比已有的算法更加具有优势。
阮扬帆[5]（2020）在《5G移动通信系统信道估计与均衡算法的研究》文中提出随着人类生活质量的普遍提高,对未来科学技术的发展有了进一步的展望,这其中也包括移动通信技术。UFMC和FBMC作为5G通信系统的候选,有着节省频谱利用率和抑制带外泄露的优点。同时,传统的信道估计方法需要大量的导频信息且重构精度不高,为了解决这一问题,压缩感知算法应运而生并且广泛使用在各个领域。本文主要研究了压缩感知理论在UFMC和FBMC系统信道估计中的应用,并结合信道均衡算法,最后得到补偿后的信号。使用本文提出的信道估计算法得到的补偿信号与原始信号的误比特率相比于传统算法有所降低。本文在第三章首先介绍了SAMP算法,发现SAMP算法最终选取出来的原子集矩阵与残差信号相关性不高,于是本文提出了基于SAMP算法的RSAMP算法。该算法是将正则化的思想引入SAMP算法中,使得在每次迭代原子时多一层筛选,筛选的标准为再一次选取的原子集中的原子与残差的最大值不能超过最小值的两倍且保证能量最大。这样的筛选可以进一步保证最后更新得到的原子集是与待估计参数最为相关的,从而提高重构精度。本文在第四章中首先推导出完备的BCS算法,在推导过程中发现传统的BCS算法在求解过度参数时迭代方式可以改进,而过渡参数的恢复直接影响到待估计参数的重构。于是本文借鉴贪婪算法中预留候选原子和变步长正则化的思路,提出了两种改进的BCS算法。BCS算法以稀疏度K为结束条件,迭代后非零分量的位置即为待估参数的非零位置,这样的做法不够严谨。在DBCS算法中,预留出K个位置作为备选,在迭代结束后可以从2K个位置中选取出K个位置构成过渡参数,这样的多次筛选可以提高重构精度;BCS算法每次只选取一个位置置1,而本文提出的RBCS算法每次迭代时使M个非零位置置1,然后从M个位置中选取出L个分量,每次迭代结束后更新M,这样可以保证选取的位置更加接近。最后通过软件平台仿真得出改进后的BCS算法总体上有1至2dB的性能提高。
汪俐敏[6]（2019）在《平行机上半在线排序模型的算法性能分析》文中研究说明本篇论文主要是研究半在线模型下的算法设计以及算法性能比分析。论文主要分为四章内容,第一章为绪论部分,首先介绍了组合优化问题的定义以及其研究意义,然后就组合优化问题中典型的排序问题进行背景、分类、研究现状等多方面叙述,最后引入近似算法的概念和基本思想并介绍Pm和本文我们所构造的S形算法。第四章是对整篇文章做了一个总结,并提出了今后研究工作可能的方向。主体内容将分别在第二章和第三章中展开详细证明。第二章:我们构造了S形算法,证明了当m=2时,对于任意的工件序列L={J1,J2,…,Jn},加工时间非递增（p1 ≥ p2≥…≥ pn）,工件具有相似的加工时长pj ∈[1,r]（1 ≤ r ≤ 2）时,其最坏性能比为:而在Wei-Ping Liu,Jeffrey B.Sidney,Andre van Vliet 1996年（[20]）给出的算法P（2）中,其最坏性能比为CmaxP2/CmaxOPT(L≤4/3,后证得即使加入工件具有相似的加工时长pj∈[1,r]（r≥1）这一约束后该算法的最坏性能比仍不变,始终有supLCmaxP2/CmaxOPT（L）=4/3但是在S形算法中我们通过限定工件加工时长得到了更好的结果。第三章:本章证明了对于任意的工件序列L={J1,J2,...,Jn},工件满足加工时长非递增,到达时间不都为零且非递减（即p1 ≥ p2 ≥...≥pn,r1≤r2≤...≤rn）时,Pm算法的最坏性能比为本章主要是对文献[11]做了相关的修正,并且优化了该算法的最坏性比能,从而得到了更加精确的结果。
朱文龙[7]（2019）在《社交网络中的影响力阻断最大化研究》文中认为随着互联网技术的飞速发展,以Facebook、Twitter、新浪微博、腾讯微博、豆瓣等为代表的社交网络不断涌现,利用社交网络进行信息交流已成为人们日常生活中的一部分。随着社交网络应用的日益普及,学者们从不同的角度对社交网络相关问题进行了研究,影响力最大化是其中非常热门的研究领域之一。其目标是选择k个用户（也称为种子集）,通过社交网络中朋友间的口碑来进行信息的传播,使得源信息能最大限度的在网络中传播。影响力阻断最大化是影响力最大化的扩展与延伸,与传统的影响力最大化问题不同,影响力阻断最大化问题的目标是选择k个用户,通过社交网络中朋友间的口碑来进行信息的传播,使得源信息的传播能够最大限度的阻断竞争对手信息的传播。影响力阻断最大化在谣言抑制、口碑推荐等领域有非常重要的应用,特别是对于谣言抑制问题,由于社交网络的虚拟性和开放性,社交网络极易成为谣言传播的温床。当谣言发生时,通过寻找影响力阻断最大的用户,可以有效抑制谣言的传播,减少谣言带来的损失。本文对社交网络中的影响力阻断最大化进行了深入的研究,主要包括以下几个方面。首先,现有的影响力阻断最大化算法并没有考虑到影响力阻断的区域性问题,无法根据区域进行最优种子的选取。针对此问题,本文首次提出了区域影响力阻断最大化（Location-aware Influence Blocking Maximization,LIBM）问题。证明了该问题在同质竞争独立级联传播模型下的NP难特性和影响力函数的单调子模特性。为解决传统的贪婪算法效率低下的问题,提出了一种基于整体的区域影响力阻断最大化算法LIBM-H。该算法采用四叉树保存节点位置信息,采用最大影响树模拟影响力传播,采用动态规划算法计算备选节点在整个区域中的阻断影响力,采用贪婪策略选择阻断影响力最大的节点作为种子节点。通过在真实的位置社交网络数据集上的实验表明,该算法能够根据给定的区域选择最优种子,算法的阻断性能与理论最优的贪婪算法接近但运行速度提高了4个数量级,同时该算法的阻断性能明显优于其他基线算法。其次,针对影响力阻断的区域性问题,虽然LIBM-H算法可以得到最优种子,但由于其需要实时计算每个备选节点在整个区域中的阻断影响力,这是非常耗时的。因此,本文又提出了一种基于元组的区域影响力阻断最大化算法LIBM-C。该算法并不直接计算备选节点在整个区域中的阻断影响力,而是在预处理阶段根据四叉树建立元组索引和节点索引来保存节点在四叉树单元中的阻断影响力,在在线处理阶段利用预处理阶段生成的元组索引和节点索引,采用基于上界的估计算法和最大堆来选择种子节点,忽略阻断影响力较小的节点。实验结果表明LIBM-C算法的平均运行时间比LIBM-H减少了2.5倍且阻断性能接近LIBM-H算法。然后,现有的影响力阻断最大化算法并没有考虑到种子选择的区域性问题,无法根据给定的查询区域和阻断区域进行最优种子选取。针对此问题,本文首次提出了影响力阻断最大化中的区域种子选择（Location-based Seeds Selection for Influence Blocking Maximization,LSSIBM）问题。证明了该问题在同质竞争独立级联传播模型下的NP难特性和影响力函数的单调子模特性。为解决传统贪婪算法效率低下的问题,提出了基于影响集的区域影响力阻断最大化算法IS-LSS和其改进算法IS-LSS+。这两种算法都基于节点的影响集计算其区域阻断影响力,基于最大堆选择最优种子。IS-LSS+算法相比于IS-LSS算法的优化在于其采用了基于上界的估计算法进一步降低了处理时间。实验结果表明两种算法能够根据给定的查询区域和阻断区域选择最优种子,阻断性能接近贪婪算法但运行效率提高了4个数量级,同时阻断性能明显优于其他基线算法。另外,IS-LSS+算法相比于IS-LSS算法对于不同规模区域请求的处理时间更少且更具鲁棒性。最后,现有的影响力阻断最大化算法并没有考虑到种子选择的主题性问题,无法根据给定的主题和区域进行最优种子选取。针对此问题,本文首次提出了区域主题影响力阻断最大化（Location-aware Targeted Influence Blocking Maximization,LTIBM）问题。证明了该问题在同质竞争独立级联传播模型下的NP难特性和影响力函数的单调子模特性。进一步的,本文提出了LTIBM-H算法解决该问题。该算法通过QT-tree保存和获取节点位置及主题信息,通过动态规划算法计算备选节点对区域中所有与给定主题有偏好节点的区域主题阻断影响力,并贪婪的选择区域主题阻断影响力最大的节点作为种子节点。实验结果表明本文提出的算法能够根据给定的主题和位置信息选择最优的种子节点,阻断性能明显优于其他基线算法。
聂嘉明[8]（2017）在《线性约束下的组合优化问题研究》文中认为组合优化是运筹学的一个重要研究分支,包含很多经典问题,如排序问题、网络流问题、背包问题、装箱问题等。每个组合优化问题都有各自的参数,如排序问题中工件的加工时间、背包问题中物品的权重和价值、装箱问题中物品的大小等。在传统的组合优化研究中,这些参数一般独立于问题的决策,由外部环境预先给定。在实际的应用中,决定这些参数往往也是一个需要优化的问题,例如参数需要满足一些资源的约束或满足一定的供求关系。本文研究一些线性约束下的经典组合优化问题,即组合优化问题的参数需要满足一些线性约束,因此也是决策的一部分。本文研究的问题包括线性约束下的排序问题、线性约束下的背包问题、线性约束下的装箱问题等。这些问题具有全新的结构,在实际生活中有广泛的应用场景,蕴含着丰富的研究内容,但文献中却很少有相关的研究。本文首先给出了这些线性约束下的组合优化问题的具体模型,提供它们的研究动机和实际背景。很多线性约束下的组合优化问题,都能自然地表示成一些复杂的数学规划问题,如混合双线性规划问题。一般而言,这些数学规划问题都是十分困难的,不容易直接应用它们的结论去求解本文研究的问题。利用线性规划和组合优化的技术,本文分析这些问题的计算复杂性和提出相应的算法。本文通过研究发现,有一些原来困难的组合优化问题,例如平行机排序问题、装箱问题等,其线性约束下的问题在某些情况下,如约束的个数并不多时是多项式可解的;也有一些原来可解的组合优化问题,例如不含负权的最短路问题等,其线性约束下的问题一般情况下是困难和难以近似的。本文主要的创新点总结如下:1.根据实际应用需要,提出了线性约束下的组合优化问题的概念,并建立了一系列线性约束下的经典组合优化问题。2.探索线性约束下的组合优化问题的结构与性质,并建立它们与线性规划、经典组合优化问题的联系。3.分析这些问题在不同情形下的计算复杂性,并设计相应的多项式时间算法或近似算法。
代文强,李晓荣,冯毅[9]（2016）在《最大和搜索结果多样性问题及其贪婪算法分析》文中进行了进一步梳理研究互联网搜索结果的最优多样性问题.给定用户搜索关键词较少,以及关键词本身的多义性,同时由于搜索系统一次呈现结果存在数量上的限制,系统常不能准确定位用户的真实搜索需求.为了最大化覆盖用户的搜索需求,搜索系统显示的结果不仅需要最大化同关键词的相关性,而且需要最大化结果之间的差异性.考虑了最大和搜索结果多样性问题,给出了贪婪算法,并针对实际中的差异性度量常常不满足三角不等式的情况下,分析证明了该贪婪算法具有的近似性能比.结果表明贪婪算法具有很好的理论近似性能.
任庆娟,许保光[10]（2012）在《有元素类型约束的k-划分问题研究》文中研究指明研究有元素类型约束且每个元素权重为正数的κ-集合划分问题,元素类型约束指κ-划分后每个集合所包含的元素的类型均不同,该问题是对κ-划分问题（κ-partitioning problem）的一个拓展,在一人可拥有多技能执照的行业有广泛的应用背景,提出基于LPT算法思想的贪婪算法,并得出以下结论:κ≤2,该算法给出最优解:κ>2,最坏情况下的性能比为2-m-1,这里m指待分配集合的数量。
二、贪婪算法与最坏性能比分析（论文开题报告）
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
本文主要提出一款精简64位RISC处理器存储管理单元结构并详细分析其设计过程。在该MMU结构中,TLB采用叁个分离的TLB,TLB采用基于内容查找的相联存储器并行查找,支持粗粒度为64KB和细粒度为4KB两种页面大小,采用多级分层页表结构映射地址空间,并详细论述了四级页表转换过程,TLB结构组织等。该MMU结构将作为该处理器存储系统实现的一个重要组成部分。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
三、贪婪算法与最坏性能比分析（论文提纲范文）
（1）面向交通出行的车联网资源调度策略研究（论文提纲范文）
| 摘要 |
| ABSTRACT |
| 缩略词表 |
| 第一章 绪论 |
| 1.1 引言 |
| 1.2 技术背景及研究现状 |
| 1.2.1 车联网技术演进概述 |
| 1.2.2 5G车联网关键技术 |
| 1.2.3 边缘计算技术概述 |
| 1.2.4 面向交通的车联网研究现状 |
| 1.3 现有研究的不足 |
| 1.4 本文的主要研究内容与创新 |
| 1.4.1 主要研究内容 |
| 1.4.2 论文的贡献与创新点 |
| 1.5 本论文的结构和内容安排 |
| 第二章 车联网资源辅助下的交通性能分析 |
| 2.1 引言 |
| 2.2 车联网资源辅助的交通安全分析 |
| 2.2.1 车辆跟随模型 |
| 2.2.1.1 安全距离 |
| 2.2.2 面向交通流的元胞自动机 |
| 2.3 交通吞吐率分析 |
| 2.3.1 V2V传输覆盖范围 |
| 2.3.2 V2V辅助的交通吞吐率 |
| 2.3.3 V2X辅助的交通吞吐率 |
| 2.3.4 交通吞吐率仿真验证 |
| 2.4 车流稳定性分析 |
| 2.4.1 车流稳定性及其充分条件 |
| 2.4.2 车流稳定性仿真验证 |
| 2.5 雾化车联网架构 |
| 2.5.1 车联网资源对交通业务影响 |
| 2.5.2 系统模型 |
| 2.6 本章小结 |
| 第三章 基于边缘计算的5G异构车联网接入选择研究 |
| 3.1 引言 |
| 3.2 车联网异构通信技术性能分析 |
| 3.2.1 随机网络演算理论 |
| 3.2.2 DSRC V2V性能分析 |
| 3.2.3 C-V2V性能分析 |
| 3.2.4 mmWave V2V性能分析 |
| 3.2.5 C-V2I性能分析 |
| 3.2.6 本地处理性能分析 |
| 3.3 面向异构车联网通信与计算协同优化 |
| 3.3.1 优化模型 |
| 3.3.2 联邦Q学习 |
| 3.3.3 松弛法优化 |
| 3.4 性能分析 |
| 3.4.1 不同卸载算法性能对比 |
| 3.4.2 不同车联网通信技术的接入性能 |
| 3.4.3 不同通信技术对交通吞吐率影响 |
| 3.5 本章小结 |
| 第四章 面向车队出行的动态资源管理策略 |
| 4.1 引言 |
| 4.2 车队的形成 |
| 4.2.1 面向车辆边缘计算的车队组建模型 |
| 4.2.2 Lagrangian松弛法 |
| 4.2.3 公平候选组队策略 |
| 4.3 面向车队的资源调度策略 |
| 4.3.1 基于休眠多臂机算法的车队资源分配策略 |
| 4.4 性能分析 |
| 4.4.1 车队生成算法性能对比 |
| 4.4.2 面向车队的车辆边缘计算资源分配性能对比 |
| 4.5 本章小结 |
| 第五章 面向交通性能的网络切片资源管理 |
| 5.1 引言 |
| 5.2 面向交通性能的车联网资源需求分析 |
| 5.3 基于C-V2X网络的智能切片调度策略 |
| 5.3.1 系统模型 |
| 5.3.2 Markov决策过程建模 |
| 5.3.3 面向切片资源匹配的蒙特卡洛树搜索算法 |
| 5.3.4 基于交叉熵的MCTS-RAVE收敛性证明 |
| 5.4 性能分析 |
| 5.4.1 不同交通性能权重下的安全距离 |
| 5.4.2 网络切片调度算法对比 |
| 5.5 本章小结 |
| 第六章 总结与展望 |
| 6.1 本文总结 |
| 6.2 下一步工作展望 |
| 致谢 |
| 参考文献 |
| 攻读博士学位期间取得的研究成果 |
（2）软件定义网络中的流量矩阵估计和网络流量调度（论文提纲范文）
| 摘要 |
| Abstract |
| 缩略词表 |
| 第一章 绪论 |
| 1.1 研究背景及意义 |
| 1.2 面临的挑战 |
| 1.3 国内外研究现状 |
| 1.3.1 流量矩阵估计 |
| 1.3.2 多控制器下的流量调度 |
| 1.3.3 5G网络切片的重新配置 |
| 1.4 本文的工作 |
| 1.4.1 研究思路 |
| 1.4.2 具体内容 |
| 1.4.3 本文的创新点 |
| 第二章 SDN和 NFV技术及相关理论 |
| 2.1 SDN技术 |
| 2.1.1 SDN架构特点 |
| 2.1.2 OpenFlow交换机及协议 |
| 2.1.3 流量信息收集方式 |
| 2.2 NFV技术 |
| 2.2.1 NFV架构特点 |
| 2.2.2 中间件 |
| 2.2.3 服务功能链 |
| 2.3 SDN和NFV的应用 |
| 2.3.1 SDN与 NFV的技术分析 |
| 2.3.2 网络切片 |
| 2.4 本章小结 |
| 第三章 大流识别的SDN流量矩阵估计 |
| 3.1 引言 |
| 3.2 SDN的流量矩阵估计 |
| 3.2.1 问题描述 |
| 3.2.2 算法实现 |
| 3.3 基于GBM的大流识别 |
| 3.3.1 大流的分析 |
| 3.3.2 大流的识别 |
| 3.4 交换机选择和流表聚合 |
| 3.4.1 SDN-enabled交换机选择 |
| 3.4.2 SPTBMA |
| 3.4.3 SPTBMA示例 |
| 3.5 仿真性能分析 |
| 3.5.1 实验设置 |
| 3.5.2 粗粒度下的实验结果 |
| 3.5.3 细粒度下的实验结果 |
| 3.5.4 算法运行时间 |
| 3.6 本章小结 |
| 第四章 分布式SDN中联合流量感知的中间件选择和路由 |
| 4.1 引言 |
| 4.2 系统模型和问题描述 |
| 4.2.1 系统模型 |
| 4.2.2 问题描述 |
| 4.2.3 NP-hard证明 |
| 4.3 算法设计 |
| 4.3.1 主控制器流重定向传输 |
| 4.3.2 本地决策控制器流定向传输 |
| 4.3.3 相关讨论 |
| 4.4 仿真性能分析 |
| 4.4.1 实验设置 |
| 4.4.2 实验结果 |
| 4.5 本章小结 |
| 第五章 面向5G网络切片的SFC重新配置 |
| 5.1 引言 |
| 5.2 系统模型 |
| 5.2.1 网络模型 |
| 5.2.2 问题描述 |
| 5.2.3 重新配置开销 |
| 5.3 问题构建 |
| 5.3.1 SFC_RPER |
| 5.3.2 SFC_RPSR |
| 5.3.3 问题分析 |
| 5.4 算法设计 |
| 5.4.1 整体设计 |
| 5.4.2 路径寻找算法 |
| 5.4.3 SFC重新配置算法 |
| 5.4.4 算法复杂度分析 |
| 5.5 仿真性能分析 |
| 5.5.1 实验设置 |
| 5.5.2 实验结果 |
| 5.6 本章小结 |
| 第六章 总结与展望 |
| 6.1 工作总结 |
| 6.2 研究展望 |
| 参考文献 |
| 致谢 |
| 攻读博士期间完成和发表的论文 |
| 攻读博士期间主持和参与的科研项目 |
| 攻读博士期间获得的奖励 |
（3）考虑恶化或学习效应的分组批调度方法研究（论文提纲范文）
| 致谢 |
| 摘要 |
| abstract |
| 第一章 绪论 |
| 1.1 研究背景 |
| 1.2 研究目的和意义 |
| 1.3 研究内容和结构安排 |
| 1.3.1 论文研究内容 |
| 1.3.2 论文结构安排 |
| 第二章 文献综述 |
| 2.1 分组制造模式下的调度问题 |
| 2.1.1 单机情形下的分组调度问题 |
| 2.1.2 多机情形下的分组调度问题 |
| 2.1.3 流水线情形下的分组调度问题 |
| 2.2 基于批加工模式的调度问题 |
| 2.2.1 单机情形下的批调度问题 |
| 2.2.2 多机情形下的批调度问题 |
| 2.2.3 流水线情形下的批调度问题 |
| 2.3 考虑恶化或学习效应的调度问题 |
| 2.3.1 单机情形下考虑恶化或学习效应的调度问题 |
| 2.3.2 多机情形下考虑恶化或学习效应的调度问题 |
| 2.3.3 流水线情形下考虑恶化或学习效应的调度问题 |
| 2.4 本章小结 |
| 第三章 单客户情形下考虑恶化效应的分组批调度 |
| 3.1 引言 |
| 3.2 问题描述 |
| 3.3 单机情形下的调度规则 |
| 3.4 多机情形下的混合AIS-VNS算法 |
| 3.4.1 编码与解码策略 |
| 3.4.2 VNS算法描述 |
| 3.4.3 AIS-VNS的算法框架 |
| 3.4.4 计算实验与讨论 |
| 3.5 本章小结 |
| 第四章 单客户外包情形下考虑恶化效应的分组批调度 |
| 4.1 引言 |
| 4.2 问题描述 |
| 4.3 单机情形下的结构性质 |
| 4.4 多机情形下的混合VNS-NKEA算法 |
| 4.4.1 编码与解码策略 |
| 4.4.2 邻域结构描述 |
| 4.4.3 增强局部搜索策略 |
| 4.4.4 VNS-NKEA的算法框架 |
| 4.4.5 计算实验与讨论 |
| 4.5 本章小结 |
| 第五章 多客户情形下考虑恶化效应的分组批调度 |
| 5.1 引言 |
| 5.2 问题描述 |
| 5.3 单机情形下的调度策略 |
| 5.4 多机情形下的IDE算法 |
| 5.4.1 编码及修正策略 |
| 5.4.2 邻域结构设计 |
| 5.4.3 基于DE的邻域搜索 |
| 5.4.4 改进DE算法框架 |
| 5.4.5 计算实验与讨论 |
| 5.5 本章小结 |
| 第六章 多客户情形下考虑学习效应的分组批调度 |
| 6.1 引言 |
| 6.2 问题描述 |
| 6.3 单机情形下的调度算法 |
| 6.4 多机情形下的LIMA-IRG算法 |
| 6.4.1 LIMA-IRG算法的过程 |
| 6.4.2 LIMA-IRG算法的应用步骤 |
| 6.4.3 计算实验与讨论 |
| 6.5 本章小结 |
| 第七章 总结与展望 |
| 7.1 全文总结 |
| 7.2 研究展望 |
| 参考文献 |
| 攻读博士学位期间的学术活动及成果情况 |
（4）遗憾最小化查询近似算法研究（论文提纲范文）
| 摘要 |
| abstract |
| 注释表 |
| 缩略词 |
| 第一章 绪论 |
| 1.1 研究背景 |
| 1.2 选题意义 |
| 1.3 主要研究内容 |
| 1.4 论文组织结构 |
| 第二章 代表点查询相关工作 |
| 2.1 Top-k查询和Skyline查询简述 |
| 2.1.1 Top-k查询 |
| 2.1.2 Skyline查询 |
| 2.2 遗憾最小化查询 |
| 2.2.1 基于最大遗憾率的遗憾最小化查询 |
| 2.2.2 基于几何方法的遗憾最小化查询 |
| 2.2.3 基于ε-核的遗憾最小化查询 |
| 2.2.4 基于命中集的遗憾最小化查询 |
| 2.2.5 基于矩阵min-max方法的遗憾最小化查询 |
| 2.2.6 具有非受限界的遗憾最小化查询 |
| 2.2.7 遗憾最小化查询拓展研究 |
| 2.3 子模相关理论 |
| 2.5 本章小结 |
| 第三章 基于采样技术的遗憾最小化查询算法 |
| 3.1 遗憾最小化查询问题 |
| 3.1.1 问题描述 |
| 3.1.2 问题定义 |
| 3.2 基于预选点的PRESGREED算法 |
| 3.2.1 GREEDY算法 |
| 3.2.2 PRESGREED算法 |
| 3.2.3 线性规划计算方式 |
| 3.2.4 选点正确性论证 |
| 3.2.5 算法分析 |
| 3.3 基于采样的STOCPRESGREED算法 |
| 3.3.1 STOCPRESGREED算法 |
| 3.3.2 算法分析 |
| 3.4 实验评测 |
| 3.4.1 实验设置 |
| 3.4.2 实验结果及分析 |
| 3.5 本章小结 |
| 第四章 基于采样技术的遗憾最小化查询算法近似率 |
| 4.1 函数性质 |
| 4.1.1 子模函数定义 |
| 4.1.2 开心度函数和最小开心度函数特性 |
| 4.2 子模率和曲率 |
| 4.2.1 子模率概念 |
| 4.2.2 曲率概念 |
| 4.3 PRESGREED算法近似率 |
| 4.4 STOCPRESGREED算法近似率 |
| 4.5 本章小结 |
| 第五章 基于单调性和采样的k-遗憾最小化查询算法 |
| 5.1 k-遗憾最小化查询问题 |
| 5.1.1 问题描述 |
| 5.1.2 问题定义 |
| 5.2 问题特性 |
| 5.3 基于单调性加速的ACCGREED算法 |
| 5.3.1 ACCGREED算法 |
| 5.3.2 选点正确性论证 |
| 5.3.3 单调性加速策略 |
| 5.4 基于采样的SAMPGREED算法 |
| 5.4.1 SAMPGREED算法 |
| 5.4.2 SAMPGREED算法结果集分析 |
| 5.5 实验评测 |
| 5.5.1 实验设置 |
| 5.5.2 实验结果及分析 |
| 5.6 本章小结 |
| 第六章 总结与展望 |
| 6.1 论文工作总结 |
| 6.2 研究工作展望 |
| 参考文献 |
| 致谢 |
| 在学期间的研究成果及发表的学术论文 |
（5）5G移动通信系统信道估计与均衡算法的研究（论文提纲范文）
| 摘要 |
| abstract |
| 缩略词表 |
| 第一章 绪论 |
| 1.1 研究工作的背景与意义 |
| 1.2 国内外研究历史与现状 |
| 1.2.1 UFMC研究历史与现状 |
| 1.2.2 FBMC研究历史与现状 |
| 1.2.3 信道估计的研究历史与现状 |
| 1.2.4 信道均衡的研究历史与现状 |
| 1.3 本论文的结构安排 |
| 第二章 5G多载波系统与信道估计理论 |
| 2.1 无线信道简介 |
| 2.1.1 无线信道特性 |
| 2.1.2 无线信道模型 |
| 2.2 5G多载波系统简介 |
| 2.2.1 UFMC系统简介 |
| 2.2.2 FBMC系统简介 |
| 2.3 基于导频的信道估计算法 |
| 2.4 本章小结 |
| 第三章 基于压缩感知的信道估计算法研究 |
| 3.1 压缩感知理论 |
| 3.2 重构算法 |
| 3.3 贪婪算法 |
| 3.3.1 OMP算法 |
| 3.3.2 ROMP算法 |
| 3.3.3 CoSaMP算法 |
| 3.3.4 SAMP算法 |
| 3.4 基于SAMP改进的RSAMP算法 |
| 3.5 UFMC/FBMC系统中改进算法与传统算法仿真和分析 |
| 3.5.1 UFMC系统中改进SAMP算法和贪婪算法性能比较 |
| 3.5.2 FBMC系统中改进SAMP算法和贪婪算法性能比较 |
| 3.6 本章小结 |
| 第四章 贝叶斯压缩感知的信道估计与均衡实现 |
| 4.1 贝叶斯压缩感知 |
| 4.1.1 贝叶斯理论 |
| 4.1.2 BCS算法推导 |
| 4.2 改进的BCS算法 |
| 4.2.1 DBCS算法 |
| 4.2.2 RBCS算法 |
| 4.3 UFMC系统中改进算法与传统算法仿真与分析 |
| 4.3.1 UFMC系统中BCS算法和贪婪算法性能比较 |
| 4.3.2 UFMC系统中BCS算法和改进BCS算法性能比较 |
| 4.4 FBMC系统中改进算法与传统算法仿真与分析 |
| 4.4.1 FBMC系统中BCS算法与贪婪算法性能比较 |
| 4.4.2 FBMC系统中BCS算法与改进BCS算法性能比较 |
| 4.5 UFMC/FBMC信道均衡实现 |
| 4.5.1 ZF均衡算法 |
| 4.5.2 MMSE均衡算法 |
| 4.5.3 UFMC/FBMC系统信道均衡仿真和分析 |
| 4.6 本章总结 |
| 第五章 全文总结与展望 |
| 5.1 论文总结 |
| 5.2 后续工作展开 |
| 致谢 |
| 参考文献 |
| 攻读硕士学位期间取得的成果 |
（6）平行机上半在线排序模型的算法性能分析（论文提纲范文）
| 中文摘要 |
| 英文摘要 |
| 第一章 绪论 |
| 1.1 组合优化问题 |
| 1.2 排序问题及其分类 |
| 1.3 近似算法 |
| 1.4 P_m算法和S形算法 |
| 第二章 两台机上工件加工时长有约束的性能比分析 |
| 2.1 引言 |
| 2.2 S形算法介绍及符号引入 |
| 2.3 定理及其证明 |
| 第三章 工件到达时间非递减的半在线P_m算法的性能比分析 |
| 3.1 引言 |
| 3.2 P_m算法介绍及符号引入 |
| 3.3 定理及其证明 |
| 第四章 总结 |
| 参考文献 |
| 致谢 |
（7）社交网络中的影响力阻断最大化研究（论文提纲范文）
| 摘要 |
| abstract |
| 第1章 绪论 |
| 1.1 研究背景及意义 |
| 1.2 国内外研究现状 |
| 1.2.1 影响力传播模型 |
| 1.2.2 影响力最大化算法 |
| 1.2.3 影响力最大化应用 |
| 1.3 论文的研究框架与内容 |
| 1.3.1 研究框架 |
| 1.3.2 研究内容 |
| 1.4 论文的组织结构 |
| 第2章 基于整体的区域影响力阻断最大化算法 |
| 2.1 引言 |
| 2.2 相关理论与模型 |
| 2.2.1 影响力传播模型 |
| 2.2.2 影响力最大化和影响力阻断最大化 |
| 2.3 区域影响力阻断最大化和贪婪算法 |
| 2.4 基于整体的区域影响力阻断最大化算法LIBM-H |
| 2.4.1 基于Quadtree的节点位置信息存取 |
| 2.4.2 基于动态规划算法的节点负激活概率计算 |
| 2.4.3 基于整体的节点阻断影响力估计 |
| 2.4.4 LIBM-H算法 |
| 2.5 实验及分析 |
| 2.5.1 实验设置 |
| 2.5.2 与贪婪算法的比较 |
| 2.5.3 正种子数对性能的影响 |
| 2.5.4 区域规模对性能的影响 |
| 2.6 本章小结 |
| 第3章 基于元组的区域影响力阻断最大化算法 |
| 3.1 引言 |
| 3.2 元组索引和节点索引 |
| 3.2.1 元组索引 |
| 3.2.2 节点索引 |
| 3.3 基于元组的节点阻断影响力估计 |
| 3.4 基于阻断影响力上界的种子选择 |
| 3.5 基于元组的区域影响力阻断最大化算法LIBM-C |
| 3.6 实验及分析 |
| 3.6.1 实验设置 |
| 3.6.2 正种子数对性能的影响 |
| 3.6.3 区域规模对性能的影响 |
| 3.6.4 随机负种子对性能的影响 |
| 3.6.5 参数θ对性能的影响 |
| 3.7 本章小结 |
| 第4章 基于影响集的区域影响力阻断最大化算法 |
| 4.1 引言 |
| 4.2 问题定义和贪婪算法 |
| 4.3 基于影响集的区域影响力阻断最大化算法IS-LSS |
| 4.3.1 影响集和区域限制影响集 |
| 4.3.2 IS-LSS算法 |
| 4.4 改进的区域影响力阻断最大化算法IS-LSS+ |
| 4.5 实验及分析 |
| 4.5.1 实验设置 |
| 4.5.2 与贪婪算法的比较 |
| 4.5.3 查询区域与阻断区域相同时的实验结果 |
| 4.5.4 查询区域与阻断区域不同时的实验结果 |
| 4.6 本章小结 |
| 第5章 基于主题的区域影响力阻断最大化算法 |
| 5.1 引言 |
| 5.2 问题定义 |
| 5.3 基于主题的区域影响力阻断最大化算法LTIBM-H |
| 5.3.1 区域目标节点的获取 |
| 5.3.2 基于整体的节点区域主题阻断影响力估计 |
| 5.3.3 LTIBM-H算法 |
| 5.4 实验及分析 |
| 5.4.1 实验设置 |
| 5.4.2 正种子数对性能的影响 |
| 5.4.3 主题对性能的影响 |
| 5.4.4 区域规模对性能的影响 |
| 5.4.5 负种子数对性能的影响 |
| 5.5 本章小结 |
| 结论 |
| 参考文献 |
| 攻读博士学位期间发表的论文和取得的科研成果 |
| 致谢 |
| 个人简历 |
（8）线性约束下的组合优化问题研究（论文提纲范文）
| 摘要 |
| abstract |
| 主要符号对照表 |
| 第1章 引言 |
| 1.1 研究背景和选题意义 |
| 1.2 线性约束下的组合优化问题 |
| 1.3 相关研究 |
| 1.4 论文主要工作和内容安排 |
| 第2章 相关知识概述 |
| 2.1 组合优化 |
| 2.2 计算复杂性 |
| 2.3 近似算法 |
| 2.4 线性规划和相关数学规划问题 |
| 第3章 线性约束下的排序问题 |
| 3.1 SLC问题及背景介绍 |
| 3.1.1 问题描述 |
| 3.1.2 应用背景 |
| 3.1.3 排序问题简介 |
| 3.2 一台机器或一个约束的情形 |
| 3.2.1 一台机器的情形 |
| 3.2.2 一个约束的情形 |
| 3.3 常数台机器的情形(m≥2) |
| 3.3.1 常数个约束的情形(k≥2) |
| 3.3.2 任意个约束的情形(k≥2) |
| 3.4 任意台机器的情形(m≥2) |
| 3.4.1 两个约束的情形(k=2) |
| 3.4.2 常数或任意个约束的情形(k≥3) |
| 3.5 本章小结 |
| 第4章 线性约束下的背包问题 |
| 4.1 KLC问题及背景介绍 |
| 4.1.1 问题描述 |
| 4.1.2 应用背景 |
| 4.1.3 背包问题简介 |
| 4.2 常数个约束的情形 |
| 4.3 任意个约束的情形 |
| 4.3.1 KLC1问题 |
| 4.3.2 KLC2问题 |
| 4.4 线性约束下的多背包问题 |
| 4.5 本章小结 |
| 第5章 线性约束下的装箱问题 |
| 5.1 BLC问题及背景介绍 |
| 5.1.1 问题描述 |
| 5.1.2 应用背景 |
| 5.1.3 装箱问题简介 |
| 5.2 任意个约束的情形(k≥2) |
| 5.3 常数个约束的情形 |
| 5.4 物品大小受限的情形 |
| 5.5 本章小结 |
| 第6章 线性约束下的最短路和顶点覆盖问题 |
| 6.1 问题描述 |
| 6.2 相关问题简介 |
| 6.3 常数个约束的情形 |
| 6.4 不可近似性 |
| 6.5 本章小结 |
| 第7章 总结和展望 |
| 参考文献 |
| 致谢 |
| 个人简历、在学期间发表的学术论文与研究成果 |
（10）有元素类型约束的k-划分问题研究（论文提纲范文）
| 0 引言 |
| 1 贪婪算法:修正的LPT算法 |
| 2 近似算法的性能比率分析 |
| 3 结论及工作展望 |
四、贪婪算法与最坏性能比分析（论文参考文献）
- [1]面向交通出行的车联网资源调度策略研究[D]. 熊凯. 电子科技大学, 2021(01)
- [2]软件定义网络中的流量矩阵估计和网络流量调度[D]. 刘贵燕. 西南大学, 2020
- [3]考虑恶化或学习效应的分组批调度方法研究[D]. 廖宝玉. 合肥工业大学, 2020(01)
- [4]遗憾最小化查询近似算法研究[D]. 董奇. 南京航空航天大学, 2020(07)
- [5]5G移动通信系统信道估计与均衡算法的研究[D]. 阮扬帆. 电子科技大学, 2020(07)
- [6]平行机上半在线排序模型的算法性能分析[D]. 汪俐敏. 湖南师范大学, 2019(01)
- [7]社交网络中的影响力阻断最大化研究[D]. 朱文龙. 哈尔滨工程大学, 2019
- [8]线性约束下的组合优化问题研究[D]. 聂嘉明. 清华大学, 2017(02)
- [9]最大和搜索结果多样性问题及其贪婪算法分析[J]. 代文强,李晓荣,冯毅. 系统工程理论与实践, 2016(03)
- [10]有元素类型约束的k-划分问题研究[J]. 任庆娟,许保光. 运筹学学报, 2012(03)