【摘 要】
：
最大团问题（Maximum Clique Problem,简称MCP）是一类NP难问题,有效求解它的精确算法大多数是基于分支定界（Branch-and-Bound,简称B＆B）框架的,其中的上界策略对缩小解空间、提高算法效率起着重要作用。目前应用最广泛的是基于图着色的上界,但该上界与最优解之间常常存在一定的差距而导致解空间过大。此外它的时间复杂度总是大于O（n2）,当图规模较大时它可能对算法效率产
论文部分内容阅读
最大团问题（Maximum Clique Problem,简称MCP）是一类NP难问题,有效求解它的精确算法大多数是基于分支定界（Branch-and-Bound,简称B＆B）框架的,其中的上界策略对缩小解空间、提高算法效率起着重要作用。目前应用最广泛的是基于图着色的上界,但该上界与最优解之间常常存在一定的差距而导致解空间过大。此外它的时间复杂度总是大于O（n2）,当图规模较大时它可能对算法效率产生负面影响。MCP以及其他NP难问题的巨大计算量给电子计算机带来了挑战,膜计算（又称P系统）作为一种具有极大并行性的计算模型,在解决NP难问题上更具有优势,而它对MCP鲜有研究。因此本文针对解决MCP的精确算法尤其是对上界策略的优化进行了研究。为求解一般的MCP——k-团问题,本文设计了一个求解k-团问题全部解的P系统,并完成了仿真实现。本文的主要工作有:①提出了能够捕捉G中顶点的邻居之间局部关系的s-index和s+-index,基于此设计了s+-index上界策略,它相比基于图着色的上界策略的时间复杂度更低为O（n）。将其与基于图着色上界策略相结合并对测试的九个图数据集预估上界,实验表明,该上界是基于图着色上界的0.74～0.98倍,平均小了 21,最多的小了 48。验证了s+-index上界策略与基于图着色上界策略相结合的优势。②提出了一种解决MCP的精确算法SMC-BRB,该算法分为初始化、启发式求解、精确求解三个阶段,它在启发式求解阶段将s+-index上界策略与图着色策略相结合并对所有子解空间预估上界,在精确求解阶段利用该上界对无效的子解空间进行剪枝。在九个测试图数据集上,SMC-BRB与三个目前优秀的MCP算法进行了对比实验。实验结果表明SMC-BRB在5小时内找到最大团的成功率为100%,比对比算法的高33%～100%。此外SMC-BRB运行10次的时间平均值是所有对比算法中最短的0.68～1.00倍,验证了 SMC-BRB算法的有效性。③提出了求解k-团问题的算法KCLIQUE,基于该算法提出了求解k-团问题全部解的P系统ΠKCLIQUE,设计了ΠKCLIQUE的初始膜结构和五类进化规则,并通过实例及计算机仿真软件验证了KCLIQUE和ΠKCLIQUE的有效性和正确性。本文所提出的s+-index上界策略和SMC-BRB算法对未来基于B＆B框架求解MCP的精确算法的研究提供了更多上界策略的选择和算法参考。本文所设计的求解k-团问题全部解的P系统ΠKCLIQUE对拓宽P系统的应用领域有重要意义。
其他文献
害虫是造成农作物减产和破环园林生态的主要因素之一。准确而快速的害虫识别是害虫防控过程中的关键所在。传统害虫识别主要依赖农林业专家的经验,而这一过程效率低且成本高昂。近年来,随着深度学习技术在计算机视觉领域取得快速进展,基于卷积神经网络（Convolutional Neural Network,CNN）的害虫图像识别方法被广泛研究与应用,并取得显著成效。然而,野外环境下的害虫图像识别由于受到细粒度、
电子鼻系统模拟了生物的嗅觉系统。它通过传感器技术和人工智能技术实现了对气体的快速检测和分析。然而在实际应用中,电子鼻系统会出现传感器时间漂移和多系统板间差异问题。这些问题会导致电子鼻系统前后采集的数据分布发生变化,使得训练好的模型无法有效地对后续数据进行分析,从而限制了电子鼻的应用。近年来,基于子空间投影的漂移抑制方法发展迅速,但性能需要进一步提高。本论文的研究目的便是提出高性能的基于子空间投影的
膜进化算法（Membrane Evolutionary Algorithm,MEA）是受到生物细胞结构和行为启发而提出的一种进化算法,被广泛应用于各类NP难问题的求解上。最长圈问题（Longest Cycle Problem,LCP）是图论中经典的NP难问题之一,不仅在图论研究中有重要的意义,也和现实世界的复杂网络应用密切相关。过往的LCP研究大多通过特殊图的理论性质来寻找最长圈,难以直接运用到现
红外摄像头主要应用于低光照或夜间条件下的监控系统,是城市视频监控系统重要的组成部分,在可见光图像与红外光图像之间检索行人对于城市安防以及刑侦工作的高效开展起着重要作用。因此跨模态行人重识别的研究十分重要。跨模态行人重识别指在可见光图像与红外光图像之间检索行人。现有基于深度学习的跨模态行人重识别模型识别精度普遍较低,原因是两种图像成像方式不同,风格上存在较大差异,提取出的图像特征缺乏另一模态信息,而
作为人工智能的重要应用领域,智慧医疗具有将生理数据与医学知识联系起来的关键能力,在提高医疗服务质量的同时降低医疗成本方面显示出巨大的潜力。同时,基于机器学习模型的智慧医疗服务也能借助云计算等新兴技术,在提升数据服务质量的同时降低行业从业门槛,促进以人为中心的智能解决方案。基于数据和机器学习模型的智慧医疗系统需要采集用户的生理数据来提供高质量的数据服务。然而,医疗数据的敏感性在用户隐私方面极为关键,
随着大数据时代的到来,无论是获取数据的渠道和方式,还是数据本身的大小、类型和结构都越来越多样化,这使得数据挖掘的发展越来越具有挑战性。近年来离群检测逐渐成为数据挖掘领域中的热门研究方向,它被广泛地应用于包括社交网络、移动支付和购物系统等在内的众多领域,因为除了常规数据外,少数离群点往往也能带来有价值的信息,并且随着业务的升级,对离群检测算法能够更有效地处理各种复杂的数据的要求也越来越高。本文针对现
土地利用/覆盖变化（LUCC）的研究可以帮助人们更好地对土地资源进行合理的配置,使得社会能够可持续发展。冯·诺伊曼提出的元胞自动机能够有效模拟从大量基本单元的相互作用中涌现出的包括自组织结构在内的复杂现象,因此被广泛应用于土地利用变化的模拟。目前针对基于元胞自动机的土地演变模型的改进大都集中在前期的适应性概率的计算方式上,比如使用神经网络、逻辑回归、支持向量机等机器学习方法,而对元胞自动机模型自身
＜正＞一、问题的提出目前，社会对高质量学前教育资源的需求日益迫切，幼儿师资的培养要求随之发生显著变化，直接影响着高等院校学前教育专业人才培养的走向。2018年《教育部关于实施卓越教师培养计划2.0的意见》提出贯通职前职后，创新机制模式，深化协同育人的指导方针，要求支持建设一批省级政府统筹，高等学校与中小学（幼儿园）“协同开展培养培训、
互联网用户数的急剧膨胀导致相关数据量激增,由此产生的信息过载问题持续影响着人们的生活。推荐算法可以帮助人们快速从海量信息中获取真正需要的内容,摆脱信息过载并节省信息筛选的成本。在为人们带来便利的同时,推荐算法自身也暴露出了诸多问题。目前推荐算法的改进工作大多以各类型上下文信息构建用户和项目之间的联系,再融入如矩阵分解、深度学习等多种技术,提升算法的预测精准度。针对目前推荐算法中存在的冷启动问题和预
近年来随着人们的生活水平不断提高,人们承受的压力也逐渐增加甚至部分人由此导致了如睡眠质量变差等各种问题。有研究表明合适的音乐可以改善人的睡眠质量,但由于音乐种类众多使得寻找适合自己的音乐也成为一个难题,本文的目标是通过深度学习技术来实现睡眠音乐的自动生成,从而缓解这个难题。本文实现睡眠音乐生成的方法主要包括主旋律提取以及音乐生成两个方面的内容。其中存在许多难点:1)音乐数据不同于普通的序列数据,可