摘要：提出了一种解决三维空间曲面匹配问题的有效方法。该方法基于最大独立集算法,通过将曲面匹配转化成曲面离散点的匹配并建立离散点之间的距离矩阵,利用误差半径构造0-1矩阵,最终求解出匹配点的最大独立集。实例表明:该算法能够实现曲面的部分匹配和整体匹配,并表现出良好的全局匹配效果。

摘要：针对炼钢生产中的钢种集约问题,建立了数学模型,并以图论的思路设计了一种基于最大独立集的求解方法.首先基于图论知识,构造了钢种集约问题的图,并证明了最大独立集的独立数是它的主目标的下界;然后对图进行赋权,以实现对次要目标的控制;最后在最大独立集的基础上,采用图分解的方法,对赋权图递归分解来获得优化后的钢种集约方案.选择实际生产数据构造了一些测试案例,对它们进行仿真计算,结果表明所提出的算法明显好于遗传算法;同时分析了图的顶点、密度变化对算法性能的影响,揭示了它们之间的关系.

摘要：最大独立集问题是著名的NP问题,并且在许多场景中都有应用。传统的精确算法解决最大独立集问题需要指数级的时间复杂度。为更高效地解决最大独立集问题,提出了一种基于量子近似优化算法的量子线路解决方案。该方案由最大独立集的数学模型,推导出最大独立集问题的哈密顿量表达式;设计了基于量子近似优化算法的量子线路,采用COBYLA经典优化算法对参数量子门中的参数进行优化,并使用IBM提供的量子开发框架Qiskit进行仿真实验。仿真结果表明,使用量子近似优化算法可以在多项式时间内以高概率获得最大独立集问题的解,实现了指数加速。量子近似优化算法对解决最大独立集问题有一定的可行性和有效性。

摘要：降低能耗以延长网络生存时间是无线传感器网络设计中的一个重要挑战.在传感器节点高密度部署的环境中,在保证网络性能的前提下,仅将最少量的节点投入活跃工作状态,而将其余节点投入低功耗的睡眠状态,是一种节约系统能量的有效方法.如何计算同时满足“覆盖要求”(工作节点必须能够完全覆盖目标区域)和“连通性要求”(工作节点组成的通信网络必须是连通的)的最小节点集合,是一个NP难问题.设计了一种基于目标区域Voronoi划分的集中式近似算法(centralizedVoronoitessellation,简称CVT),用于计算完全覆盖目标区域所需要的近似最小节点集.当节点通信半径大于等于2倍感知半径时,CVT算法构造的节点集是连通的;当节点通信半径小于2倍感知半径时,设计了一种基于最小生成树(minimumspanningtree,简称MST)的连通算法来计算确保CVT算法构造的覆盖集连通所需的辅助节点.理论分析和实验数据表明,CVT(+MST)算法的性能在时间复杂性和连通覆盖集大小方面都优于已有的贪婪算法.

摘要：为了有效地度量空间曲面相似性,针对噪声敏感、部分匹配的受损文物碎块模型,提出一种基于空间曲面特征优化的匹配算法.首先计算模型表面点体积积分不变量形成匹配约束簇,提取匹配约束簇特征,并结合曲面凹凸互补性得到初始匹配簇对;然后定义3类空间几何一致性约束,并采用最大独立集方法对非正确匹配对进行消除,求解粗匹配最优化问题;最后在粗匹配实验基础上,采用不变特征迭代最近点进行精确对齐.实验结果表明,该算法能较好地实现高噪声影响下存在部分匹配关系的受损文物虚拟拼接.

摘要：针对当前多星航天测控资源调度系统模型描述复杂、求解算法不适合大型算例的问题,利用系统约束条件的二元化特点建立了多星测控资源调度系统在一类特殊图上的最大独立集模型,进而针对该模型解空间结构多峰密布、欺骗性强的问题,提出了一种带预估选择机制的改进型Memetic算法.在分析交叉操作可达域的基础上,设计了一种能快速预估交叉操作最大收益的预估算子,通过预估运算,每个个体从几个待选交叉对象中可选择出最有利的一个对象,以在有希望区域间实现搜索的转移.大型Benchmark算例上的仿真结果表明,所提预估选择机制能减弱原模型欺骗性的影响,使Memetic算法的性能平均提高了17%.

摘要：许多生物序列数据库中都含有大量的冗余序列,这些冗余序列通常不利于对数据库的统计分析和处理,而且它们要占用更多的计算机存储和处理资源。针对这个问题,本文中我们设计了一种去除蛋白质冗余序列的算法。该算法基于图论最大独立集的概念来生成非冗余序列集合,对目前存在的不少蛋白质去冗余程序所采用的由Hobohm和Sander最早设计的一种首先将序列分成若干簇然后取出代表序列的算法进行了改进,使得生成了更多的非冗余代表序列集合,避免了一些非冗余的序列也被去除。我们开发出了实现该算法的程序FastCluster,可以用来去除蛋白质数据库中的冗余序列。

摘要：设计了一种基于目标区域Voronoi划分的改进的集中式近似算法,用于计算完全覆盖目标区域所需要的近似最小节点集.仿真结果表明,该算法能够有效地找到更少的连通覆盖节点,降低能耗,延长网络的生命周期.

摘要：加权分治技术是算法分析中的一种新技术,该技术基于选择不同的量来描述分支子问题的大小,以求得到在最糟糕情况下最好的时间复杂度.setpacking问题是一典型的NP-hard问题,广泛应用于调度、代码优化和生物信息学等领域.本文对有n个子集的setpacking问题,引入符号全集变量N设计基于分支搜索策略的递归算法,并应用加权分治技术对算法加以分析,得到时间复杂度为O*(1.1686n+N)的精确算法,当N≤n/4时,比现有最佳的算法O*(1.2209n)更加有效.

摘要：最大团问题是NP难解的,用遗传算法求解的关键是如何设计有效的评估函数.首先从理论上分析编码规则及适应函数对个体进化的影响,提出个体基因适应函数和个体适应函数多重评估方法,并设计求解算法.数值实验表明,算法具有较好的通用性和较高的性能.