求解最大完全子图的一种DNA算法

最大完全子图是图论中一个重要的问题。粘贴和删除模型是DNA计算的两个基本计算模型。利用改进的粘贴和删除模型给出求解最大完全子图的DNA算法。     

一种欠约束几何系统求解的图优化方法

针对一般几何约束系统欠约束状态下约束分解的多态性,对相应的有向图强连通子图提出了进一步分解的二部图匹配自适应优化处理策略,给出了主要算法,实现了欠约束系统的优化分解,有利于一般几何约束系统快速求解．     

RNA折叠中的最大公共嵌套子图

在嵌套线状图模型中,寻找ncRNA联配的最大公共二次结构,实际就是寻找其序列导出线状图的最大公共嵌套线状子图。通过对模型的简化,证明该问题在伪平嵌套线状图的情形下是NP-完全的,并给出求最大水平嵌套线状子图的近似算法。     

不含3正则子图的图的最大可能边数的下界

１９７４年，Ｅｒｄｏｓ和Ｓａｕｃｅｒ提出如下问题：设ｆ（ｐ）是ｐ个顶点的不含３正则子图的图的最大可能边数，确定ｆ（ｐ）。本文给出：（１）ｆ（ｐ）≥３ｐ－９，ｐ≥４；（２）ｆ（ｐ）≥３ｐ－５，ｐ≥３４。     

基于软约束满足理论的用户偏好建模方法

用户建模是电子商务领域的重要研究问题之一,但是到目前为止还没有非常有效的方法能够建模用户的动态偏好等特征。在分析电子商务领域用户偏好特征获取一般特点的基础上,提出基于实例的两阶段递增式用户偏好特征获取方法。并采用基于半环的软约束满足问题表示用户的各类偏好特征,将用户建模看成是潜在方案空间上施加一系列偏好约束的过程。提出不同的偏好约束类型以及利用偏好约束建立用户模型的过程,实现电子商务领域复杂用户偏好的灵活建模。     

日计划机车周转图智能编制方法的研究

给出了日计划机车周转图的约束满足优化问题模型及其智能求解算法,该模型以列车工作计划、机车技术作业时间、乘务员作息时间、１８点归位机车台数、检修机车最晚到达基本段时间及段备机车的最早可解备时间等作为约束条件,以减少机车在站停留时间作为目标．该模型的智能求解算法将启发式知识与回溯策略相结合,以求得日计划机车周转图的满意解．     

带约束最长公共子序列快速算法

带约束最长公共子序列(CLCS)问题有很深的生物学应用背景,常被用来表示同源基因序列相似性的度量,但计算CLCS时间代价很高,最早的CLCS算法的时间复杂度为O(rn4),目前,最快的CLCS算法的时间复杂性为O(rn2).运用对偶原理将带约束最长公共子序列问题转换为带约束最小覆盖集问题,并建立带权的ref树结构,构造包含约束序列的约束覆盖子集,约简带约束覆盖子集并从中搜索关键路径,再通过关键路径构造CLCS,该算法将算法时间复杂度提升到O(nlogn+(q+r)L),r是约束序列的长度,q是两序列序偶的个数,L是两序列的最长公共子序列(LCS)长度.     

具有约束的极小生成子图的一个算法

针对实际中的一类连接问题建立了网络模型，给出了便于计算机实现的算法，即：通过依次收缩各边简化网络Ｇ＝ （ Ｖ，Ｅ，Ｗ） ，最终得到最小生成树；然后恢复各边和顶点，从而得到了此类问题的最优解。     

简单平面三角剖分图中各生成两部子图的最大次

讨论了简单平面三角剖分图中各生成两部子图的最大次的取值范围,否定了郁星星提出的生成两部子图最大次的上界为常数的猜想,并且得到了下面的主要结果。（１）设Ｇ是简单平面三角剖分图,当ｎ＝３时,ａ０（Ｇ）＝１;当ｎ＝４时,ａ０（Ｇ）＝ａ１（Ｇ）＝ａ２（Ｇ）＝１;当ｎ≥５时,有２≤ａ０（Ｇ）≤ａ１（Ｇ）≤ａ２（Ｇ）≤「△（Ｇ）／」,且下界ａ０（Ｇ）－２能达到。⑵若ｌ是不小于３的整数,则（ａ）存在简单平面三角     

混沌图引力搜索算法求解压力容器约束问题

为解决运用混沌图引力搜索算法( CGSA: Chaotic Gravitational Constants for the Gravitational Search Algorithm) 难以计算经典的压力容器设计( PVD: Pressure Vessel Design) 约束优化问题,提出了一种改进的混沌图引力搜索算法( CGSA9 + ) 。首先,分析PVD 约束条件中各变量间的相互依赖关系,确定总体中各维度随机的先后依赖顺序; 其次,在继承CGSA 算法子代产生的规则基础上,更新越界子代的产生规则,借助当前全局最优解位置,优化子代产生规则; 最后,通过循环验证是否满足约束,进而求解与评估,得到最优解。对比实验表明,该新算法能有效解决PVD 约束优化问题,并具有较好的优化效果。     

具有距离限制的最大竞争能力选址问题

以现实生活中的最佳选址问题为背景,定义了一种新型的选址问题——具有距离限制的最大竞争能力选址问题,分析了此类问题的NP-困难性,并为之设计了一个启发式算法.     

最大熵剑桥算法的一种改进的约束条件

在最大熵剑桥算法中,提出了一种正方体约束条件代替通常的球体约束,讨论了两种条件在一定条件下的相互嵌套性,说明了正方体约束较之球体约束具有明显的优越性     

Consistent Algorithm for Multi-value Constraint with Continuous Variables

Mature algorithms for the Constraint Satisfaction Problem (CSP) of binary constraint with discrete variables have already been obtained for the application. For the instance of multi-value constraint with continuous variables, the approach will be quite different and the difficulty of settling will aggrandize a lot. This paper presents the algorithm for realizing global consistency of continuous variable. And this algorithm can be applied to multi-value constraint.     

图的最大独立集问题的模拟退火算法

给出了一种具有全局优化特性的改进的模拟退火算法 ,建立了图的最大独立集的模拟退火模型 ,研究了扰动的形成和算法参数的选取 ,并用计算机进行模拟 ,结果表明该算法是有效的     

有预算限制的最大并行流问题

改进了Garg N和Koenemarm给出的求解具有预算限制的最大并行流问题的近似算法，使得算法求出的目标函数值的近似性由原来的λ≥（1-ε）^3OPT改进为λ≥1／（1＋3ε）OPT，更接近最优值，而算法复杂性不变，给出数值例子，验证了算法改进的有效性。     

几何约束奇异性判定的残量扰动算法

针对几何约束奇异性的判定问题 ,分析了奇异性的内在特征 ,给出了奇异约束的 3个性质 ,在此基础上 ,提出了奇异性判定的残量扰动算法 ,为快速准确的几何约束识别和求解提供了理论依据和实现方法 .     

图分割在Singleton弧相容算法中的应用

基于原有SAC-MP算法,提出一种将图分割技术应用到SAC-MP算法中的一种新算法,该算法在执行时能充分利用图分割技术确定适当的k值,避免了由于k值的不确定带来的冗余操作和盲目性.实验结果表明,该算法在求解约束满足问题时效率较高.     

约束满足问题求解及ILOG SOLVER系统简介

首先综述求解约束满足问题的基本算法和搜索策略, 然后介绍ILOG SOLVER求解系统提供的类和函数的基本组成, 并给出用该系统求解的两个地图着色示例.     

图结构在文本聚类中的应用

提出了一种基于图结构的文本聚类方法,采用基于图结构的文本表示方法来构建文本的图结构模型,将一个文本映射为相应的图结构,通过最大完全公共子图的求解计算文本间相似度,并进行聚类。实验结果验证了该方法的有效性。