摘要：图的划分问题(GPP)是具有广泛应用背景的典型NP-难解问题,高效启发式算法一直是该领域的研究热点.作为设计启发式算法的有力工具,GPP的骨架分析存在理论分析结果匮乏、骨架规模过小等缺陷.文中采用构造偏移GPP实例的技巧,不仅在理论上证明了获取GPP的骨架是NP-难解的,并且利用一般GPP实例与偏移实例的关系,实现了骨架规模的提高.在此基础上,文中对于目前求解GPP问题最好的算法之一的IBS进行了改进,提出了基于偏移实例的IBS算法(BI-IBS).算法BI-IBS首先构造偏移GPP实例,然后再利用局部最优解交集对它进行归约,最后再求解归约后的规模更小的新实例.实验结果表明,BI-IBS比现有算法在解的质量上有了较显著的提高.文中的工作较完善地解决了GPP的骨架研究存在的问题,所采用的构造偏移实例的技巧对于其它NP-难解问题的骨架理论分析及启发式算法设计亦具有较高的参考价值.

摘要：旅行商问题(traveling salesman problem,简称TSP)是经典的NP-难解组合优化问题之一,求解它的高效启发式算法一直是计算机科学研究的热点.脂肪作为描述TSP结构特征的新工具,对启发式算法设计具有重要意义.目前,TSP问题的脂肪研究还处于初始阶段,缺乏理论分析结果及相关的启发式算法.首先分析了TSP问题的脂肪计算复杂性,通过构造偏移实例的技巧,证明了获取TSP的脂肪是NP-难解的,即在P≠NP的假设下,不存在算法可以在多项式时间内获得完整脂肪.在此基础上,通过分析TSP问题局部最优解与脂肪的关系,给出了求解TSP问题的元启发式算法——动态候选集搜索(dynamic candidate set search,简称DCSS)算法.利用该算法,改进了目前求解TSP问题最好算法之一的***典型实例的实验结果表明,改进后的算法在解的质量上有较为明显的提高.新的基于脂肪的启发式算法对于求解其他NP-难解问题具有一定的参考价值.

摘要：骨架是指一个NP-难解问题实例的所有全局最优解的相同部分,因其在启发式算法设计中的重要作用而成为该领域的研究热点.本文对目前骨架及相关概念的研究成果进行了全面综述,将骨架本身的研究工作归纳为三个层面:理论基础层面主要考虑骨架与计算复杂性的关系问题;应用基础层面主要考虑如何高效地获取骨架;应用层面主要考虑如何利用骨架进行高效启发式算法设计.在此基础上,本文详细讨论了骨架研究亟待解决的难题,并指出了解决这些问题的努力方向.

摘要：该文针对聚类问题上缺乏骨架研究成果的现状,分析了聚类问题的近似骨架特征,设计并实现了近似骨架导向的归约聚类算法。该算法的基本思想是:首先利用现有的启发式聚类算法得到同一聚类实例的多个局部最优解,通过对局部最优解求交得到近似骨架,将近似骨架固定得到规模更小的搜索空间,最后在新空间上求解。在26个仿真数据集和3个实际数据集上的实验结果表明,骨架理论对提高聚类质量、降低初始解影响及加快算法收敛速度等方面均十分有效。

摘要：设计模式是对实际软件设计方案的经验性总结,是软件开发中辅助软件设计的有效方案之一。现有设计模式挖掘研究的任务大多是在源代码中识别设计模式的实例,少有考虑用自然语言语料对设计模式建模。为了提升设计模式语言分类模型的推荐效果,将代码、类图或对象协作纳入考虑范围,提出了一种基于CodeBERT的设计模式分类挖掘模型dpCodeBERT,以实现自然语言与代码语言的对照理解。首先,通过随机组合合成多分类算法数据和代码搜索数据作为模型输入,dpCodeBERT模型能够获取transformer层中的模型为令牌生成的注意力权重;然后,分析令牌和语句注意力权重以发现更有效的模型输入类别,进一步改造训练输入;最后,dpCodeBERT模型能够通过全连接层将分布式特征映射到样本空间并输出复数值的方式实现具体软件工程任务,如设计模式选择和设计模式代码搜索任务。在拥有80个软件设计问题的设计模式选择任务的数据集上的实验结果显示,相比同类基准模型,所提模型在设计模式检测准确率(RCDDP)和平均倒数排名(MRR)两个指标上平均提升了10%~20%,设计模式选择更加准确。通过深度研究模型数据需求,dpCodeBERT挖掘了CodeBERT对类级代码的理解,探索了CodeBERT在设计模式挖掘中的应用,具有预测准确、拓展性强等特点。

摘要：旅行商问题(Traveling Salesm an Prob lem,TSP)是组合优化中最典型的NP难问题之一,长期以来人们都在寻求快速高效的近似算法以在合理的计算时间内准确地解决大规模问题,并设计出许多高效实用的启发式和宏启发式算法,其中循环LK算法是性能最好和最具代表性的算法之一.作者研究了该算法的运行时间分布:通过对TSPLIB中大量不同规模的TSP实例的运行时间分布的统计分析和拟合,发现求解TSP问题的循环LK算法的运行时间分布很好地服从W e ibu ll分布,并进一步给出了该分布对求解TSP问题的物理意义.作者同时首次给出了循环LK算法求解TSP问题得到的解的性能分布以及由此得到的一些有实际指导意义的结论.

摘要：黑白旅行商问题是经典旅行商问题的推广,在基于SONET技术的光纤网络设计、航线调度等领域具有广泛的应用.已有研究工作集中在无向黑白旅行商问题上.文章研究该问题的更一般形式——有向黑白旅行商问题.首先,给出了有向黑白旅行商问题的混合整数线性规划公式.与目前无向黑白旅行商问题包含指数多个约束的规划公式相比,它仅包含多项式个约束.其次,给出了一种启发式算法.实验表明,该启发式算法能够有效地求解黑白旅行商问题的实例.由于无向黑白旅行商问题是有向黑白旅行商问题的特例,故文中的结论对于求解无向黑白旅行商问题同样有效.

摘要：运用桌面虚拟化技术,对现有的实验体系进行了相关内容的扩充。利用VMware View虚拟化平台最大限度地提高服务器利用效率,同时为终端提供快捷、安全的定制化桌面系统,设计搭建针对实验室环境的桌面虚拟化实验。针对高校学生的基本情况设计了理论完善、操作性强的实验流程。

摘要：骨架分析是近年来理论计算机科学研究的热点,对于NP-难解问题的启发式算法设计具有重要意义.由于骨架计算复杂性研究十分困难,现有的骨架分析方法多采用实验统计手段.针对现有方法中存在的骨架规模小的缺陷,给出图的二分问题GBP(graph bi-partitioning problem)的唯一全局最优解实例构造算法,有效提高了骨架的规模.同时,利用该算法从理论上证明了寻找GBP问题的完整骨架属于NP-难解问题,即在P≠NP的假设下,不存在多项式时间的算法可以确保得到GBP问题的完整骨架.本文的工作拓广了骨架计算复杂性研究的范围,所提出的唯一全局最优解实例构造算法对于NP-难解问题启发式算法设计亦具有较高的参考价值.

摘要：CLARANS是一种有效且广泛应用于空间数据挖掘的聚类算法,非常适合发现多边形的聚类结果.CLARANS的实质是随机重启搜索优化算法.由于搜索空间的表面粗糙不平,布满了局部最优解的"陷阱",因此CLARANS算法易受局部最优解的影响.空间平滑技术允许启发式搜索有效地避开局部最优解的"陷阱".本文给出了基于空间平滑搜索的CLARANS算法(CLARANS algorithm based on Search Space Smoothing-CLARANS-SSS),设计合理的噪声法空间平滑策略能够移除搜索空间中大部分的局部最优解.实验结果表明空间平滑搜索对于CLARANS算法非常有效.