共查询到20条相似文献,搜索用时 62 毫秒
1.
针对网络设计和组合优化中的度约束最小生成树问题,基于第k最小生成树的求解算法,提出了一种求解网络G关于指定节点的最小k度生成树的新算法。该算法通过对网络G的最小生成树作最优可行变换,逐步构造出指定节点的度数越来越接近度约束k的最小i度生成树,最终得到了网络G关于指定节点的最小k度生成树。给出了算法实施的具体步骤,并证明了算法的正确性。最后通过仿真结果和一个运输实例,表明了该算法在解决度约束最小生成树问题中的有效性。 相似文献
2.
最小生成树算法是数据结构中,求网络模型耗费代价最优解的一个重要工具。现实生活中的连通网络模型复杂而多变,有时还需兼顾其它的目标,一棵最小生成树不足以解决问题,因此找出所有的最小生成树是很有必要的,在此提出一种新的寻找所有最小生成树的算法--最小差值法。无向连通图网络通过去掉连枝生成最小生成树,一个连枝加入最小生成树形成一个圈。这种算法是在一个圈中,用连枝的权与其它树枝的权分别作差,求最小差值。由最小差值是否为零,判断原有的最小生成树能否通过换进换出边,生成新的最小生成树。该算法能够有规律、高效率的寻找出所有的最小生成树。在找出的所有最小生成树方案中,选择符合实时情况的最小生成树方案,该方案即为网络耗费代价的最优解。 相似文献
3.
最小生成树算法是数据结构中,求网络模型耗费代价最优解的一个重要工具。现实生活中的连通网络模型复杂而多变,有时还需兼顾其它的目标,一棵最小生成树不足以解决问题,因此找出所有的最小生成树是很有必要的,在此提出一种新的寻找所有最小生成树的算法——最小差值法。无向连通图网络通过去掉连枝生成最小生成树,一个连枝加入最小生成树形成一个圈。这种算法是在一个圈中,用连枝的权与其它树枝的权分别作差,求最小差值。由最小差值是否为零,判断原有的最小生成树能否通过换进换出边,生成新的最小生成树。该算法能够有规律、高效率的寻找出所有的最小生成树。在找出的所有最小生成树方案中,选择符合实时情况的最小生成树方案,该方案即为网络耗费代价的最优解。 相似文献
4.
一种新的基于最小生成树的物流配送优化路线算法 总被引:1,自引:0,他引:1
杨跃武 《计算技术与自动化》2008,27(3):7-11
提出一种基于树理论算法的物流配送线路优化决策,首先将复杂的道路网转化成最少生成树并建立优化转移策略,开发由最少生成树构造最小生成树的算法,通过对最小生成树进行标记的方法最后得到最优路径,使物流配送的周转总量最小。算法用Jbuilder9开发,运行表明所提出的算法是有效的,简化以往算法的复杂程度。 相似文献
5.
图的最小生成树问题是网络优化中的一类基本问题。目前构造最小生成树的算法都是基于传统计算机的算法如Prim算法和Kruskal算法。该文提出了一个用于构造图的最小生成树的量子算法,它结合量子搜索的方法和经典Kruskal算法的思想,对于n个节点m条边的图,依次搜索出n-1条边使它们构成一棵最小生成树。这一算法的时间复杂性为O(nm√)。与经典Kruskal算法相比,在同等条件下,该文的算法有较快的加速。 相似文献
6.
7.
求解最小生成树问题被广泛应用于求解现实中的搜索相关问题。然而现实瞬息万变,一个连通网络的节点常常发生变动。而一旦发生改变,传统算法必须要再次计算最小生成树。但是虽然节点发生了变动,最小生成树未必全部发生改变,这就造成了不必要的浪费。鉴于此提出一种基于Kruskal算法和Prim算法的最小树更新策略,对Kruskal算法和Prim算法做了改进,使其不必重新计算也能在连通图发生改变时更新最小生成树。 相似文献
8.
通过研究模糊权值网络中的最小生成树问题,使用基于模糊数的结构元加权序和经典最小生成树问题的改进权矩阵法,本文提出一种求解边权值为三角模糊数的模糊权值网络最小生成树问题的矩阵算法,并对算法的复杂度和正确性进行分析。通过实例验证了该算法的有效性。 相似文献
9.
贾青慧 《计算机应用与软件》2012,29(5):48-49,80
度约束最小生成树问题是网络设计和优化中的一个NP-hard问题。提出一种求解网络G关于指定节点的最大度约束最小生成树的改进算法。算法在保证指定节点最大度的前提下,通过选取剩余边中权最小的边加入当前网络,得到网络G关于指定节点的最大度最小生成树,同时对算法的复杂度进行了分析。最后通过与其他算法的仿真比较,表明新算法的有效性和通用性。 相似文献
10.
一种分布式数据库多元连接查询优化算法及改进 总被引:18,自引:1,他引:18
论文对于分布式数据库中的多元连接查询提出了一种优化算法。该算法产生的操作序列具有全局优化特征。在远程网中,采用最小生成树算法,生成最佳的连接序对能使得总的代价达到最小。而在局域网中,采用改进的最小生成树算法,生成尽可能多的并行连接序对,最大程度地应用并行性,使得响应时间最小。 相似文献
11.
基于Rough集的规则学习研究 总被引:9,自引:1,他引:8
Rough Sets方法是一种处理不确定或模糊知识的重要工具,本文在对Rough Sets理论进行深入研究的基础上,提出了一种基于Rough Sets的自增量学习算法,该算法利用简化的差异矩阵和置信度,能较好地进行确定性规则和非确定性规则的学习。 相似文献
12.
基于密度加权的粗糙K-均值聚类改进算法 总被引:7,自引:1,他引:7
针对粗糙K-均值聚类算法中类均值计算式的特点,提出了一种改进的粗糙K-均值算法.改进后的算法基于数据对象所在区域的密度,在类的均值计算过程中对每个对象赋以不同的权重.不同测试数据集的实验结果表明,改进后的粗糙K-均值算法提高了聚类的准确性,降低了迭代次数,并且可以有效地减小孤立点对聚类的影响. 相似文献
13.
聂林娣 《数字社区&智能家居》2009,(9)
数据挖掘是近年来数据库领域中出现的一个新兴研究热点,它是从大量数据中获取知识。进行数据挖掘的方法很多,粗糙集方法便是其中的主要方法之一。属性约简算法是基于粗糙集理论的数据挖掘模型中的关键步骤,同时也是粗糙集理论研究中的一个研究重点。通过对粗糙集理论的属性约简算法的深入研究,本文提出了一种改进的属性约简启发式算法。该算法建立在可辨识矩阵计算基础上。改进算法基于Hu的算法与Jelonek算法,在计算可辨识矩阵的基础上,保证最终能够找到决策信息系统的一个约简,同时较Jelonek算法相比,运算时间明显减少。 相似文献
14.
15.
本文就粗糙集理论及其在数据挖掘中的应用方法进行了较为深入系统地研究。重点研究了扩展粗糙集模型;基于连续属性的粗糙集模型及其约简算法;不完备信息系统下粗糙集模型及其约简算法;以及更一般的集值信息系统及其约简算法。 相似文献
16.
本文就粗糙集理论及其在数据挖掘中的应用方法进行了较为深入系统地研究。重点研究了扩展粗糙集模型;基于连续属性的粗糙集模型及其约简算法;不完备信息系统下粗糙集模型及其约简算法;以及更一般的集值信息系统及其约简算法。 相似文献
17.
周涛 《计算机工程与应用》2010,46(26):7-10
粗糙聚类是不确定聚类算法中一种有效的聚类算法,这里通过分析粗糙k-means算法,指出了其中3个参数wl,wu和ε设置时存在的缺点,提出了一种自适应粗糙k-means聚类算法,该算法能进一步优化粗糙k-means的聚类效果,降低对“噪声”的敏感程度,最后通过实验验证了算法的有效性。 相似文献
18.
19.