共查询到20条相似文献,搜索用时 187 毫秒
1.
简单介绍了最小生成树和最小Steiner生成树的概念,通过实例(有线通讯网络问题)提出了一种求解最小Steiner生成树问题的遗传算法。试验结果表明,该算法能够收敛到全局近似最优解。 相似文献
2.
最小生成树问题在很多工程应用方面发挥了重要的作用,Prim算法是最小生成树较为普遍使用的算法之一。针对Prim算法在分析和解决问题时,需要的时间复杂性进行了分析和验证,得出了最低时间成本,此研究成果对使用Prim算法进行计算机求解的过程有一定的指导意义。 相似文献
3.
杨跃武 《湖南农业大学学报(自然科学版)》2008,(3)
提出一种基于树理论算法的物流配送线路优化决策,首先将复杂的道路网转化成最少生成树并建立优化转移策略,开发由最少生成树构造最小生成树的算法,通过对最小生成树进行标记的方法最后得到最优路径,使物流配送的周转总量最小.算法用Jbuilder 9开发,运行表明所提出的算法是有效的,简化以往算法的复杂程度. 相似文献
4.
《山东农业大学学报(自然科学版)》2017,(6)
本文提出了一种Retinex和改进的最小生成树分割相结合的算法,能够准确地从模糊航拍图像中提取出河流。首先,通过多尺度Retinex(MSR)算法增强图像,然后基于形状先验和改进的最小生成树分割算法检测出主要河流。分别测试了各种不同模糊航拍河流图像,比较了四种众所周知的图像增强算法和四种常用的图像分割算法。结果表明:若没有MSR的图像增强,单一的最小生成树算法无法准确地提取模糊航拍图像中的河流;新算法对模糊或光照不均的河流图像,与传统算法比较有着明显的检测效果。 相似文献
5.
6.
针对天然气集输管网的优化问题,采用K-means聚类算法对天然气田区域内的井口进行分簇,在Prim算法的基础上提出了惩罚最小生成树算法,建立了天然气集输管网规划模型,并给出了天然气管网规划代价函数,采用迭代逼近的思想,从全局优化的角度,对天然气集输管网规划问题进行研究,借助SPSS与Matlab软件对模型进行了程序实现。结果表明:利用惩罚最小生成树模型规划的天然气集输管网与传统星枝状结构的天然气管网相比代价更小,具有一定的可行性与灵活性,能够为天然气集输系统的工程建设与成本优化提供参考依据。 相似文献
7.
简要介绍分布式查询优化的过程和目标,分析了基于半连接查询的代价估算方法,提出了基于并行性的查询优化算法,该算法采用改进的最小生成树算法,生成尽可能多的并行连接序对,最大程度地应用并行性,使得响应时间最小。分析试验表明,多元连接查询的并行执行是提高算法性能的有效方法。 相似文献
8.
9.
目的安全检查在工业生产中不可或缺,是发现和消除事故隐患、落实安全措施、预防事故发生的重要手段。为提高巡检的效率,优化资源配置,通过建立数学模型以达到花费最短的时间和最少的人力完成巡检任务。方法通过对模型的假设及简化,建立目标规划模型,运用Kruskal算法找出连通图的最小生成树,运用Floyd算法找出最短路径,使用MATLAB、LINGO编程对建立的模型进行求解。结果在问题1中,运用Kruskal算法找出最小生成树后,经过分析计算,以调度中心XJ—0022为树根对最小生成树粗略划分为4个子图,运用Floyd算法找出每位工人的最短巡检路径,建立目标规划模型,再使用MATLAB及LINGO,确定每班4人为最优,并给出了最优巡检线路和巡检时间表。在问题2中,若增加休息和吃饭时间,经过分析讨论后每班应有6名工人。根据第一问的算法思想求出每位工人的最短巡检路径,经过软件求解,给出了最优巡检线路和巡检时间表。在问题3中,若要把问题1中的固定上班改为错时上班,反而会增加人力成本,不可取。对问题2,把上班时间进行如下调整:3∶00-11∶30、11∶30-19∶00、19∶00-3∶00,这样每班5个人就可以完成工作,此种方法比固定上班可节省3人。结论通过建立数学模型,并对模型的求解,最终解决了问题,花费最短的时间和最少的人力完成巡检任务。 相似文献
10.
MasonIri论证了网络最小流问题可以在多项式时间内转换为哈密顿问题的模型与方法。本文利用一个反例指出了在该证明中使用的模型存在有不严格的地方。在此基础上,利用网络最小生成流的概念提出了一个修正模型,并证明了无环最小生成流问题可以在多项式时间内转换为哈密顿圈问题。文中最后指出,这一新的模型为解决在有向图内构造哈密顿轨的有效算法提供了一个新的思路和方法 相似文献
11.
数据结构主要研究数据之间的逻辑关系、数据的存储方式以及对数据的各种操作.最小生成树是数据结构中图的一种重要应用,算法与数据结构关系密切.本文以邻接矩阵作为图的存储结构,指出如何在计算机上实现克鲁斯卡尔算法,并分析所设计算法的时间复杂度. 相似文献
12.
基于"船舶拟人智能避碰决策"理论基础,采用船舶相对运动几何分析与仿真试验相结合的方法,着重研究多艘船舶陷入紧迫危险局面下,避让重点船的智能避碰决策及其实施方案的校验与优化算法;借助航行安全与自动避碰(NSACA)仿真测试平台进行仿真实验,验证了理论分析结果的正确性. 相似文献
13.
路径诱导是一种主动引导车辆合理分流来解决城市交通拥堵的方法.本文提出了一种基于增量搜索的多目标优化路径诱导方法.该方法首先利用图论法将复杂路网抽象为点线的赋权图,引入多目标优化变量,建立路网模型;然后在启发式搜索基础上引入增量搜索,结合全局规划和局部动态重规划,实现车辆的实时路径诱导.仿真结果表明该方法能有效地解决复杂路网中车辆的实时路径诱导问题. 相似文献
14.
Floyd最短路径算法在配送中心选址中的应用 总被引:13,自引:1,他引:12
胡桔州 《湖南农业大学学报(自然科学版)》2004,30(4):382-384
以最少物流费用为最优目标的配送中心选址的定量技术颇多,其中,最优化规划法及图论方法是研究热点.阐述了Floyd全部顶点间最短路径算法选址的原理,并通过实例讨论了配送中心选址算法的步骤及MATLAB程序实现的全过程. 相似文献
15.
图论作为数学的一个分支,在各种科学分支、工程技术领域及社会科学中有着广泛的应用。笔者把图论的思想和方法与农业经济中的实际情况结合起来,将复杂的经济问题转化为简洁的图论问题。 相似文献
16.
基于图论的带模糊约束最小费用与最小时间问题 总被引:1,自引:0,他引:1
为了寻求工程实施中费用与时间的最小化问题,在构造多因素隶属度PERT图和建立隶属函数模型的基础上,给出了最短路径的算法,并运用模糊约束量来解决带最小化时间因素的最小费用流问题。同时,给出了相应的数学模型及算法。 相似文献
17.
A near-optimum parallel planarization algorithm is presented. The planarization algorithm, which is designed to embed a graph on a plane, uses a large number of simple processing elements called neurons. The proposed system, composed of an N x N neural network array (where N is the number of vertices), not only generates a near-maximal planar subgraph from a nonplanar graph or a planar graph but also embeds the subgraph on a single plane within 0(1) time. The algorithm can be used in multiple-layer problems such as designing printed circuit boards and routing very-large-scale integration circuits. 相似文献
18.
19.
本文巧妙得将运动员参赛项目的排序问题转化为图论中经典的旅行商问题求解。以连续参加两项比赛的人次最少为目标,应用了最小生成树求解Ham ilton回路的方法,得到了题目的最优解。之后,经过严谨的分析,我们又增加了1个使连续比赛的事件尽量分散开的约束条件,即保证任何1位运动员至多出现1次连续比赛的情况的条件下,求得总连续比赛人次数最少的排序方案。这样得到结果就加强了比赛项目排序结果对每位运动员的公平性、合理性。改进后的约束模型,要求我们从一些近似最优解的结果中再挑选满足约束的最终解。针对这种算法,我们采取了解决这种问题更有效的遗传算法计算。两种算法各有利弊,得到的结果与理论分析保持一致。 相似文献