首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 109 毫秒
1.
针对图割曲面重建算法计算量过大的难题, 根据代数多栅理论对图割计算过程进行多尺度分解, 仅对最后一级进行最大流计算, 其他级的标记值通过插值得到。首先, 根据点云法向和重建曲面法向的一致性构建能量函数; 其次, 将能量函数映射到三维权重图的顶点和边上; 然后, 定义顶点间的一致性并由此构造抽取矩阵, 以决定哪些图的顶点参与图割运算; 之后, 构造插值矩阵, 将最后一级图割计算结果逐级插值到第一级; 最后, 利用步进立方体算法得到重建曲面的三角网格表示。实验结果表明, 与窄带图割算法相比, 本方法计算速度更快, 当图的顶点数越多时速度提高得越多; 对于不均匀采样的点云数据, 重建效果更好; 其他情况下两者效果相当。  相似文献   

2.
经典近似算法求解最大割问题时,时间复杂度与图的复杂度呈正相关。为提高求解效率,使用量子绝热近似算法求解无向图最大割问题哈密顿量的基态,其基态对应该问题的最优解。该算法的时间复杂度不依赖于图的顶点个数及边的条数,可以在有限步骤内计算得到最大割解。基于ProjectQ量子软件进行编程模拟,建立由初始哈密顿量线性变化到最大割问题哈密顿量的演化路径,分析该路径下最大割问题哈密顿量期望值的变化,判断算法能否求出最优解。数值分析结果表明,量子绝热近似算法能够以较高准确率计算出最大割解,其求解3个顶点无向图和6个顶点无向稀疏图最大割问题的准确率为0.999 9,求解6个顶点无向完全图最大割问题的准确率为0.969 6。  相似文献   

3.
传统的聚类算法用于DNA微阵列数据分析时,多数只能生成一种聚类结果,无法识别出与多组不同基因表达模式相类似的基因。针对该问题,提出一种基于图论的聚类算法,采用一个有向无权图来描述需要分析的DNA微阵列数据,分别计算该图具有最小割权值和第二小割权值的图割。测试结果表明,该算法可以有效地探测聚类结果空间并输出一组可能性较高的聚类结果,与Fuzzy-Max、Fuzzy-Alpha、Fuzzy-Clust等聚类算法相比具有更高的准确性。  相似文献   

4.
参数为k的几乎树中的染色多路割   总被引:1,自引:1,他引:0  
李曙光  辛晓 《计算机科学》2010,37(2):246-249
染色多路割问题源于对等网络中的数据分片,是传统多路割问题的推广。给定颜色相关边赋权图G和G上若干特异顶点的局部染色,将该局部染色扩展到所有顶点上,使得两端点染不同颜色的边的权和最小。对于参数为k的几乎树,给出了多项式时间精确算法。也就是说,染色多路割问题是固定参数可解的,其中的参数k是使得G中任意双连通分支C成为树所要拿掉的最大边数。  相似文献   

5.
割点求解是图应用中的一个重要操作.深度优先搜索树算法可以解决割点求解问题.但是该算法存在缺点,导致它不能在实际问题中得到很好的应用.这是因为当今数据的两大特点,一是数据规模庞大,对于很多图操作提出了挑战性的要求;二是数据多变,每天数据的大量更新使得传统算法必须依据更新重复计算,浪费了时间和空间.深度优先搜索树算法的时间复杂度为O(|V|+|E|),其中,|V|和|E|分别为图的顶点的数目和边的数目.它能够很好地适应第1个特点,但是对于第2个特点该算法则无能为力.提出一种基于压缩的割点求解算法来解决这个问题.该算法通过点的朴素相似来压缩图,时间复杂度为O(|E|).在得到的无损压缩图上进行割点求解,同时在压缩图上动态地维护点和边的更新,在不解压图的情况下完成图的更新,在更新后的图上进行割点求解,极大地降低了时间和空间消耗.该压缩算法得到的压缩图对其他图操作同样适用.  相似文献   

6.
基于图割与均值漂移算法的脊椎骨自动分割   总被引:2,自引:0,他引:2  
为提高图割算法的效率并减少用户交互量,提出将图割与均值漂移算法结合应用的脊椎骨自动分割方法。该方法利用均值漂移算法产生的区域邻接图代替像素点图,从而大幅减少参与图割算法的顶点和边的数目,并有效利用了均值漂移良好的边界结构保持特性。实验结果表明,该方法有效地结合了两者的优点,提高了算法的精度和速度,并减少了用户交互量。  相似文献   

7.
平衡图分割是基本的组合优化问题之一,针对超大规模图高效实现高质量的平衡图分割仍然是一个极富挑战性的问题。提出了一种基于标签交换图分割算法,以最小化规格化割(normalized cut)作为优化目标,利用顶点标签交换迭代更新以达到平衡图分割;针对大规模图,引入采样技术,通过计算局部最优的方式提高算法效率,最后采用邻域抖动(VNS)策略抖动计算多个局部最优解,然后取其中最好的解近似作为全局最优解。实验结果表明,该算法分割得到的子图内密度较好,与最权威图分割算法METIS相比,算法求得的最小割质量更优。  相似文献   

8.
为提高图割算法对图像的分割效果,提出一种改进的模糊C均值聚类算法(FCMA)和图割分割算法相结合的图像分割方法。首先,用均值漂移算法将图像过分割成多个小区域(超像素),用得到的超像素代替像素点作为图的顶点,以相邻像素块间的关系为边构建图模型;然后,采用改进的模糊C均值(FCMA)算法对前景和背景的混合高斯模型分别进行聚类分析;最后,用最大流/最小割算法求取能量函数的全局最优解即得到图像的分割结果。实验结果表明,该方法在分割结果上具有较强的区域一致性及较为清晰、平滑的图像边缘,并且该方法对含有噪声的图像也能得到较好的分割结果。  相似文献   

9.
文中提出了一种基于IG图(Intersection Graph)点割的电路划分算法,引入IG图模型,根据电路中信号网络间的交互关系构建IG图,直接对电路信号网络IG图进行最小点割划分,从而实现对电路单元(模块)的划分.该算法既有效地解决了电路超图与图之间转换的一致性问题,又实现了点割目标值与直接电路划分目标值的一致性,IG图点割集的大小即为真实电路划分的目标值.此外,通过给每个电路网络赋权重的方式构建带权重网络交互图,实现对电路网络划分的面积平衡进行近似控制,满足电路划分对面积平衡的特殊要求.采用MCNC提供的标准电路测试数据进行测试,实验结果表明,基于IG图点割的电路划分算法较基于网络超图HDN划分的K-DualFM算法平均有3%~7.8%的提高;同时,基于IG图点割的随机优化算法ROP比基于超图划分的FM优化算法具有更强的全局优化能力,划分结果提高18%,比基于二部图匹配的点割优化算法提高36%,对较大规模数据划分优化效果更好.  相似文献   

10.
张伟  曾瑞弼  胡明晓 《计算机应用》2012,32(4):1116-1118
针对带权无向图的输出需用边长反映权值大小的问题,提出了一种基于遗传算法的带权无向图画图算法,通过对顶点坐标的编码进行交叉和变异来得到理想的节点坐标,变异算子结合了非一致性变异和单点邻域变异,并在适应度函数中运用顶点平均距离、边交叉数、多度顶点相关边夹角均匀度、边的权值长度比一致程度四个美学标准。实验结果表明,该算法画出的图形连线无交叉,分支清晰,权值—长度相合,能得到清晰、美观且能直观反映权值的可视化输出结果,可应用于带权无向图的可视化输出系统的设计。  相似文献   

11.
本文分析基于量子绝热近似的不同顶点的最大割问题求解.该算法将无向图的顶点等效为量子比特,各个顶点间的边等效为两个量子比特之间的耦合,边的权重值等效为量子比特间的耦合强度.采用Python语言编写算法程序,模拟了6–13个顶点的完全无向图的最大割问题求解情况.实验结果表明,当完全无向图顶点个数取为8,12,13,同时耦合强度为1.0时,所求解最大割问题哈密顿量的期望值不收敛.进一步调整模拟计算中量子比特间耦合强度数值,观察期望值变化.实验发现,对于顶点数为12的完全无向图,耦合强度取0.95时,其期望值获得收敛.对于顶点数为8和13的完全无向图情形,当耦合强度取0.75时,所计算得到的期望值随演化时间变化收敛.由此推测超过13个顶点的完全无向图在用量子绝热算法求解最大割问题时,可将量子比特耦合强度归一化到0.75左右,使期望值有效收敛.  相似文献   

12.
A graph G is the k-leaf power of a tree T if its vertices are leaves of T such that two vertices are adjacent in G if and only if their distance in T is at most k. Then T is the k-leaf root of G. This notion was introduced and studied by Nishimura, Ragde, and Thilikos motivated by the search for underlying phylogenetic trees. Their results imply a O(n3) time recognition algorithm for 3-leaf powers. Later, Dom, Guo, Hüffner, and Niedermeier characterized 3-leaf powers as the (bull, dart, gem)-free chordal graphs. We show that a connected graph is a 3-leaf power if and only if it results from substituting cliques into the vertices of a tree. This characterization is much simpler than the previous characterizations via critical cliques and forbidden induced subgraphs and also leads to linear time recognition of these graphs.  相似文献   

13.
针对分类变量相似度定义存在的不足, 提出一种新的相似度定义. 利用新的相似度定义, 将数据集抽象为无向图, 将聚类过程转化为求无向图连通分量的过程, 进而提出一种基于连通分量的分类变量聚类算法. 为了定量地分析该算法的聚类效果, 针对类别归属已知的数据集, 提出一种新的聚类结果评价指标. 实验结果表明, 所提出的算法具有较高的聚类精度和聚类效率.  相似文献   

14.
This paper develops an algorithm for finding all maximal complete subgraphs or cliques of an undirected graph. The algorithm is simple, and is based on a refinement of the technique of successive splitting described by Paull and Unger in the determination of maximal compatibles of states in the context of minimization of incomplete sequential machines. The proposed algorithm tends to reduce computation in generating the subgraphs for problems most generally encountered, particularly in relation to the applicability in sequential switching theory.  相似文献   

15.
基于谱方法的无向赋权图剖分算法*   总被引:2,自引:0,他引:2       下载免费PDF全文
在多水平方法初始剖分阶段提出了一种基于谱方法的无向赋权图剖分算法SPWUG,给出了基于Lanczos迭代计算Laplacian矩阵次小特征值及特征向量的实现细节。SPWUG算法借助Laplacian矩阵次小特征值对应的特征向量,刻画了节点间相对距离,将基于非赋权无向图的Laplacian谱理论在图的剖分应用方面扩展到无向赋权图上,实现了对最小图的初始剖分。基于ISPD98电路测试基准的实验表明,SPWUG算法取得了一定性能的改进。实验分析反映了在多水平方法中,最小图上的全局近似最优剖分可能是初始图的局部最  相似文献   

16.
Finding maximal homogeneous clique sets   总被引:1,自引:0,他引:1  
Many datasets can be encoded as graphs with sets of labels associated with the vertices. We consider this kind of graphs and we propose to look for patterns called maximal homogeneous clique sets, where such a pattern is a subgraph that is structured in several large cliques and where all vertices share enough labels. We present an algorithm based on graph enumeration to compute all patterns satisfying user-defined constraints on the number of separated cliques, on the size of these cliques, and on the number of labels shared by all the vertices. Our approach is tested on real datasets based on a social network of scientific collaborations and on a biological network of protein–protein interactions. The experiments show that the patterns are useful to exhibit subgraphs organized in several core modules of interactions. Performances are reported on real data and also on synthetic ones, showing that the approach can be applied on different kinds of large datasets.  相似文献   

17.
In this paper, we propose a clique-based sparse reinforcement learning (RL) algorithm for solving cooperative tasks. The aim is to accelerate the learning speed of the original sparse RL algorithm and to make it applicable for tasks decomposed in a more general manner. First, a transition function is estimated and used to update the Q-value function, which greatly reduces the learning time. Second, it is more reasonable to divide agents into cliques, each of which is only responsible for a specific subtask. In this way, the global Q-value function is decomposed into the sum of several simpler local Q-value functions. Such decomposition is expressed by a factor graph and exploited by the general maxplus algorithm to obtain the greedy joint action. Experimental results show that the proposed approach outperforms others with better performance.   相似文献   

18.
许多现实问题可以抽象成无向简单连通图的生成问题。为了从节点的度数序列得到所有可能的无向简单连通图,针对度数序列设计了适合用计算机实现的去点回溯算法,证明了算法的正确性,通过每一步去点回溯后的变化矩阵,得到生成无向简单连通图所需的邻接矩阵,并最终用计算机实现了该算法,解决了节点度数已知时无向简单连通图的生成问题。  相似文献   

19.
Mesh decomposition is critical for analyzing, understanding, editing and reusing of mesh models. Although there are many methods for mesh decomposition, most utilize only triangular meshes. In this paper, we present an automated method for decomposing a volumetric mesh into semantic components. Our method consists of three parts. First, the outer surface mesh of the volumetric mesh is decomposed into semantic features by applying existing surface mesh segmentation and feature recognition techniques. Then, for each recognized feature, its outer boundary lines are identified, and the corresponding splitter element groups are setup accordingly. The inner volumetric elements of the feature are then obtained based on the established splitter element groups. Finally, each splitter element group is decomposed into two parts using the graph cut algorithm; each group completely belongs to one feature adjacent to the splitter element group. In our graph cut algorithm, the weights of the edges in the dual graph are calculated based on the electric field, which is generated using the vertices of the boundary lines of the features. Experiments on both tetrahedral and hexahedral meshes demonstrate the effectiveness of our method.  相似文献   

20.
Approximating maximum clique with a Hopfield network   总被引:5,自引:0,他引:5  
In a graph, a clique is a set of vertices such that every pair is connected by an edge. MAX-CLIQUE is the optimization problem of finding the largest clique in a given graph and is NP-hard, even to approximate well. Several real-world and theory problems can be modeled as MAX-CLIQUE. In this paper, we efficiently approximate MAX-CLIQUE in a special case of the Hopfield network whose stable states are maximal cliques. We present several energy-descent optimizing dynamics; both discrete (deterministic and stochastic) and continuous. One of these emulates, as special cases, two well-known greedy algorithms for approximating MAX-CLIQUE. We report on detailed empirical comparisons on random graphs and on harder ones. Mean-field annealing, an efficient approximation to simulated annealing, and a stochastic dynamics are the narrow but clear winners. All dynamics approximate much better than one which emulates a "naive" greedy heuristic.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号