八角形斯坦纳树问题的文化基因算法

针对多端线网互连问题,提出以超大规模集成电路物理设计中布线阶段应用较多的斯坦纳树为切入点,采用一种基于种群的全局搜索和基于个体的局部启发式搜索相结合的文化基因算法,对八角形斯坦纳树的结构进行优化,从而进一步缩减线长. 使用Prim算法预处理取得初始种群,并重新修改了原本的文化基因的编码以及相关操作,以便可以处理八角形斯坦纳树构建这一离散问题,利用八角形结构,使其能在全局范围内,快速收敛并全局寻优. 实验结果表明,所提算法能获得较好拓扑的八角形斯坦纳树,快速得到多端线网最优或者较优的布线结果,缩减布线的线长.     

最小直线斯坦纳树及其在详细布线中的应用

在面向区域的详细布线中,最小直线斯坦纳树(MRST)可为单个线网产生满足连线最短要求的最佳初始布线模式,可为全局最优布线大大减小搜索空间。一般说,构造MRST是NP完备问题,为了降低问题的复杂度,需要研究生成MRST的实用有效算法。本文讨论了两种这样的算法,并结合例题说明,MRST只是局部最优树,在实际布线应用中要综合考虑其它布线质量因素,对当前线网的初始MRST进行调整或动态修改。     

八角形斯坦纳树问题的文化基因算法

针对多端线网互连问题,提出以超大规模集成电路物理设计中布线阶段应用较多的斯坦纳树为切入点,采用一种基于种群的全局搜索和基于个体的局部启发式搜索相结合的文化基因算法,对八角形斯坦纳树的结构进行优化,从而进一步缩减线长.使用Prim算法预处理取得初始种群,并重新修改了原本的文化基因的编码以及相关操作,以便可以处理八角形斯坦纳树构建这一离散问题,利用八角形结构,使其能在全局范围内,快速收敛并全局寻优.实验结果表明,所提算法能获得较好拓扑的八角形斯坦纳树,快速得到多端线网最优或者较优的布线结果,缩减布线的线长.     

网格空间瓶颈斯坦纳树问题快速近似（英文）

指出了瓶颈斯坦纳树问题要求寻找一棵用至多k个斯坦纳点将n个点连接起来使得此斯坦纳树之最长边最短的斯坦纳树,该问题在VLSI、无线通讯网络和生命演化树重建等领域都有应用.Du和Wang证明网格空间瓶颈斯坦纳树问题是NP-Hard,不存在近似性能比低于2的多项式时间解决方案,并且提出一个近似性能比为2的多项式时间近似算法,算法的实际时间复杂度为O(nlog2n+kn+k2).通过引入二叉堆和斐波那契堆使算法的时间复杂度分别改进到了O(nlog2n+klog2n)和摊还时间O(nlog2n+klog2n).该改进可直接应用于欧几里得平面的瓶颈斯坦纳树2-近似算法.     

多目标优化问题的研究

针对传统方法求解多目标优化问题的局限性,应用一种新的算法求解。遗传算法从问题解的串集开始搜索,覆盖面大,可以同时处理群体中的多个个体,利于全局择优,减少陷入局部最优的风险,而最小生成树具有过程简单清晰、适用性广泛的特点,结合两者的优点,构造了基于生成树的遗传算法。首先通过加权目标规划法求出最优解,然后通过遗传算法和基于生成树的遗传算法求解,结果表明,对于小规模的多目标优化问题,两种算法都可以求出最优解,在求解时间方面,基于生成树的遗传算法比遗传算法更优越。     

最小代价归并树的动态规划实现

动态规划算法广泛应用于求解最优化问题中，通过对最小代价归并树问题的研究，构造出动态递归方程，分析其最优子结构以及重叠子问题性质，从而实现动态规划的过程分析，并用C程序生成最小代价归并树验证其有效性。     

折叠超立方体的广义3-连通度

设图G是一个连通图,S⊆V(G)。图G的一棵S-斯坦纳树是一棵包含S中所有顶点的树T=(V ',E '),使得S⊆V '。如果连接S的两棵斯坦纳树T和T ',满足E(T)∩E(T ')=且V(T)∩V(T ')=S,则称T和T '是内部不交的。定义κ(S)为图G中内部不相交S-斯坦纳树的最大数目。广义k-连通度(2≤k≤n)定义为κ_k(G)=min{κ(S)|S⊆V(G)且|S|=k},显然,κ₂(G)=κ(G)。证明了κ₃(FQ_n)=n,其中FQ_n是n-维折叠超立方体。     

一种基于链路优化的时延约束组播路由算法

研究具有时延约束的最小代价组播路由问题，提出一种基于链路优化的组播路由算法求解该问题。算法从最小时延树开始，不断地用低代价链路代替树中高代价链路，以求得满足条件的组播树。仿真实验结果表明，该算法能根据组播应用对时延的要求，快速、有效地构造最优组播树，具有较低的时延。     

12参双参数直角梯形板元的构造及收敛性分析

考虑特殊的四边形单元--直角梯形单元,构造出一类12自由度直角梯形板元;为了降低自由度,节省计算量,利用双参数法将自由度进行离散,得到一类双参数12参直角梯形板元.证明了该单元对薄板弯曲问题的收敛性.     

对给定谱系树的最优拟合

本文给出了两个求解给定谱系树最优拟合的递推公式。它适用于离散和连续的谱系树的最优拟合问题。还对有限离散的谱系树最优拟合问题,给出一种利用矩阵运算的求解方法。     

几何法在求解函数最值问题中的应用

本文通过挖掘求解最值问题的几何意义,构造出相应的几何模型,将函数最值问题转化为几何问题,针对不同问题运用构造向量、数形结合、构造曲线等方法求解最值,探求了解决问题的简捷方法,并结合实例探讨了利用几何方法求解一些函数的最值。     

重数为2r的正交对称多小波的构造

给出一类重数为2r的正交对称-反对称多小波的构造算法,即对任给长度为2N的对称-反对称正交多小波,通过本文所给的构造算法可以得到长度为2N 1的对称和反对称多小波.反之亦然.最后给出相应的例子.     

不变小波域内基于DWT的图像数字水印

 面对各种几何攻击,现有数字水印算法露出各种缺陷,到目前为止还没有发现真正能抵抗各种攻击特别是几何攻击的算法.利用具有旋转、伸缩、平移不变性的RST不变小波变换设计了一种新颖的基于量化边通信模型的DWT盲数字水印算法.实验表明,这种新颖算法对于旋转、伸缩、平移等普通几何攻击以及滤波与噪声等多种攻击具有较好的鲁棒性,但该算法对局部几何攻击具有一定的敏感性.     

旋转曲面变换PSO算法估计纹理图像MRF参数

快速准确地估计马尔可夫随机场的参数，通过拟似然函数可以将其参数估计转化为一个寻找全局极值的问题．粒子群优化算法应用于多极值点函数优化时，存在陷入局部极小点和搜寻效率低的问题．为此提出旋转曲面变换方法，将被优化函数映射到一个同胚曲面上，它将当前局部极小点变换为全局最大点，并保持被优化函数值在当前局部极小点以下部分的形状不变，从而克服陷入局部极小点问题．利用旋转曲面变换粒子群优化算法对充满局部极小点的目标函数求全局极值．用Gibbs采样器生成的纹理图像实验结果表明，利用这种方法估计马尔可夫随机场参数效果较好．     

一类构造线性最优设计的算法研究

对构造线性最优设计最常用的Fedorov算法进行了改进,得到了一类构造线性最优设计的新方法并给出了收敛性证明．     

一种基于Rough集的启发式人工选择算法

在传统二进制编码遗传算法(GA)的基础上,提出一种基于Rough集的启发式人工选择算子和人工选择算法。利用粗糙集对遗传算法的历史数据进行分析,发现重要基因位,获得重要模式信息,并以此为启发式信息,选择优秀模式进行人工育种,从而对复杂优化问题进行有效求解。采用该算法对典型测试函数进行了验证,算例结果表明,人工选择算法加速了常规遗传算法进化速度,提高了收敛效率。     

对称矩阵特征值反问题的最佳逼近解的一种数值解法

利用复合最速下降法,给出了对称矩阵特征值反问题AX=XΛ有解和无解两种情况下最佳逼近解的通用数值算法,对任意给定的初始矩阵A0,经过有限步迭代可以得到对称矩阵特征值反问题的最佳逼近解,并分别给出有解和无解两种情况下的数值实例,证明了此算法的可行性.另外,结合投影算法,可以用此算法来求解其它凸约束下矩阵特征值反问题的最佳逼近解,从而扩大了此算法的求解范围.     

可靠安全事务

本文提出了一个电子商务协议可靠安全事务(RST)从分布系统中借鉴了两段式提交,事务日志,时间戳的技术,试图使事务足够健壮.事务在公共网(如Internet)进行时的安全性则通过采用加密方法和电了证书的技术来获得描述RST的基本步骤.并在本文结尾,罗列了RST具有的某些特性.     

单台机器排序问题中工件的预排序

在排序问题中,为了寻找一个工件的加工次序,有时需要对原来工件进行重新编号,即对工件进行预排序.例如用动态规划求解工件有先后约束关系的单台机器排序问题时,需要对工件进行预排序,使得先加工的工件的序号小于它的后继工件的序号,且使得某种指标达到最优.对于工件之间的先后关系呈链状结构的单台机器排序问题,给出了一个算法,并证明了该算法是最优的.对于工件之间的先后关系呈树形结构的单台机器排序问题,也给出了一个算法,并证明了对于某些特殊的树形结构的单台机器排序问题,该算法是最优的.     

钢筋混凝土受弯构件的优化设计—一类离散型非线性规划

研究钢筋混凝土受弯构件的优化设计问题，建立了新的数学模型—一类离散型非线性规划，给出了计算步骤与若干算例．提出的算法容易在微机上实现，所有可行解都是整数解，而且所得最优值在一定条件下是总体最优值．