共查询到19条相似文献,搜索用时 87 毫秒
1.
数据结构是计算机科学的算法理论基础和软件设计的技术基础,在计算机领域中有着举足轻重的作用。本文以邻接矩阵作为图的存储结构,指出如何在计算机上实现克鲁斯卡尔算法,并分析所设计算法的时间复杂度。 相似文献
2.
Prim算法、Kruskal算法和Sollin算法是最小生成树的典型构造算法。这三个算法均基于贪婪策略。Prim和Kruskal算法在本专科数据结构课程中有详细的介绍,而Sollin算法涉及较少。本文基于边集数组这一存储结构,详细说明了Sollin算法的步骤与实现。 相似文献
3.
最小生成树的高效异步并行算法 总被引:1,自引:0,他引:1
在MIMD-SM并行计算模型上,本文给出了时间复杂性为O(n(n/p+logp))的最小生成树的异步并行算法,其中n,p(1≤p≤n)分别表示图的顶点数和处理机的个数。 相似文献
4.
本文基于三维网孔处理机阵列,运用分而治之策略和数据归约技术在加权无向图上给出了一种新的有效的最小生成树算法。 相似文献
5.
给定连通无向赋值图G=(V,E),|V|=n,|E|=m,当G的某边的赋值改变时,必引起其最小生成树的改变。本文给出了一个快速有效地求新的最小生成树的并行算法,时间为O(log m),处理器个数为O(m~(1/2)),计算模型为EREW-PRAM。预处理也仅需O(log~2m)时间O(m)个处理器,与求初始最小生成树的耗费一样。我们的算法的并行时间与处理四个数的乘积为O(m~(1/2) log m)(此问题已知最快的串行算法时间为O(m~(1/2)))。 相似文献
6.
刘欣 《计算机光盘软件与应用》2011,(9)
最小生成树是数据结构中图的一种重要应用,对于具有n个顶点的带权连通图可以建立许多不同的生成树.Kruskal算法和Prim算法是求最小生成树的常用算法.本文讨论了一种新的算法. 相似文献
7.
8.
最小连接问题在网络优化中有广泛的应用,找到快速有效的算法来构造最小生成树是解决问题的关键。该文提出了一种构造算法,在存储结构和排序方法两方面进行了改进。从理论上分析了算法的计算复杂度,并实际测试了算法运行时间。结果表明该算法较现有算法有了很大提高。 相似文献
9.
最小比率生成树是找出目标函数形式为两个线性函数比值最小的生成树,例如总代价与总收益比值最小的生成树。当不限制分母的符号时,这是一个NP-hard问题。在分析最小比率生成树数学性质的基础上,提出了最小比率生成树的竞争决策算法。为了防止算法陷入局部最优,采用edge_exchange操作来增加算法的搜索范围。为了验证算法的有效性,采用无关和相关两种策略产生测试数据,并使用Delphi 7.0实现了算法的具体步骤。 相似文献
10.
基于Prim算法和Kruskal算法的最小生成树优化研究 总被引:1,自引:0,他引:1
李仙玉 《计算机光盘软件与应用》2010,(3):95-95,94
文章从目前最常见的两种在图最小生成树算法,即Prim和Kruskal算法,展开了阐述和分析,运用了大量的数据和实例对这两种计算方法进行了分析和研究。通过试验并对Prim算法进行改进,从图中每个顶点的度数入手,采取删除某些无用边的思想方法,给出了一个寻找最小生成树的算法,使其能动态调整自身的性能,既适合于稠密图,又适合于稀疏图。 相似文献
11.
本文对KMB算法进行了改进,提出了一种快速的最小代价组播树算法,它只需使用一次PRIM算法,也不需要判断叶结点,从而快速地获得了最小代价组播树,减少了算法的运行时间。随机网络模型的仿真实验表明:该算法的计算时间远小于KMB算法,是一种快速、稳定、高效的算法。 相似文献
12.
已知一加权无向图G(V,E),|V|=n.本文基于网孔处理机阵列,运用分而治之策略和数据归约技术给出了一种新的最小生成树算法.此算法需O(n~2/p)时间,使用了O(p)个处理机(1≤p≤n).当p=n时,此算法仅需O(n)时间和O(n)处理机.而目前基于同一计算模型上此问题的最好算法需O(n)时间和O(n~2)个处理机,因而这里给出的算法在使用处理机数目方面改进了O(n)因子. 相似文献
13.
一种点边带权最小生成树的近似算法 总被引:1,自引:0,他引:1
在给定的一个除边有代价外点也有两种代价的图中,要求出一棵点边代价和最小的生成树。这个优化问题具有实际应用背景。证明了该问题是NP难的,并且也给出该问题的近似算法和近似度分析。 相似文献
14.
贾青慧 《计算机应用与软件》2012,29(5):48-49,80
度约束最小生成树问题是网络设计和优化中的一个NP-hard问题。提出一种求解网络G关于指定节点的最大度约束最小生成树的改进算法。算法在保证指定节点最大度的前提下,通过选取剩余边中权最小的边加入当前网络,得到网络G关于指定节点的最大度最小生成树,同时对算法的复杂度进行了分析。最后通过与其他算法的仿真比较,表明新算法的有效性和通用性。 相似文献
15.
委托授权具有动态性和细粒度授权等特性,解决了分布式授权的可扩展性问题.提出用带权有向图描述委托授权模型,并给出了形式化描述,设计了一种有向图的最小生成出树算法,解决了授权深度、环状授权和冲突授权等关键问题. 相似文献
16.
本文提中一种最小费用流算法,实现从两个正交的一维投影重建图象。该方法在寻找增值链的过程中,为网络各节点设置状态变量,用以记录当前增值链通过该节点允许的最大费用值,使算法只搜索可能增流的节点,从而提高了图象重建效率.该方法已成功地应用于医学同位素扫描图象的重建. 相似文献
17.
一种新的决策树归纳学习算法 总被引:79,自引:1,他引:79
本文不示例学习的重要分枝--决策树归纳学习进行了分析探讨,从示例学习最优化的角度分析了决策树归纳学习的优化原则,指出了以往的以ID3为代表的归纳学习算法所固有的缺陷,并提出了一种新的基于概率的决策树归纳学习算法PID,PID在扩展属性的选择上仍采用基于信息增益率的方法,但在树上的扩展过程中,采用属性聚类的方法进行树的支合并。PID得到的决策树在树的规模和分类精度上都优于ID3。 相似文献
18.
19.
聚类的边界是一种有用的模式,为有效地提取聚类的边界点,提出c-层近邻概念,将c-层近邻应用于二路生成树,能快速计算出每个对象的反向近邻值,从而根据反向近邻值提取聚类的边界。提出的基于二路生成树的边界检测算法(DBMST)在综合数据集和真实数据集的实验结果表明,该算法在含有噪声/孤立点的数据集上,能够快速有效地识别出聚类的边界。 相似文献