次模函数近似算法求最小颜色生成树

给定图G并对其进行边着色,G的最小颜色生成树（MCST）问题是指,找出G的一棵生成树,使得其边集所着颜色数最少.最小颜色生成数问题MCST已被证明是NP-、APX-完备的,从而此问题没有近似比为常数的近似算法.本文中,我们利用次模函数理论（贪婪算法的思想）给出最小颜色生成树问题的一个近似算法,且此算法的近似比为最好结果.     

由对换树生成的凯莱图的3-额外连通度

给定一个图G和一个非负整数g,若图G中存在(边)点集,使得删除该集合后图G不连通并且每个连通分支的点数大于g,所有这样的(边)点集的最小基数,称为g-额外(边)连通度(记作κg(G)(λg(G)).本文将确定由对换树生成的凯莱图的3-额外(边)连通度(记作κ3(λ3).     

基于遗传操作的延迟和度约束的多播路由启发式算法

基于启发式思想的简单性和路径相似性原理，采用遗传算法的交叉和变异操作，提出了一种快速的满足延迟和度约束的最小费用多播路由树的生成算法(DDCMRA)，以解决直接修改延迟约束或者度约束多播路由算法时寻优时间长、并且可能导致部分目的节点因不能满足延迟或者度约束而不能加入多播的问题．仿真结果显示。该算法获得的多播路由树满足延迟和度约束，费用较少，运行时间接近CSPT和RA算法．该算法也为动态多播路由树生成和网络负载平衡提供了一种方法．     

约束最小支撑树 ( C-MST)问题: 复杂性和上下界估计

本文首先建立了约束最小支撑树问题的模型 ,利用背包问题的复杂性 ,证明了该问题是 N P-完 全的 . 然后利用一个广义线性规划的对偶算法 ,对目标函数的上下界作出了估计 ,最后分析了解的平面 性质 .     

单位加工时间入树约束Open Shop 问题的多项式时间算法

本文研究具有单位加工时间及入树约束的Open Shop问题,提出了一个多项式时间算法,该算法根据入树约束的层次结构分批安排加工,使每批加工解除约束的工件数最多。文章证明,算法的计算量为O(n2)。     

基于最小平均复杂度的矢量量化音频分类方法

首先提出了“平均复杂度”的概念，然后由信息熵公式给出了最小平均复杂度的计算方法，并以此为准则构造音频数据的矢量量化树，从而得到音频数据在特征空间的分布情况．根据不同种类的音频数据有不同分布这一事实，比较未知音频与已知音频种类的数据在特征空间中的分布情况的近似程度，就可完成音频分类．实验表明，该方法具有适应性强、计算效率高的特点。     

变换图τ_2(G)连通度

M.Farber 等在[2]中引入了“边不交的生成树对”的变换图τ_2(G)的定义,证明了它是连通的.本文讨论了τ_2(G)的连通度,得到了一个下界.特别地,对于2-补树图,即恰含有两个边不交的生成树的图,本文先给出了一种递归方法去构造全体2-补树图,然后证明了2-补树图 G 的τ_2(G)的连通度≥|V(G)|-1,井给出了例子,说明这一下界是最佳可能的.     

当匹配数很小时具有最小拉普拉斯谱半径的树

考虑了具有最小拉普拉斯谱半径的树的问题. 并确定了当匹配数很小时具有最小拉普拉斯谱半径的树.     

经典组合优化问题的概率极限定理

本文对经典组合优化问题解的主要概率极限定理作一综述 ,并重点讨论零担售货员问题 ,极小生成树, 匹配和最长单调增子列长度. 涉及的概率极限定理包括强大数律,收敛速度,依分布收敛和大偏差原理. 没有提供详细证明, 文中包含了一些值得关注的问题.     

集值向量均衡问题近似有效解的最优条件

分析实局部凸Hausdorff拓扑向量空间一类具约束集值向量均衡问题的近似有效解,讨论其有效解和近似有效解的关系。在近似锥-次类凸集值映射概念的基础上,运用凸集分离定理,建立了有效解和近似有效解的最优条件。在广义凸性假设条件下,借助相应的分析方法,得到集值向量均衡问题近似有效解的Kuhn-Tucker型和Lagrange型的最优充要条件。     

约束Steiner最小树问题

本文首先提出一个约束Steiner最小树问题。设欧氏平面上直线L的一侧有n个点, 记点集为N,现要在L上找一点P,使关于N∪{P}的Steiner树长度最小。文章解决了n=2及n=3的情形。     

一种最佳二叉排序树的动态检索算法

给出了一种最佳二叉排序树的动态检索算法,其性能优于二叉排序树和平衡二叉树,克服了用折半检索方法构造最佳二叉排序树的缺点,且不会因插入结点而发生蜕变,影响检索的性能．     

针对k-匿名数据的判定树构造算法

数据挖掘问题是提高k-匿名隐私保护模型下数据可用性问题之一.通过分析发现,k-匿名表中准标识符属性值与利用精确表生成的判定树的部分非叶结点的属性值均是通过泛化产生的,根据这一对应关系,本文提出了一种基于k-匿名表的判定树生成算法.该算法直接以k-匿名表作为输入,避免了经典ID3算法运行前的数据准备工作.实验表明,该算法节省了建立概化层次树的时间,并且行之有效.     

预测RNA二级结构的一种遗传模拟退火算法

讨论了RNA二级结构的预测问题，首先提出一种用树表示RNA二级结构的方法，然后给出一种用于预测RNA二级结构的混合遗传算法——遗传模拟退火算法．在该算法中，个体(RNA二级结构)直接用茎序列编码，与个体用二进制串编码的同类型算法相比，在很大程度上缩短了个体的编码长度．计算结果表明该预测算法具有较高的精度．     

混合约束不可微非线性规划的L_1－精确罚函数法

在［１］中，我们提出了只含不等式约束的不可微非线性规划问题的Ｌ１精确罚函数法，给出了收敛性分析。本文提出解既含不等式约束又含等式约束的不可微规划问题的Ｌ１－精确罚函数算法，在目标函数上约束函数为半光滑的条件下给出了收敛性结果．     

云格环境下基于P2P的动态资源发现机制

为在云计算平台上实现大数据的高效并行处理与访问,针对动态增长的异构资源所具有的集成与共享所形成的超强计算力结合网格计算,从基于服务计算的角度分析了云计算与网格计算2个不同框架体系的集成问题,探讨了一种资源与服务的统一描述机制,提出了云格体系下的一种分组生成树的P2P网络动态资源与服务发现算法,可实现海量数据的高效处理与访问.实验表明该算法具有一定的可行性与针对性.     

一种求解约束条件下多变量非线性函数所有全局最优解的区间算法

研究和实践中经常会遇到附有约束条件的非线性优化问题，对这类问题，通常采用随机搜索的方法来解决，但是，随机搜索法不能证明所得到的解就是全局最优解．本文给出了一种求解约束条件下非线性优化问题所有全局最优点和最优值的区间算法，该算法非常宜于解决优化问题，它能求出问题的所有全局最优解，给出解的包含区间，并很容易获得解的逼近误差，这是随机搜索等其他方法做不到的．理论分析和数值结果均表明，区间算法是稳定而可靠的．     

三维迷宫的设计与建模

三维迷宫在难度和趣味性上达到了一个更高的水平.通过改进二维迷宫的生成算法,提出了循环迷宫的概念和迷宫复杂度公式.进而,提出一种基于四边形网格曲面的三维迷宫设计算法.该算法分3个步骤:首先,将给定的三维曲面四边形网格化;再确定迷宫的起点和终点,采用基于生成树的二维迷宫生成算法,在网格表面生成迷宫路径;最后,将迷宫实体化为三维结构,并与原始三维模型做布尔运算,得到三维迷宫.通过3D打印机制造出个性化的三维迷宫玩具,大大增强了迷宫的趣味性,改善了用户体验.