双网络中影响力凝聚子图发现算法

双网络由物理图和概念图构成，其中物理图和概念图共享网络结点集合而具有不同边集合.物理图中边表示结点间实际存在的关系；概念图中边表示结点间的相似程度，通常由计算得出.最近，从双网络中发现凝聚子图，即物理图中连通且概念图中稠密的子图受到研究者的广泛关注，在研讨会筹备、商品推荐和致病基因发现等真实场景中具有广泛应用.但现有研究鲜有考虑双网络中凝聚子图的影响力.为此：1）提出一种基于最小边权重定义的影响力凝聚子图，即影响力k-连通truss(k-ICT)子图模型.k-ICT子图模型能够有效刻画子图在双网络中的重要性且对低影响力边鲁棒. 2）由证明可知，发现影响力最大的k-ICT子图是NP-难的，因此提出一种基于概念图边等价类划分的CT索引结构.利用索引的概要图，能够根据不同的k值，快速发现包含所有k-ICT子图的候选子图. 3）提出了基于全局枚举删除和局部子图扩展的精确算法Exact-G kICT和Exact-LkICT，用于发现top-r具有最大影响力的k-ICT子图.通过大量在真实数据集上的实验，验证算法的高效性和有效性.     

开孔圆柱壳屈曲优化的均匀设计序列响应面方法

为了减少优化中原模型的分析次数,提高优化效率,提出一种序列二次响应面近似优化方法.该方法基于均匀设计建立一个由低精度的全局响应面和精度逐渐提高的局部响应面组成的近似模型,其中,全局响应面用于确定初始子区域,而局部响应面获得问题在子区域内的优化解;采用基于归一化优化解相对位置的运动极限新准则更新子区域,通过子区域内样本点的继承和增补构造响应面并求解,重复迭代过程,实现问题的优化求解.最后通过5组典型测试函数和一个工程设计问题的优化求解验证了文中方法的有效性——可以高效率地完成开孔圆柱壳最大屈曲载荷的优化设计,展现出求解高计算成本工程优化问题的良好应用前景.     

基于约束图分片求解DCOP的Agent组织结构

MAS中许多分布式推理问题可以建模为分布式约束优化问题(DCOP),解决DCOP的分布式算法已经成为MAS中的重要基础.已有的Adopt等算法通过对等的Agent之间的平等协商完成求解,强调了异步通信、分布计算与对解质量的保证,在求解问题的组织结构方面仍有改进余地.可以采用一种基于分散与集中相结合的思路,基于对约束图分片的方法及核心结点、通信主干道等概念,构造新颖的Agent组织结构,完成DCOP问题的异步、分布求解.在该组织结构下求解DCOP的算法可在效率、适应动态性方面得到改善,并将一个Agent一个变量和一个Agent多个变量的DCOP求解方法统一起来.     

几何约束有向图的规划分解研究

在基于有向图表达的几何约束系统中,几何约束的匹配方向、分布状态以及有向图中强连通分量的规模直接影响到整个约束系统的求解;如何对几何约束系统进行合理规划,得到正确有效的求解序列,是目前约束分解研究的重要内容。该文提出了一个规划分解算法,它针对欠约束几何系统的特点,能够优化约束的初始匹配方向,对于约束匹配过程中生成的强连通子图,通过调整约束匹配方向,自适应地改善约束分布,从而减小强连通子图的规模,以求得到几何约束系统正确而高效的求解序列。同时,基于规划分解算法,完成了约束的奇异性分析,提供了面向分解的奇异性分析算法。     

数值与符号的耦合约束求解模型

采用约束关系依赖图(CRDG)表达耦合约束之间的依赖关系,从而建立数值与符号耦合约束模型.提出耦合约束的求解算法:对CRDG进行最小独立子图分解,对存在耦合约束的子图用"孪生变量法"进行一阶解耦,对没有耦合约束的子图用传统方法进行独立求解,求解之后再对孪生变量进行等效性验算.该耦合约束模型及其求解算法拓展了传统约束理论,实现了教学求解和推理求解有机地结合.     

基于标识的特征造型原型系统的研究与实现

从特征造型软件开发的角度对参数化特征造型的一些关键技术进行了研究，并在ACIS几何平台上开发了一个参数化特征造型原型系统GDS。讨论了GDS的关键技术：基于标识的特征表示模型，标识子系统、统一二、三维约束的基于子图的草图设计及约束求解方法、基于约束依赖图的特征编辑算法等。     

一个基于变形映射的约束图有向化与求解方法

提出了变形映射和变形源的概念,给出一种基于变形映射的二维工程图约束图有向化与求解新方法.同时,提出一种基于变形映射的约束图有向化新方法,并在约束图分解的基础上,给出了一个基于复合节点及虚拟约束的约束图变形求解新算法.应用此方法,可提高约束图有向化的可靠性、降低计算复杂度,且能方便地求解带有循环约束的约束图.     

密集标志点集的拓扑保持变换方法*

在对自由特征模型参数化基础上,提出一种约束求解的新方法。该方法对自由特征形体定义点进行参数化,建立几何约束图,将约束问题分解为三角形约束和四面体约束两大类,分别进行求解,定义手向性规则,利用该规则将子问题组合为全局解。在自主开发的HUST-CAIDS（哈尔滨理工大学计算机辅助工业设计系统）中实现了本算法,并得到满足设计者需求的模型。     

自由特征模型约束求解研究*

在对自由特征模型参数化基础上,提出一种约束求解的新方法。该方法对自由特征形体定义点进行参数化,建立几何约束图,将约束问题分解为三角形约束和四面体约束两大类,分别进行求解,定义手向性规则,利用该规则将子问题组合为全局解。在自主开发的HUST-CAIDS（哈尔滨理工大学计算机辅助工业设计系统）中实现了本算法,并得到满足设计者需求的模型。     

求解三维装配约束闭环的投影变换方法

为避免直接迭代求解三维装配约束闭环带来的复杂非线性方程组,提出一种投影变换方法求解三维装配设计中的平面约束闭环问题.首先采用等价性分析方法消除伪装配约束闭环,运用无向图块分算法分解装配约束图;然后采用旋量理论将装配约束闭环子图转换为运动副约束图,通过分析运动副的特征参数确定可投影的装配约束闭环,并将其投影变换为二维几何约束系统;最后通过求解二维几何约束系统获得三维装配约束闭环的解.实例结果表明,该方法缩减了迭代求解的规模并降低了约束方程的复杂性,明显地提高了求解的效率和稳定性.     

基于并行约束规划的最大团识别研究

为提高大数据平台下大规模图例的最大团问题求解效率,提出一种基于并行约束规划的最大团识别算法.通过BMT图划分策略将一个复杂图例分割为若干个可独立计算的子图,并将其分配给Spark集群中的计算节点,每个计算节点采用约束规划方法对分割产生的子问题分别进行建模和求解,实现最大团问题的并行化处理.引入时间预测模型,设计基于任务运行时间预测模型的并行图划分方法,从而有效解决计算节点的负载均衡问题.实验结果表明,与基于BMC图划分策略的最大团并行识别算法相比,该算法具有更高的求解效率,可取得近似线性的加速比.     

Revisiting decomposition analysis of geometric constraint graphs

Geometric problems defined by constraints can be represented by geometric constraint graphs whose nodes are geometric elements and whose arcs represent geometric constraints. Reduction and decomposition are techniques commonly used to analyze geometric constraint graphs in geometric constraint solving.In this paper we first introduce the concept of deficit of a constraint graph. Then we give a new formalization of the decomposition algorithm due to Owen. This new formalization is based on preserving the deficit rather than on computing triconnected components of the graph and is simpler. Finally we apply tree decompositions to prove that the class of problems solved by the formalizations studied here and other formalizations reported in the literature is the same.     

混合式几何约束满足的研究

几何约束系统可以分为陈述式和构造式两类。为了使基于约束的设计更加符合使用要求,参数化CAD系统需要综合满足两类约束。文中研究了三维情况下和构造统一的约束满足策略,通过引入形状自由度的概念,将形状变化和集团变化统一处理。约束系统采用约束图来表示,各个子系统之间的层次结构利用约束层次树来表示。采用剪枝和凝聚相结合的策略实现了欠约束和完备约束系统的分解,使用解析法和数值法对约束进行求解。该策略已经在参数化CAD系统GEMS5．0的二维和三维上实现。     

二元约束满足问题求解的结点开销模型

提出了在二元约束满足问题中以搜索结点个数为衡量标准的求解开销模型,该模型被应用于随机二元约束满足问题的求解开销相变分析中,并且比较了模型所导出的理论开销和实际中的搜索结点个数、约束检查次数、求解时间3种衡量标准的开销之间的相似性.在模型的基础上，探讨了求解启发式减少求解开销的作用，给出了一个新的变量选择启发式.     

A Real-Time Performance Evaluation Model for Distributed Software with Reliability Constrains

In this paper, we propose an approach for the real-time performance analysis of distributed software with reliability constraints, called Athena. The approach is based on the real-time and reliability performance analysis of distributed program. In Athena, two important factors, imperfect nodes and the links reliability, are introduced. The algorithms proposed in Athena generates sub-graphs, counts the reliability of each sub-graph, calculates the transmission time for all the transmission paths of each data file, and computes response time of each data file with reliability constraint. In this way, the real-time performance of distributed software with reliability constrains can be evaluated.This paper is supported by National Science Foundation of China under grant 60273076.     

基于邻居信息聚合的子图同构匹配算法

图匹配在现实中被广泛运用,而子图同构匹配是其中的研究热点,具有重要的科学意义与实践价值。现有子图同构匹配算法大多基于邻居关系来构建约束条件,而忽略了节点的局部邻域信息。对此,提出了一种基于邻居信息聚合的子图同构匹配算法。首先,将图的属性和结构导入到改进的图卷积神经网络中进行特征向量的表示学习,从而得到聚合后的节点局部邻域信息;然后,根据图的标签、度等特征对匹配顺序进行优化,以提高算法的效率;最后,将得到的特征向量和优化的匹配顺序与搜索算法相结合,建立子图同构的约束满足问题（CSP）模型,并结合CSP回溯算法对模型进行求解。实验结果表明,与经典的树搜索算法和约束求解算法相比,该算法可以有效地提高子图同构的求解效率。     

对象族拓扑约束求解的研究

针对当前对象族模型在求解拓扑约束时存在的缺陷,提出一种求解拓扑约束的新方法,这种方法在求解拓扑约束时,把拓扑约束映射为布尔约束满足问题,通过用SAT求解器求解布尔约束来求解拓扑约束。实践证明,该方法不仅直接关联与拓扑约束指定的特征的语义,而且当模型中存在大量相交的特征时也是可行的,提高了拓扑约束求解的效率。