论文部分内容阅读
图和超图可以用来表示事物间的复杂关联,综合了两者特征的超结构可以表达更为丰富的关联信息。图、超图和超结构的划分在并行计算、数据挖掘、大规模电路设计、交通规划等领域有非常重要的应用价值和发展前景。图划分的研究相对成熟,在此基础上的超图划分研究也非常热门,但是还有一些具有现实意义的超图和超结构划分问题没有得到广泛研究和解决。本文主要研究超图的连通划分、超图的负载均衡划分、超结构的连通均匀负载均衡划分以及超结构的距离均衡划分等四个问题的复杂性理论、模型、算法以及应用。本文的主要贡献在以下四个方面: 第一,研究超图的连通划分问题。主要考虑将一个超图划分为连通部分数最少的连通划分。这个划分问题实质上就是检测超图的连通分支并给出每个连通分支对应的点集的过程。在研究图的连通划分算法的基础上,给出超图连通划分的一种新方法:逻辑和的方法。由于超图的连通分支数与其生成的二部图的连通分支数相等,且连通分支一一对应,因而,本文还提出了一种基于生成二部图的超图连通划分算法。我们在随机生成的点数超过10,000的超图上验证比较了不同的超图连通划分算法,其中基于超图关联矩阵的逻辑和算法能最快给出精确解。 第二,研究超图的负载均衡划分问题。考虑将超图H=(V,H)的顶点集V划分为K个部分:{V1,V2,…,VK},最小化每个部分关联超边数的最大值。本文主要给出超图负载均衡划分目标函数最优值的上下界,以及取到下界的充分条件和必要条件。为了解决原问题,我们将超图负载均衡划分转化为一系列的逆问题,并为逆问题设计近似算法,从而转化为普通超图的负载均衡划分算法。在真实的文本数据集上验证了本文的负载均衡划分算法的有效性。 第三,研究超结构的连通均匀负载均衡划分问题。超结构的连通均匀负载均衡划分问题,是指将超结构的点集划分为K个部分,满足均匀和连通约束,求每个部分关联的最大超边数的最小值。基于超结构相关特性,建立了连通均匀负载均衡划分问题的非线性0-1整数规划模型,证明该问题是NP-难的。根据问题的连通、均匀性质,给出了一种不受限于超结构的点数的精确算法。该算法可以在多项式时间内求解超树的连通均匀均衡划分问题,并且在运行时间和解的准确度上优于现有的通用求解工具。 第四,研究超结构的距离均衡划分问题。超结构的距离均衡划分问题是将超结构的顶点集划分成K部分,每个部分的点数是均匀的,而且要最小化每个部分两点间的距离的最大值。本文定义了超结构中的距离和距离矩阵的概念,并建立了该问题的0-1二次规划模型。提出了一种基于K-means的划分算法,和一种逐次生成划分算法。通过实例验证了所提出算法的有效性。