COMPUTING MAXIMUM CLIQUES OF CIRCULAR ARCS IN PARALLEL*

Given a set S of n proper circular arcs, it is required to identify a largest cardinality subset K[S] of S each two of whose members intersect. This paper describes an optimal parallel algorithm to compute K[S]. The algorithm is not based on any previously known sequential solution, and is designed for the CREW PRAM model of computation. It uses 0(n/logn) processors and runs in O(logn) time. An interesting feature of the algorithm is that it transforms the computational geometric problem at hand, to a problem involving computations on 0-1 matrices, and then transforms the latter back into a ray shooting problem in computational geometry.     

基于分辨函数的极大团搜索算法

寻找极大团是几何图论极为重要的基础研究问题之一。将分辨函数模型与极大团性质结合,定义了顶点的极大团分辨函数、顶点关于某顶点子集的布尔映射函数,得到了一些与极大团相关的重要性质与定理,证明了图的极大团搜索问题可快捷自然地转换为相对简单的分辨函数表达式约束,为设计极大团搜索算法提供了一种有效的理论依据与求解途径。进而引入约简树构造方法设计了基于分辨函数的极大团搜索算法,最后通过给定无向连通图实例说明了算法的可行性与有效性。     

空间极大co-location模式挖掘研究

空间co-location模式代表了一组空间特征的子集,它们的实例在空间中频繁地关联。挖掘空间co-location模式的研究已经有很多,但是针对极大co-location模式挖掘的研究非常少。提出了一种新颖的空间极大co-location模式挖掘算法。首先扫描数据集得到二阶频繁模式,然后将二阶频繁模式转换为图,再通过极大团算法求解得到空间特征极大团,最后使用二阶频繁模式的表实例验证极大团得到空间极大co-location频繁模式。实验表明,该算法能够很好地挖掘空间极大co-location频繁模式。     

一个大规模股市图交互式可视化分析系统

随着物联网、移动互联网、云计算以及各种数据自动采集技术的迅猛发展,许多领域迅速积累了大量具有图结构的可用数据。其中一个重要的图应用是股市图。如何分析股市图达到合理充分的投资决策支持一直是一个重要的课题。其中极大团(Maximal Clique)分析是分析股市图的一个重要方法。股市图的规模庞大,传统的极大团枚举算法仅仅罗列图中所有的极大团。但一个图中可以有指数级数量的极大团,而一支股票对应的点可以参与到任意多的极大团中。因此,传统的极大团枚举算法不能直接有效支持股市图分析。本文提出一个支持快速选择、自动分组及导航浏览三种股市图交互式可视化操作的大规模股市图分析系统。根据用户感兴趣的股市图节点,这三种股市图交互式可视化操作从股市图中快速枚举出与这些特定股票相关的极大团、查看这些特定股票之间的组合关系以及显示与这些特定股票相关的其他股票,是有效支持股市图分析的必要手段。同时基于对某些特定顶点或边相关的极大团枚举的需求,本文提出了从图中枚举出与特定顶点或边相关的极大团算法。我们使用真实数据验证了本文提出的算法的优越性。     

贝叶斯网络在空间机械臂故障诊断中的应用研究

空间机械臂在空间设施中广泛应用,如何准确快速判断其运行状态成为需要解决的重要问题。文中首先介绍了机械臂在国内外空间设施的应用背景,然后采用基于故障树与贝叶斯网络的故障诊断方法,包括：基于系统组成结构的故障树建模、贝叶斯网络转化、团树传播算法和最大后验估计(MAP)推理结果分析。最后利用单点故障实验和多点故障实验对所提方法进行了验证,结果表明将故障树分析和贝叶斯网络结合应用到空间机械臂故障诊断是有效的、可行的。     

智能搜索算法求解最大团问题研究

最大团问题MCP（Maximum Clique Problem）在国外得到了广泛的研究,在国内刚起步,是一类NP完全问题。传统的确定性算法不能有效地进行求解。定义了MCP;介绍了使用启发式算法求解MCP的研究进展;综述了几种典型的智能搜索算法;分析了使用这些典型算法求解MCP的基本思想;研究了这些智能算法在求解MCP时的特点及性能。     

图着色算法解决考试时间安排问题的优化

时间表问题是将有限的时间资源分配给多个对象的资源分配问题,它是一类具有多约束条件的组合优化问题。时间表问题已经被证明是一个NP完全问题。大学考试时间安排问题是时间表问题的一个应用,利用改进的图着色算法来处理大学考试的时间安排问题能够最大程度上使考试时间安排得更加人性化、合理化。实验测试表明,基于所给出的算法实现的考试时间安排系统具有良好的可行性、实用性和优越性。     

基于最大权团的曲面粗匹配算法

提出一种将曲面匹配问题转化为图论中的最大权团搜索问题、将最优的点对应关系用最大权团表示的曲面粗匹配算法,该算法分为点匹配、点对应图构造和最大权团生成等3个阶段.点匹配使用高曲率点和均匀采样点作为候选点,通过自旋图进行匹配计算,构造初始点对应集合;点对应图构造使用距离约束、法矢约束和唯一性约束构造图的边,并使用自旋图相关系数为顶点赋权值;最大权团生成使用基于分支限界的团搜索算法,从对应点图中提取出代表最优对应的最大权团.实验结果表明,文中算法稳定、有效、可扩展,能够进行部分曲面匹配,并且适用于欠特征曲面.     

n-太阳图的线图及全图的团覆盖数与团划分数

主要讨论ｎ－太阳图的线图及全图的团覆盖数和团划分数,得出了ｎ－太阳图的线图及全图的覆团盖数与团划分数相等且都是ｎ的倍数。     

基于多层Markov网络的信息检索模型

随着信息检索技术的不断发展,挖掘更加有效的信息来提高检索精度成为研究热点,已有的研究表明在检索过程中有效地融合各种信息将得到更好的检索效果。对一个具体查询而言,可以充分利用与已有查询的相关性、词语相关性和文档相关性等信息进行查询扩展和重构。基于这种思路,该文分别构造查询网络、词网络和文档网络,提出了多层Markov网络的信息检索模型,模型可以融合词间关系、文档间关系和查询间关系,为了有效降低计算量,给出了基于团计算模型。在标准数据集上的实验表明该文的模型能够有效融合三类信息,并较大幅度地提高检索效果。