共查询到20条相似文献,搜索用时 15 毫秒
1.
针对串行算法模型下基于顶点遍历图的情况,提出了一种在CREWPRAM并行模型下遍历无向图的算法。该算法是找出无向图的一棵最短路径生成树,由向上和向下两条有向边替换最短路径生成树的每条边形成欧拉回路,运用欧拉回路技术计算前缀和,前缀和所对应的顶点即为遍历无向图的顺序。得出了该算法时间复杂度为O(n+logn)的结论。 相似文献
2.
本文分析基于量子绝热近似的不同顶点的最大割问题求解.该算法将无向图的顶点等效为量子比特,各个顶点间的边等效为两个量子比特之间的耦合,边的权重值等效为量子比特间的耦合强度.采用Python语言编写算法程序,模拟了6–13个顶点的完全无向图的最大割问题求解情况.实验结果表明,当完全无向图顶点个数取为8,12,13,同时耦合强度为1.0时,所求解最大割问题哈密顿量的期望值不收敛.进一步调整模拟计算中量子比特间耦合强度数值,观察期望值变化.实验发现,对于顶点数为12的完全无向图,耦合强度取0.95时,其期望值获得收敛.对于顶点数为8和13的完全无向图情形,当耦合强度取0.75时,所计算得到的期望值随演化时间变化收敛.由此推测超过13个顶点的完全无向图在用量子绝热算法求解最大割问题时,可将量子比特耦合强度归一化到0.75左右,使期望值有效收敛. 相似文献
3.
4.
基于谱方法的无向赋权图剖分算法* 总被引:2,自引:0,他引:2
在多水平方法初始剖分阶段提出了一种基于谱方法的无向赋权图剖分算法SPWUG,给出了基于Lanczos迭代计算Laplacian矩阵次小特征值及特征向量的实现细节。SPWUG算法借助Laplacian矩阵次小特征值对应的特征向量,刻画了节点间相对距离,将基于非赋权无向图的Laplacian谱理论在图的剖分应用方面扩展到无向赋权图上,实现了对最小图的初始剖分。基于ISPD98电路测试基准的实验表明,SPWUG算法取得了一定性能的改进。实验分析反映了在多水平方法中,最小图上的全局近似最优剖分可能是初始图的局部最 相似文献
5.
许多现实问题可以抽象成无向简单连通图的生成问题。为了从节点的度数序列得到所有可能的无向简单连通图,针对度数序列设计了适合用计算机实现的去点回溯算法,证明了算法的正确性,通过每一步去点回溯后的变化矩阵,得到生成无向简单连通图所需的邻接矩阵,并最终用计算机实现了该算法,解决了节点度数已知时无向简单连通图的生成问题。 相似文献
6.
7.
等价类学习是贝叶斯网络结构学习的一个重要分支,而本质图是贝叶斯网络等价类的图形表示,是进行等价类学习的有力工具。针对求解贝叶斯网络结构本质图存在的繁琐问题,提出了一种构建贝叶斯网络本质图的组合算法。该算法从初始非循环有向图开始,对所有有向边进行排序,保持V-结构中的边不变,将不参与V-结构的有向边转化为无向边,依次根据三条规则判定各条无向边在本质图中的方向。给出了算法的理论证明,通过具体案例分析验证了算法的有效性。 相似文献
8.
关联规则挖掘中对Apriori算法的一种改进研究 总被引:2,自引:0,他引:2
通过对关联规则挖掘算法的详细分析,提出了一种基于无向项集图的动态频繁项集挖掘算法.当事务数据库和最小支持度发生变化时,该算法只需重新遍历一次无向项集图即可得到新的频繁项集.该算法不仅简单、只需扫描一次数据库,而且还具有搜索速度快、节省内存空间等优点. 相似文献
9.
首先研究了任意无向不加权图情况下的极小K点连通扩充算法,在此基础上提出无向加权图G总边数和各点的连通度均保持不变时,使图G的总权值变小的一种可行边交换方法;同时得出一个可行边交换的引理.最终推出了任意无向加权图K点连通最小扩充的模拟退火算法. 相似文献
10.
苏蕴 《数字社区&智能家居》2010,(6)
通过对工艺尺寸链解算原理的分析,结合图论提出了计算机辅助解算工艺尺寸链的一种新的方法。该方法利用建立无向图来存储各尺寸环的数据信息及其之间的位置关系,最后通过对无向图的遍历达到求解工艺尺寸链的目的。 相似文献
11.
《国际计算机数学杂志》2012,89(3-4):207-220
The number of internal stability or independence number of an undirected graph has many important applications. Computationally it belongs to the class of intractable problems known as NP-Hard. In this paper we develop a tree search algorithm to determine the ndependence number of an undirected graph. Extensive computational experience on 2400 randomly generated graphs ranging from 20% to 90% densities and from 50 to 200 vertice has shown that the proposed algorithm is very effective. 相似文献
12.
Yung H. Tsin 《Theory of Computing Systems》2007,40(2):125-142
A simple linear-time algorithm for finding all the
3-edge-connected components of an undirected graph is presented.
The algorithm performs only one depth-first search over the given
graph. Previously best known algorithms perform multiple
depth-first searches in multiple phases. 相似文献
13.
14.
针对分类变量相似度定义存在的不足, 提出一种新的相似度定义. 利用新的相似度定义, 将数据集抽象为无向图, 将聚类过程转化为求无向图连通分量的过程, 进而提出一种基于连通分量的分类变量聚类算法. 为了定量地分析该算法的聚类效果, 针对类别归属已知的数据集, 提出一种新的聚类结果评价指标. 实验结果表明, 所提出的算法具有较高的聚类精度和聚类效率. 相似文献
15.
16.
17.
最小顶点覆盖问题是组合最优化问题,在实际应用中有较广泛的应用,是一个NP难问题。论文针对最小顶点覆盖问题给出了一种混合化学反应优化求解算法。首先根据无向图的邻接矩阵表示法,设计了参与化学化反应的分子编码和目标函数;同时把贪心算法思想创造性地融入到化学反应优化算法的四个重要反应算子中,以加快局部较优解的搜索过程;最后通过模拟化学反应中分子势能趋于稳定的过程,在问题的解空间中搜索其最优解。模拟实验结果表明,该算法对于求解无向图的最小顶点覆盖问题是有效的,并且在求解效率等方面有一定的改善。 相似文献
18.
19.
Hai-LongYao Yi-CiCai QiangZhou Xian-LongHong 《计算机科学技术学报》2005,20(2):0-0
Crosstalk noise is one of the emerging issues in deep sub-micrometer technology which causes many undesired effects on the circuit performance. In this paper, a Crosstalk-Aware Routing Resource Assignment (CARRA) algorithm is proposed, which integrates the routing layers and tracks to address the crosstalk noise issue during the track/layer assignment stage. The CARRA problem is formulated as a weighted bipartite matching problem and solved using the linear assignment algorithm. The crosstalk risks between nets are represented by an undirected graph and the maximum number of the concurrent crosstalk risking nets is computed as the max clique of the graph. Then the nets in each max clique are assigned to disadjacent tracks. Thus the crosstalk noise can be avoided based on the clique concept. The algorithm is tested on IBM benchmarks and the experimental results show that it can improve the final routing layout a lot with little loss of the completion rate. 相似文献
20.
摘 要:节点相似度是图聚类算法的重要基础,在基于结构-属性图聚类现有方法中,由于传统图模型的限制,需要多次矩阵相乘来调整属性边的权值,算法执行效率低。为解决这一问题,提出了结构-属性平衡图的概念,并采用随机游走模型策略统一度量结构-属性平衡图GB中顶点间的相似度。与现有方法相比,该方法不但能测量直接相连的顶点之间的相似度,还可测量不直接相连而存在不同长度的路径的顶点之间的相似度,且没有增加原相似度矩阵的规模,节省了大量存储空间,提高了算法执行效率。 相似文献