混合图在无向图割集生成中的应用

为了进一步提高生成无向图割集的递归收缩算法的执行效率,将无向图转换为一类特殊的混合图,并将转换结果代替无向图输入递归收缩算法进行处理,修改了递归收缩算法中相应的算法步骤,使得改进算法可以更高效地生成无向图的割集.在理论上论证了改进算法的正确性,并通过理论分析和实验比较了改进算法和现有算法的时间复杂度和空间复杂度.理论分析结果和实验比较结果均表明改进算法明显比现有算法高效.     

3D网格脆弱水印中孤立水印顶点研究

研究发现,经典的3D网格脆弱水印中普遍存在的孤立水印顶点(簇)问题。通过理论和实例分析孤立水印顶点(簇)产生的原因,以及孤立水印顶点(簇)所导致的安全隐患。针对孤立水印顶点(簇)问题,在经典算法的基础上,提出改进算法,对水印顶点嵌入水印的同时,对非水印顶点进行伪水印处理,增加水印顶点之间的关联度,消除了孤立水印顶点(簇)。实验结果证明,改进后的算法有效地解决了孤立水印顶点(簇)问题。     

PVPS：P2P点播中的分布式搜索算法

PVPS系统针对P2P点播服务实现中的源节点搜索问题给出了一种实用高效的解决策略.PVPS在节点结构组织上采用了基于节目内容分簇的网状结构,每个分簇中由代理节点进行管理.在簇间搜索过程中,PVPS采用改进的启发式MPR算法、基于邻居优先级的自裁减策略和基于消息冗余度的剪枝策略对非结构化搜索进行多次优化,提高了搜索的效率.理论分析和实验结果表明,PVPS服务体系采用的搜索策略在性能上优于现有策略,在大型网络中具有良好的稳定性和扩展性.     

Hanoi塔问题非递归的新算法

关于Hanoi塔问题的非递归算法,已有了大量的研究[1￣4]。实验表明,当圆盘数目较少时,现有的非递归算法的执行速度比递归算法要快一些,但是随着圆盘数目的增加,现有的非递归算法的执行速度会逐渐变得比递归算法慢。论文提出了一种基于压缩编码的非递归新算法,在压缩了存储空间的同时,提高了算法的执行速度。实验结果表明,对于任意圆盘数目n,论文所实现的非递归算法的执行速度比现有的递归算法和非递归算法都有成倍的提高。     

深度优先遍历图的非递归算法的改进

针对深度优先遍历图的非递归算法与递归算法得到的顶点访问序列不一致的问题,提出改进算法。实验结果表明,改进算法在算法时间和空间性能保持不变的情况下克服了原算法的不足。     

简单多边形方向识别的健壮算法

极值顶点前后相邻边矢量叉积法是识别任意简单多边形方向的最优算法 该算法存在的问题是 :当极值顶点前后相邻边夹角接近 0°或 180°时 ,叉积结果接近 0 ,因此存在二义性 ,会导致错误的方向识别 针对现有算法对奇异情形方向判别解决不彻底的问题 定义了多边形极值顶点奇异情形 ,对相邻边夹角接近 0°和 180°两种奇异情形给出了判定方法 ;提出了极点前后点坐标比较法和极点序号大小比较法 ,有效地解决了所有奇异情形下的方向识别问题 ,它们都可以发展成为独立的方向判断算法 实验结果表明 ,该算法简单高效 ,健壮性强 ,时间复杂度为O(n)     

一种联系数表达的位置不确定数据流聚类算法

在不确定数据流聚类算法的研究中,位置不确定性是一种新的不确定数据类型.已有的不确定数据模型不能很好地描述和处理位置不确定数据.鉴于此,在提出基于联系数的位置不确定数据模型、联系距离函数、微簇密度可达性等主要概念的基础上,提出了一种联系数表达的位置不确定数据流聚类算法--UCNStream.数据流聚类算法采用在线/离线两级处理框架,使用基于密度峰值思想的初始化策略,定义了新的可动态维护的微簇聚类特征向量.利用衰减函数和微簇删除机制对微簇进行在线维护,准确地反映了数据流的演化过程.最后,分析了算法的计算复杂性,并通过对实际数据集上的实验与几种优秀的聚类算法进行了比较,实验结果表明,UCNStream算法具有较高的聚类精度和处理效率.     

反舰导弹航路规划的OACRR-PSO算法

为了提高反舰导弹航路规划算法的搜素效率,从几何学角度对航路规划空间进行了研究,在将功能区域概念融入 逆向航路规划的过程中发现了功能区域的几何学渐变规律,据此提出功能区域簇作为其物理载体.将功能区域簇引入粒子群优化(Particle swarm optimization, PSO)算法,提出了功能区域簇实时约束(Operational area cluster real-time restriction, OACRR)的PSO算法(OACRR-PSO).为了便于表示功能区域簇,采用航路极坐标编码方式.与传统的PSO算法不同的是,考虑到 粒子中分量之间的关联性,该算法在优化过程中并不是对粒子的整个速度分量同时进行更新,而是引入一种分步递归进化 策略对粒子的分量逐步进行更新.在粒子的更新过程中,使用功能区域簇来实时限定粒子位置分量的准确更新范围,使得 算法搜索空间逐步减小,从而加速算法收敛.仿真实验结果表明,分步递归进化策略能够非常显著地提高算法的全局搜索 性能,并且算法收敛速度快、稳定性好.     

四柱汉诺塔非递归研究与实现

对"经典三柱汉诺塔"的递归求解算法及其他非递归算法问题进行了详细的分析和研究,给出了一种新的简单且高效的非递归算法。在"经典三柱汉诺塔"的非递归算法研究基础上对"四柱汉诺塔"问题的四柱汉诺塔Frame算法进行了深入的研究,实现了一种高效的四柱汉诺塔非递归算法,并用C#语言进行了验证。通过该问题的C#实现,可使学习者清晰地观测到解决四柱汉诺塔非递归算法的全过程。     

多级划分算法的后处理与评价方法

多级划分算法需要进行多次实验以得到最优值.本文根据网表顶点在多次实验中的倾向性将其分为:活跃点、固定点和亚固定点,并提出只对活跃点重新划分的后处理方法.另外,通过将固定点和亚固定点分配到相应簇中,得到一种算法评价方法.实验表明,本文的后处理方法可有效减小hMetis算法的最小割,而评价方法能够客观评价hMetis算法在不同聚类策略下的划分结果.     

一种新的模式合一算法

传统的模式合一,使用递归调用的方法,算法的时间复杂度是指数级的,因此,往往容易耗费大量的系统资源,从而造成系统的崩溃。为了解决这个问题,本文提出一种新的模式合一算法,共时间复杂度为线性的。实验结果表明,本算法可以有效地解决原来算法中存在的递归调用问题。     

基于顶点度的模型简化算法

针对基于二次误差度量的边收缩算法在计算大度顶点误差度量时计算量大,且收缩该类顶点关联边时易使关键点发生偏移而引起模型变动过大、简化不够准确的问题,提出了基于顶点度的模型简化算法.该算法不但提高了模型的简化质量,而且加快了模型的简化速度.     

基于择优协作策略的PES算法在整数规划问题上的应用

整数规划是在科学领域和应用研究中广泛使用的一类数学模型.由于它是NP困难问题,因而求解困难.目前的求解方法是以群智能算法为主体,但这类方法一直未能很好地解决种群内部个体或者种群之间的探索与开采、竞争与协作的矛盾.基于金字塔结构的群智能演化策略（swarm intelligence evolution strategy based on pyramid structure,简称PES）是一种新型算法.该算法能够有效地解决上述两大矛盾.深入地分析了PES算法的机理,构造了一种择优协作策略的模型,并将改造后的PES算法由优化函数扩展到求解整数规划问题上.最后,通过探索实验以及对比实验探究了算法的收敛性、稳定性以及探寻全局最优点的性能.实验结果表明,基于择优协作策略的PES算法能够很好地求解整数规划问题.     

最小赋权支配集的迭代禁忌搜索算法

最小赋权支配集是一个NP困难的组合优化问题,有着广泛的应用背景。提出了一个高效的求解最小赋权支配集的迭代禁忌搜索算法。该算法采用随机贪心构造算法构造初始解,并利用快速的局部禁忌搜索算法寻找局部最优解,通过随机扰动和修复策略来搜索新的区域,以期跳出当前的局部最优解。用顶点数为800到1 000的大规模标准测试例子测试提出的算法。数值实验结果和与现存的启发式算法比较结果表明了算法是有效的。     

混合的密度峰值聚类算法

密度峰值聚类（DP）算法是一种新的基于密度的聚类算法，当它处理的单个聚类包含多个密度峰值时，会将每个不同密度峰值视为潜在聚类中心，以致难以在数据集中确定正确数量聚类，为此，提出一种混合的密度峰值聚类算法C-DP。首先，以密度峰值点为初始聚类中心将数据集划分为子簇；然后，借鉴代表点层次聚类算法（CURE），从子簇中选取分散的代表点，将拥有最小距离的代表点对的类进行合并，引入参数收缩因子以控制类的形状。仿真实验结果表明，在4个合成数据集上C-DP算法比DP算法聚类效果更好；在真实数据集上的Rand Index指标对比表明，在数据集S1上，C-DP算法比DP算法性能提高了2.32%，在数据集4k2_far上，C-DP算法比DP算法性能提高了1.13%。由此可见，C-DP算法在单个类簇中包含多密度峰值的数据集中能提高聚类的准确性。     

具有广义正则化与遗忘机制的在线贯序超限学习机

针对非平稳时间序列预测问题,提出一种具有广义正则化与遗忘机制的在线贯序超限学习机算法.该算法以增量学习新样本的方式实现在线学习,以遗忘旧的失效样本的方式增强对非平稳系统的动态跟踪能力,并通过引入一种广义的$l_2$正则化使其具有持续的正则化功能,从而保证算法的持续稳定性.仿真实例表明,所提出算法具有较同类算法更好的稳定性和更小的预测误差,适用于具有动态变化特性的非平稳时间序列在线建模与预测.     

基于规则的最短路径查询算法

最短路径查询是图数据管理中非常重要的一类问题.研究了基于规则的最短路径查询,它是一类特殊的最短路径查询问题.给定起点和终点,基于规则的最短路径查询是指找到一条从起点到终点的最短路径,使得此路径经过用户指定点集中的所有点,并且某些点的访问顺序满足一定的偏序规则.该问题被证明是一个NP-hard问题.目前已有的工作侧重于空间数据集（两点之间的最短距离用欧氏距离表示）上基于规则的最短路径问题,它采用穷举的方式列出所有满足规则的路径,然后选择长度最小的路径作为问题的解.然而在实际的道路交通网中,两点之间的距离等于两点之间的最短路径的长度,它往往大于两点之间的欧氏距离;此外,采用穷举的方式会造成大量重复的计算.因此,设计了一种前向搜索算法以及一些优化技术来求解该问题.最后,在不同的真实数据集上设计了大量的实验来验证算法的有效性.实验结果表明,该算法可以快速给出问题的解,而且算法的效率在很大程度上超过了现有的算法.     

Event‐triggered MPC design for distributed systems toward global performance

This paper studies the coordination control problem of stabilizing large‐scale dynamically coupled systems via a novel event‐triggered distributed model predictive control (DMPC) approach. In order to achieve global performance, certain constraints relevant to the triggering instant are imposed on the DMPC optimization problem, and triggering mechanisms are designed by taking into account coupling influences. Specifically, the triggering conditions derived from the feasibility and stability analysis are based on the local subsystem state and the information received from its neighbors. Based on these triggering mechanisms, the event‐triggered DMPC algorithm is built, and a dual‐mode strategy is adopted. As a result, the controllers solve the optimization problem and coordinate with each other asynchronously, which reduces the amount of communication and lowers the frequency of controller updates while achieving global performance. The recursive feasibility of the proposed event‐triggered DMPC algorithm is proved, and sufficient parameter conditions about the prediction horizon and the triggering threshold are established. It shows that the system state can be gradually driven into the terminal set under the proposed strategy. Finally, an academic example and a realistic simulation problem to the water level of a 4‐tank system are provided to verify the effectiveness of the proposed algorithm.     

进化策略算法在矩阵特征值求解中的应用

工程实践中多种振动问题的求解常常归纳为求矩阵特征值问题,另外一些稳定性分析问题及相关分析问题也可以转化为求矩阵特征值问题.为了有效求解此类问题,提出了一种新的求解矩阵特征值的进化策略算法,该算法可用于求解任意矩阵的特征值.实验结果表明,这种基于进化策略算法求解矩阵特征值的方法,与传统方法相比,表现出求解精度高,收敛速度快等优点.     

A new formulation and approach for the black and white traveling salesman problem

This paper proposes a new formulation and a column generation approach for the black and white traveling salesman problem. This problem is an extension of the traveling salesman problem in which the vertex set is divided into black vertices and white vertices. The number of white vertices visited and the length of the path between two consecutive black vertices are constrained. The objective of this problem is to find the shortest Hamiltonian cycle that covers all vertices satisfying the cardinality and the length constraints. We present a new formulation for the undirected version of this problem, which is amenable to the Dantzig–Wolfe decomposition. The decomposed problem which is defined on a multigraph becomes the traveling salesman problem with an extra constraint set in which the variable set is the feasible paths between pairs of black vertices. In this paper, a column generation algorithm is designed to solve the linear programming relaxation of this problem. The resulting pricing subproblem is an elementary shortest path problem with resource constraints, and we employ acceleration strategies to solve this subproblem effectively. The linear programming relaxation bound is strengthened by a cutting plane procedure, and then column generation is embedded within a branch-and-bound algorithm to compute optimal integer solutions. The proposed algorithm is used to solve randomly generated instances with up to 80 vertices.