若干情形分组和覆盖Steiner问题的算法

综合论述了理论计算机科学领域中两个密切相关的NP-困难问题:分组Steiner问题和覆盖Steiner问题的不同解决途径,并就其若干特殊情形设计了近似比更好的近似算法。

面向大规模优化问题的精英贡献两阶段动态分组算法

协同进化框架是解决大规模全局优化问题的有效方法,设计合理的决策变量分组方法是提高协同进化算法性能的关键,而利用精英决策变量动态构建精英子组件可以有效提高进化效率,但在进行大规模优化时,其可能将无关的变量分配到同一子组件,从而无法充分利用分组提高协同进化效率。针对该问题,提出一种精英贡献两阶段动态分组算法(EC-TSDG)。在分组前阶段,对变量进行随机分组,评估变量的贡献程度,从众多变量中寻找精英贡献变量;在分组后阶段,利用变量的相关关系寻找与精英决策变量存在相互作用的剩余变量,并将其合并形成精英子组件,使得精英子组件内部的变量两两相关,以此提高变量分组的准确性以及算法的收敛速度,避免子组件之间的相关干扰。最后,采用具有外部存档的自适应差分进化算法作为优化器进化各个子组件。在CEC'2013测试集上与其他先进算法进行比较,实验结果表明,EC-TSDG收敛速度快于对比算法,Friedman检验值为1.43,平均排序较对比的动态分组算法DCC平均提升36.78%。

基于组合变异和分组优化的单亲遗传算法求解旅行商问题

针对遗传算法求解旅行商问题存在收敛速度慢、容易陷入局部最优等问题,提出了基于组合变异和分组优化的单亲遗传算法。算法设计了由双侧倒序、近邻交换、跳跃基因构成的组合变异算子,用于扩大搜索范围,增强种群的多样性;经过精英优选后,将种群按适应度优劣分为两组作局部优化,对优质互异组依次采用插入和2opt算子,加快进化收敛速度;对普通组用倒序算子,增强其跳出局部最优的能力。仿真实验表明,对于中小型规模的旅行商问题,该算法在收敛速度和求解能力上得到明显改善和增强。

Steiner树优化问题的算法研究综述

最优Steiner树问题(Steiner tree problem,STP)是一个经典的组合优化问题,许多工程问题都可以归结为最优Steiner树问题。STP被广泛应用于通信网络、电路设计、VLSI设计等领域。然而,STP是典型的NP难问题,还没有多项式时间的精确算法求解该问题。目前,求解该问题的算法主要集中在基于启发式的近似算法、智能优化算法、信息传播算法等,并取得了很好的效果。在不同规模的网络中,基于传统遗传算法给出一种叶交叉机制(leaf crossover,LC),使用该机制的算法性能表现更好。通过对这些算法的原理、性能、精度等方面进行梳理,归纳出算法的优缺点,并指出STP的研究方向和算法设计路径,对于相关问题的研究有指导意义。

面向大规模重叠问题的两阶段差分分组方法

大规模重叠问题在实际工程应用中普遍存在,重叠问题子组间的共享变量给大规模重叠问题的优化带来了很大困难。基于分解的协同进化(CC)算法在解决大规模重叠问题上表现良好。然而,一些针对重叠问题设计的新型CC框架依赖问题分解方法获得重叠问题结构,而目前针对大规模重叠问题设计的分解方法不能同时兼顾高效性和准确性。为此,提出一种两阶段差分分组(TSDG)方法,在实现精确分组的同时显著减少了计算资源消耗。在第一阶段,采用基于有限差分原理的分组方法高效地识别子组集和共享变量集;第二阶段则提出一种分组改善方法检查前一阶段得到的子组集和共享变量集的信息,改正不准确的分组结果,以提高分组的稳定性和准确性。利用两阶段的协同作用,TSDG实现了对大规模重叠问题高效准确的分解。实验结果表明,TSDG能够在消耗较少计算资源的同时准确地分解大规模重叠问题。在优化实验中,TSDG在大规模重叠问题上的表现也优于对比算法。

组合计数中的分组问题探究

将n个小球装入若干个袋子里,共有多少种分法?这个问题叙述并不完整,因为小球是否有差异,袋子是否有差异等均未交代.可以将此分组问题分成4大类,某些子类中还要考虑是否允许有空袋子、袋子数量给定还是足够多等情形.下面选取有代表性的若干问题展开探究,其中大部分问题我们都得到了通解.

浅析排列组合中分组分配问题的解题策略

排列组合问题是高考数学中的必考题型,题型多变,解题方法也多种多样。其中分组分配问题是排列组合中的一类综合性问题,也是排列组合中的难点,两者之间既有区别又有联系,稍不留意就会引发混淆。为了解决这一棘手问题,下面将结合几个例题谈一谈解答分组分配问题的策略。

广义欧几里德Steiner问题的研究与进展

广义欧几里德Steiner问题是指确定连接平面上一组给定点的满足特定连通性要求的最短网络的问题。本文主要介绍了此问题的研究与进展,在建立了求给定平面点集的最短U-连通(或边连通)生成网络的整数规划模型的基础上,证明了文献[13]中所给的一个例子是错误的,并提出了一些关于广义Steiner问题的进一步研究的问题。

基于最优加权Steiner树的枢纽型物流中心选址问题

为了满足近年来物流运输业快速发展的需要,促进物流中转运输网络的合理化建设,研究了枢纽型物流中心的功能和选址原则,详细分析了影响枢纽型物流中心选址的各种因素,提出了基于结点带权的欧氏Steiner最优树的枢纽型物流中心选址方案。针对该方案设计了相应的智能优化算法,并进行了具体的程序实现。借助该方案不仅可以使总的运输成本最小,而且能够在无需事先确定备选点的数量和位置的情况下实现同时确定枢纽型物流中心的数量及位置的目标。最后以长三角地区枢纽型物流中心的建设问题为背景,对各种数据进行了仔细的分析比较,从中确定若干区域作为物流服务需求点集,并将各种因素的综合效用作为物流需求点的权值,对上述算法进行了有效性验证。

瓶颈Steiner网络设计问题的算法研究

瓶颈Steiner网络设计问题要求从网络中找出一个满足某种瓶颈条件的Steiner树,由于该问题的NP困难性,因此必须找出它的近似算法。该文针对树和一般图这2种网络情形,在问题转化的基础上分别给出了基于分组Steiner问题的近似算法,在Marathe等算法思想的基础上给出了有根和无根2种情形下的2个近似算法。

基于设施选址的Steiner问题的算法

在设施选址问题的基础上给出了广义Steiner树-星问题的两个近似比分别为3.55和3.582的近似算法,并在问题转化的基础上研究了其他若干特殊情形的Steiner树问题的近似算法。

求解约束优化问题的分组比较遗传算法

Deb提出的基于遗传算法求解约束优化问题的约束处理方法简单易用,但存在一些不足之处.通过考虑不可行解在优化过程中的作用,对Deb的方法进行了改进,提出了分组比较的约束处理方法,并将该法结合到一个改进的遗传算法中.数值实验和比较结果表明了这种方法的有效性.

高校思政课“群体开放式”教学模式探究——以课内“问题互动及分组讨论”为视角

激发群体动力,减缓教学疲劳,增强师生群体能动性,以学定教。思政课教师应围绕教学目标精心设计问题,结合经典视频或案例等创设愉悦教学环境,指导学生分组讨论并不时进行归纳总结。师生结合现实问题相互提问对话进行深入交流,根据每组学生思考和探讨问题表现进行综合考核评价。

带圆周约束的Steiner树问题

本文首先考虑了带圆周约束的Ｓｔｅｉｎｅｒ树问题．设欧氏平面上有一圆，平面上有ｎ个点，所成点集为Ｎ，该问题是要在圆周上找一点Ｐ，使Ｎ∪｛Ｐ｝这ｎ＋１个点的Ｓｔｅｉｎｅｒ树之长度达到最短．本文对于ｎ＝２的情形给出解．另一方面，鉴于问题的复杂性为ＮＰ－Ｃ，作者提出了一个近似解，并证明了近似解的性能比为３／２．

分组密码工作模式的应用安全问题

分组密码工作模式有着近乎完美的理论体系:只要底层分组密码是安全的,上层工作模式就可以被证明是安全的.但是理论与现实之间存在巨大差距,现实情况中分组密码工作模式往往会出现各种各样的应用安全问题,主要梳理了其中的IV误用、在线攻击、RUP问题、填充谕示攻击、生日攻击等一系列问题,其中IV误用是指程序员生成的IV值没有达到密码学要求的随机强度,对此可以使用基于Nonce的方案来避免;在线攻击是指一些情况下数据采用在线处理的方式而受到的逐分组攻击,解决方法是使用在线安全的认证加密模式;RUP问题是指工作模式输出未验证的明文,使得数据完整性得不到满足,对此Abed和Ashur等人对相关模式进行了改进;填充谕示攻击是指敌手利用接收方对不正确密文返回的错误提示信息进行攻击,对此可以使用认证加密模式来避免;生日攻击利用工作模式中间状态的碰撞进行伪造的攻击,在此攻击下分组长度为64 b的分组密码的安全强度会降为32b,为了避免这个问题,需要设计超生日界的工作模式.详细分析了以上问题出现的原因、关于它们的研究现状及相应的解决办法,最后给出几点具体的建议.

基于动态分组算法求解TSP问题

利用TSP问题特点,提出了动态分组算法求TSP问题.将TSP环路动态随机分解成双环,再用最佳组合方式组合成单环,实现了在总体路径寻优下的局部路径优化,从而使所得路径尽可能接近最优解.通过对TSPLIB中实例的大量实验及与KD、KL、SETSP、Budinich和ESOM等类SOM算法的比较,表明该算法具有良好的性能.

关于Steiner树问题

三年前,山于堵丁柱和黄光明两教授关于 Steiner 比猜想的文章发表的消息在纽约时报上刊登,该结果又接连在国内获奖,Steiner 树问题曾引起不少读者的兴趣和关注.但多数人对 Steiner 树的历史和发展了解甚少.本文作者在93年初就打算写篇介绍

高校分组教学和问题教学方法综述

本文从分组方法、分组教学方法的实证以及分组教学相对于传统教学方法的意义等方面对分组教学的当前研究现状做了综述性的概括,从问题设计和问题教学意义等方面综述了问题教学的研究现状。文中总结了当前分组教学和问题教学中存在的不足,并提出将分组教学与问题教学相结合的可行性。

基于问题的分组式教学在“操作系统”课堂中的应用

根据"操作系统"课程的特点,结合实际教学经验,在"操作系统"教学中采用基于问题的分组式教学法。即先对学生分组,然后以问题为主,通过学生组提出和解决问题,使学生以团队的形式参与到教学中来,提高了学生的学习兴趣,能更好的掌握知识点,达到了很好的教学效果。

关于E_0的Steiner邮路问题

给定图G=(V,E,w),E_0E是一个指定通过的边子集,本文讨论了关于E_0的Steiner邮路问题的特殊情况,即由E_0导出的子图仅有两个连通分支。我们分别考虑了三种不同的情形,并给出了子闭迹消去算法和带限制的最短链算法,前者是一个基于整数规划的精确算法,而后者是一个近似算法。