最小连通顶点覆盖问题的降阶回溯算法

本文从最小连通顶点覆盖问题的求解算法出发,提出一种基于该问题本身的数学性质的降阶回溯算法来求解。通过基于问题的数学性质来设计精确算法,不仅能够克服使用启发式算法求解该问题在一般情形下都无法求得最优解的缺点,也改善了该问题使用传统精确算法时最坏时间复杂度高的缺点。本文首先研究该问题的数学性质,部分数学性质可成批确定某些顶点在或不在最小连通顶点覆盖集中,从而降低该问题的规模,提高精确算法的求解速度。其次,在数学性质的基础上,设计出上下界子算法、降阶子算法、回溯子算法来求解该问题的最优解。最后,时间复杂度分析以及无线网络设计的实例分析表明,该算法不仅能求得该问题的最优解,且相对一般精确算法,本文算法的时间复杂度更低。

最小支配阈值集问题的降阶回溯算法

图论中的最小支配阈值集问题是组合优化中的一个NP-Hard问题,该问题是最小支配集问题的一个扩展问题。基于给定无向图G=(V,E)和阈值r的最小支配阈值集问题进行研究,首先得出一些可以降低问题规模的数学性质并证明,利用这些性质可以减小问题规模,降低问题的求解难度;然后设计出上界子算法、下界子算法和降阶子算法,并基于这些子算法提出了一种可以减小问题规模同时得到最优解的降阶回溯算法BAR;最后,通过一个示例分析和若干随机算例测试验证了降阶回溯算法可有效降低问题的求解难度。

严格对角占优M-矩阵的逆矩阵的无穷大范数上界的估计

设A为严格对角占优的M-矩阵,给出了‖A-1‖∞新的上界估计式,并由此给出了A的最小特征值q(A)下界的估计式.

最坏情况下Min-2SAT问题的上界

最坏情况下MaxSAT问题上界的研究已成为一个热门的研究领域.与MaxSAT问题相对的是MinSAT问题,在求解某些组合优化问题时,将其转化为MinSAT问题比转化为MaxSAT问题有着更快的速度,因此对MinSAT问题进行研究.针对Min-2SAT问题提出算法MinSATAlg,该算法首先利用化简算法Simplify对公式进行化简,然后通过分支树的方法对不同情况的子句进行分支.从子句数目的角度分析算法的时间复杂度并证明Min-2SAT问题可在O(1.134 3m)时间内求解,对于每个变量至多出现在3个2-子句中的情况,得到最坏情况下的上界为O(1.122 5n),其中n为变量的数目.

(2,2)-可视密存的最小象素方案

在 Naor和 Shamir提出的可视密存的基础上 ,给出了一种较简单的方案来解决 (2 ,2 ) -可视分存中的象素膨胀问题 .利用可视分存矩阵实现 (2 ,2 ) -可视密存并证明了此方案的有效性 ,进而得到了实现此方案的象素膨胀的最小上界 .同时给出了一个黑白象素分存时的一个选择原则 ,用它可增强分存图的对照度 .其结果是新的 .针对不同的象素膨胀值 ,编码密图“DES”.在附录中给出 (2 ,2 ) -可视分存的结果 ,它们看起来象随机图 .事实上 ,单一分存图 ,不能得到任何有关密图的信息 ,无论用什么方法和采用何种工具 .其密图的恢复只要重叠两张分存图的透明片 ,它不需要加密知识也不需要密码计算 .

多时滞区间矩阵系统的H^∞鲁棒控制

研究了系统矩阵、时滞矩阵和输入矩阵均含有不确定性的多时滞区间矩阵系统的 Ｈ∞鲁棒控制问题。文中首先针对时滞系统ｘ（ｔ）＝ Ａｘ（ｔ）＋ Δ Ａｘ （ｔ－ τ）在 Ａ 稳定条件下，运用根轨迹法，导出时滞系统稳定的条件；接着运用该条件及 Ｈ∞控制方法和实对称矩阵集合最小上界定理，设计了多时滞区间矩阵系统的 Ｈ∞鲁棒控制器。该设计方法把确定多个矩阵不等式共同解的复杂问题简化为求解单子代数 Ｒｉｃｃａｔｉ矩阵方程，所得多时滞区间矩阵系统的 Ｈ∞控制律，对于所有允许的不确定性，可使闭环系统稳定，且使系统从扰动输入到控制输出的传递函数具有 Ｈ∞范数界。文中算例表明了该方法的有效性。

严格对角占优M-矩阵的逆矩阵无穷范数的新上界

利用逆矩阵元素的范围,给出严格对角占优M-矩阵的逆矩阵无穷范数上界新的估计式,进而得到严格对角占优M-矩阵最小特征值下界的估计式,并给出了严格α-对角占优M-矩阵的逆矩阵的无穷范数新上界.理论分析和数值实例表明,新估计式改进了已有的结果.

严格对角占优M-矩阵的逆矩阵的无穷大范数的新上界

给出了严格对角占优M-矩阵的逆矩阵的无穷大范数上界新的估计式,进而给出严格对角占优M-矩阵的最小特征值下界的估计式.新估计式改进了已有文献的结果.

严格对角占优M-矩阵的逆矩阵的无穷大范数上界改进的估计式

设A为严格对角占优的M-矩阵,首先仅利用矩阵A的元素给出A-1的元素新的上界估计式,其次利用这些估计式给出了■A-1■∞新的上界估计式,并由此给出了A的最小特征值q(A)下界的估计式。这些新的估计式改进了已有的结果。

M-矩阵最小特征值的上界序列

M-矩阵最小特征值的估计是矩阵理论研究中的重要组成部分.如果上下界能够表示为关于M-矩阵元素的易于计算的函数,那么这种估计价值更高.通过构造3个收敛序列得到M-矩阵最小特征值的新界值.该方法易于计算且能得到较紧的界,数值算例表明其结果比有关结论更加精确.

严格对角占优M-矩阵的逆矩阵无穷大范数上界的序列

利用严格对角占优M-矩阵的逆矩阵元素的上界序列,得到了1A收敛的上界序列和q(A)收敛的下界序列。这些新的序列提高了现有关于该类问题的研究结果。

严格对角占优M-矩阵的||A^(-1)||_∞上界的新估计式

设A为严格对角占优的M-矩阵,首先仅利用矩阵A的元素给出A-1的元素新的上界估计式,其次利用这些估计式给出了||A-1||∞新的上界估计式,并由此给出了A的最小特征值q(A)下界的估计式.这些新的估计式改进了已有的结果.

严格α2对角占优M矩阵A的■估计式的改进

严格α2对角占优M矩阵是矩阵理论中重要的特殊矩阵之一,它被广泛应用于计算数学、经济学、生物学、密码学和智能科学等领域,尤其是数值计算中迭代系统的收敛性,运筹学中的线性互补问题,数理经济学中的Leontief模型,一般平衡的稳定性分析,网络计算中离散系统是否稳定等问题。针对该矩阵A的||A^-1||∞的上界估计问题,首先介绍了它的相关定义、符号和性质引理,借助矩阵A的元素特征,通过矩阵分裂的方法将A表示成严格对角占优矩阵B和对角矩阵F之差的形式,其次结合||A^-1||∞的范围和矩阵范数的性质,给出了||A^-1||∞的一个新估计式,进一步获得了矩阵A的最小奇异值的新下界,用理论分析和数值示例说明了所得估计式比已有的几个结果提高了估计的精度,且计算简单易行。

严格对角占优M-矩阵的逆矩阵的无穷大范数的上界估计

引入一组新的记号,给出严格对角占优M-矩阵及其逆矩阵元素关系的不等式,得到了逆矩阵的无穷大范数的上界估计式。给出矩阵A最小特征值的下界,从理论上证明了新估计式改进了某些现有文献的结果,同时数值算例说明了新估计式更精确。

基于失稳状态耗能最小原理的预应力锚索加固边坡稳定性上限解析

基于岩土塑性极限分析上限理论的基本原理,考虑预应力锚索的加固效应,分析了单预应力锚索加固措施条件下边坡的稳定性特性,并由此探讨了多预应力锚索共同加固边坡的稳定性能量分析方法。结合强度折减技术,采用内点迭代方法和序列二次规划优化迭代法对锚固边坡安全系数目标函数进行了能量耗散最小化意义上的优化计算。典型算例的分析计算表明:锚索加固效应可以有效地提高边坡的稳定性,预应力锚索设置位置对边坡安全系数、临界滑裂面位置和锚索长度有显著影响。综合考虑锚索设置位置对边坡安全系数和锚索长度的影响,单锚索的最优设置位置应位于边坡中下部区域。采用多排锚索加固既可以保证边坡的安全储备,也可有效避免局部稳定性问题。

不可约M-矩阵最小特征值的上下界

M-矩阵被广泛应用于数学物理、控制论、电力系统理论等领域,关于非奇异M-矩阵最小特征值的估计成为研究的热点;利用相似变换不改变矩阵特征值给出不可约非奇异M-矩阵最小特征值的上下界;该方法所得估计结果仅依赖于M-矩阵的元素,易于计算;最后通过数值算例表明新估计式在一定条件改进了现有的相关结果.

基于MUBF算法的微机械陀螺输出降噪方法

针对微机械(micro electro mechanical system,MEMS)陀螺输出漂移不确定性,提出采用最小上限滤波(minimum upper-bound filter,MUBF)算法实现MEMS陀螺输出信号降噪处理,该算法将漂移看作陀螺输出信号中的未知干扰,通过获取漂移变化方差上限,利用凸优化动态寻优得到角速率估计。相比卡尔曼滤波算法(Kalman filter,KF),MUBF算法可以在陀螺输出漂移模型未知的情况下工作,弱化陀螺信号降噪处理条件。陀螺静态和动态实验结果表明:MUBF算法能够有效降低陀螺噪声且优于KF算法降噪效果,该算法为MEMS陀螺降噪研究提供新思路。

M-矩阵的‖A^(-1)‖_∞及其最小特征值的新估计

根据M-矩阵的性质,结合无穷大范数的定义,对严格对角占优M-矩阵的逆矩阵的无穷大范数‖A-1‖∞的上界和最小特征值τ(A)的下界做了新的估计。理论分析和算例表明,这些新估计式改进了现有的一些结果。

关于图能量上界的注释

对一个简单连通图G V(,E)来说,其能量表示为图G V(,E)的邻接矩阵特征值的绝对值之和.在文献[1]中,Kinkar Ch.Das和Seyed A.Mojallal用定点个数、边数、团数以及顶点的最小度数给出了一个图能量的新上界.在计算验证中我们发现一点瑕疵,本文给予修正,并正确给出修正的图能量的上界.