【摘 要】
：
聚类旅行商问题（CTSP）是旅行商问题（TSP）的一个重要扩展问题,在路径规划领域吸引了许多的研究者关注。给定带边权的无向完全图G=（V,E）,其边代价满足三角不等式,顶点集V被划分为几个簇,问题的目标是计算一条访问所有顶点的代价最小的哈密顿回路,并且每个簇中的顶点都被连续访问。在许多的实际应用中,往往需要考虑一些其他因素的制约,因而产生了 CTSP问题的一个重要变体—广义聚类路由问题（The G
论文部分内容阅读
聚类旅行商问题（CTSP）是旅行商问题（TSP）的一个重要扩展问题,在路径规划领域吸引了许多的研究者关注。给定带边权的无向完全图G=（V,E）,其边代价满足三角不等式,顶点集V被划分为几个簇,问题的目标是计算一条访问所有顶点的代价最小的哈密顿回路,并且每个簇中的顶点都被连续访问。在许多的实际应用中,往往需要考虑一些其他因素的制约,因而产生了 CTSP问题的一个重要变体—广义聚类路由问题（The General Cluster Routing Problem,GCRP）给定一个必过点子集V?V和一个必过边子集E?E,GCRP的目标是计算一条最短路径以访问V中的每个点仅一次,并遍历E中的每条边至少一次,并且每个簇内的节点都被连续访问。本文研究了 GCRP问题的两个子问题,通过将问题转化为CTSP分别给出了两个子问题的近似算法,并改进了其各自当前的最佳近似比。本文第一部分内容研究了在每个簇内指定源点和目标点的广义聚类路由问题。其近似算法的主要思想如下:首先,在每个簇内,调用旅行商路径问题（Traveling Salesman Path Problem,path TSP）的算法获得一条从源点到目标点的最小代价的哈密顿路径,并将其收缩为一条有向边。其次,针对簇间的边,构造一个辅助图,并在图中寻找一个最小权值完美匹配。匹配中的边与簇内正好连接成一条环路。最后,将代表每个簇内的路径的有向边复原成路径,从而最终得到一条TSP回路。本文通过理论分析证明算法的近似比为5/3。本文的第二部分内容研究了每个簇内不指定两个终点的广义聚类路由问题,提出了另一个基于有向生成树的近似算法。我们的算法主要原理如下:首先,针对每个簇内的每一对节点对,以其作为源点和目标点,计算一条TSP路径;其次考虑组合一条路径与一条连接其他簇的边作为一条新的有向边,构造一个辅助图;然后,计算该辅助图的一个有向生成树和一个最小匹配;最后,将有向生成树和最小匹配中的边恢复为原图中的边与路径,从而最终得到一个TSP环游。本文经过理论证明得出,该算法的近似比为8/3。最后,文中用整数规划的解代替最优解,通过实验评估了本文算法的运行时间和实际性能。本文所设计的GCRP问题的算法以path TSP算法作为主要子算法模块,故其性能受旅行商路径问题的算法影响,因而旅行商路径问题算法的改进将带来本文算法的改进。
其他文献
时间序列数据在现实生活中随处可见,挖掘时序数据中的隐含信息并对其进行分析具有重大的现实意义。但在某些应用场景中,获取完整的时序数据非常困难或者需要较高的成本。解决这一问题的思路是引入主动学习,即选择少量时序中高价值的样本进行采集或者标记,然后利用这些少量采集到的数据对未采集的部分进行补全。由于不同的已采集数据对于补全效果的影响很大,为了提升补全精度,本文重点研究了时序数据的补全模型和选样策略。在补
社交媒体谣言检测旨在根据社交媒体事件相关信息对事件真实性进行判断,受到了学术界和工业界广泛关注。现有研究中基于深度学习的方法取得显著效果,然而该类方法仍存在诸多局限如:以往方法难以有效利用消息传播过程中用户特征潜在的时序信息;现有模型在获取基于全局的事件文本表示时记忆能力受限;当前研究中未能充分考虑事件多特征之间的交互关系。本文针对上述问题,进行了以下三方面的工作:（1）针对现有研究难以准确刻画消
随着集成电路先进技术节点步入微纳米时代,电路的复杂度呈指数级增长,同时布线过程要求全部总线位均需保持同一布线拓扑结构,尤其还存在布线轨道不均匀以及分布在各布线层的障碍物等问题,这给总线布线过程带来巨大的挑战。本文在当前总线布线研究的基础上,运用基于拆线重布的方法对总线布线过程中所涉及到的拓扑匹配问题展开深入研究,提出了一种在先进制程下的优化方案以解决上述问题。首先提出了基于拆线重布的拓扑匹配全局布
在临床上,对外周血白细胞进行分类识别是血液自动检测中一项重要的内容,实现端到端的外周血白细胞检测有着重要的意义。然而由于外周血白细胞同类之间形态变化大,血液显微图片背景复杂等问题,外周血白细胞识别准确率相对较低。并且现有方法大部分采用的是“先分割后分类”的做法,使得这些方法对外周血白细胞分类的准确性受到了分割效果的限制。针对上述问题,根据外周血白细胞检测的实际需求,本文研究外周血白细胞自动检测的方
图像描述任务旨在使计算机能够根据图像自动生成对应的描述语句,即完成从图像模态到语言文字模态的转换。近年来,随着深度学习技术的兴起,该领域已成为新兴的研究热点并取得了显著进展。尽管如此,仍然存在一些挑战:模态转换的中间表示对于图像语义信息的刻画不够准确;缺乏对历史解码信息和图像背景信息的有效利用;未充分考虑不同粒度图像语义信息的交互。针对上述问题,本文进行了以下三个方面的工作:（1）针对现有方法在模
选址的研究内容非常广泛,从城市规划、机场建设到配送中心、零售店的位置决策都是选址研究的范畴。随着当代社会发展和智慧城市建设,商家选址成为市总体规划中的重要一环。商家选址关系着城市商业的繁荣发展,关系着商家的经济收益,直接影响进店客流、服务内容和运营成本。因此,科学合理的选址对商家而言至关重要。早期获取数据的途径和数量有限,选址决策易掺杂着主观因素,导致准确率不高。随着互联网的发展,可以通过多种途径
电能是人类生产实践活动中至关重要的能源。随着社会工业化地不断发展,人们对电力资源的需求日益增加,与此同时,窃电行为造成的损失也在不断增加。因此,窃电行为检测对于规范用户用电行为,提高企业管理水平和经济效益具有重要意义。传统的反窃电技术存在耗费人力物力大、误报多、效率低等问题。随着智能配电网和大数据技术的发展,通过将大数据技术应用于窃电检测系统可以显著地提高电力公司在进行反窃电工作时的效率。论文根据
进入信息时代,许多事物可以被数据化,形成一个个数据实体。复杂网络作为这些数据实体以及实体间联系的抽象表示,有着许多现实应用,如交通运输网络、生物蛋白网络和社交关系网络等。复杂网络形式多样,如具有节点特征的属性网络、具有不同类型节点和边的异构网络等,给复杂网络的分析带来更大的挑战。社区结构是复杂网络的重要特性,描述了网络中节点在空间上的聚集性以及在特征上的相似性。社区发现旨在挖掘网络中的社区结构,从
数字图像在传输过程中无法避免会遇到图像退化现象,使用图像复原技术作为数字图像的预处理是一个非常有效且重要的环节。图像复原的目标是一个将退化图像恢复成原始图像的过程,这一过程事实上是求解病态逆问题的过程。基于非局部自相似性的图像复原已被证明是有效的图像复原技术,但是如何将图像块更好地划分开来是图像复原效果好坏的关键。通常使用聚类算法来实现对图像块的划分,因此如何提升聚类的精度也是提升图像复原能力的研
许多现实世界的系统都会产生结构化的数据,而结构化数据的知识发现需要使用由节点与节点之间的连接构成的网络数据。在一些真实场景,例如社交网络、通信网络以及金融交易网络中,这些结构化数据通常是动态变化的,即网络中的节点或者边会随着时间的推移而动态地演变。时序信息是动态网络的重要组成部分,反映了网络结构的演化机制。以社交网络为例,它的拓扑结构随着新用户的增加、好友关系的建立和解除而不断发展。对既有演变规律