首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到18条相似文献,搜索用时 125 毫秒
1.
两个复杂多边形求交的矢量算法   总被引:8,自引:0,他引:8  
基于计算机几何和集合的基本理论,提出了任意两多边形求交的一种矢量算法,该算法并非时间和复杂度最优,但总体较优,对多边多形求交具有广泛的适应性。  相似文献   

2.
在一般有向图中最短路问题是没有好算法的。任何一个城市道路交通网可以看作一个赋权有向图。本文就一般的城市交通道路网中道路间的拓扑结构和特性进行了分析,得到一种求城市道路交通网络中给定两点间最短路的多项式时间近似算法,算法复杂性由交通网中结点数的多项式决定。  相似文献   

3.
合理安排铁路专用线取送车顺序,对提高调车机车作业效率、加速货车周转具 有重要的意义.在已知条件下,以机车在装卸点间走行时间为权,把树枝形专用线取(送) 车作业优化问题转换成哈密尔顿图最短路问题,并松弛为指派问题,采用匈牙利算法求 出指派问题的最优解,可得到最短回路路长的下界或最优解.若未得到最优解,再利用破 圈连接法求出满意的取(送)车顺序,此算法的复杂度为O(n2).同时对送兼调移、取兼调 移、取送结合、送调取结合作业形式进行了深入地讨论.最后举例说明了模型的构造及求 解过程.大量小规模案例表明,该算法的平均复杂度及性能是比较优越的.  相似文献   

4.
最短路径子图   总被引:2,自引:0,他引:2  
在大型网络中两节点之间的最短路径常常不止一条,而且在带限制条件的路径选择等应用上,常常需要找出多条最优或近优的路径.一些经典的单源最短路径算法,如Dijkstra算法,能找出一条从起始点到目的点的最短路径,但并不能求解两点之间的所有最短路径.本文给出了最短路径子图的概念,用于存储图中两节点之间所有最短路径信息,能够节约存储空间.并给出了最短路径子图构造算法SPSG,其时间复杂度为O(n e),比同类算法时间复杂度更低.随机网络模型的仿真结果表明:SPSG算法效率更高,  相似文献   

5.
为解决物体表面重建中的轮廓拼接问题,将其转化为在有向图中寻求最优路径问题.提出了基于遗传算法的适用各种目标函数的轮廓拼接算法,其中对初始种群的产生、交叉算子和变异算子等做了改进,以确保产生的个体均能代表有效解.算例模拟结果表明,该算法简单可行,在优化性能、收敛速度及鲁棒性等方面优于模拟退火算法.  相似文献   

6.
基于图的频繁闭项集挖掘算法   总被引:5,自引:0,他引:5  
为了提高数据挖掘效率,提出了一种基于图的频繁闭项集挖掘算法GFCG(graph—based frequent closed itemset generation).该算法采用位矢量技术构造有向图,表示项与项之间的频繁关系,并在有向图的基础上递归产生频繁闭项集,从而只需扫描数据库2次,不产生候选集;引入扩展频繁项集的概念,大大减小了检查频繁项集是否闭的搜索空间.用1个真实数据库和2个合成数据库对GFCG进行了测试,并与A-close和CLOSET算法的结果进行了比较,结果表明,该算法具有良好的速度和可伸缩性性能.  相似文献   

7.
针对基本萤火虫算法优化多模函数时计算复杂度高和需要预先设定较多参数值的问题,提出了两种修正的萤火虫算法:基于种群的萤火虫算法(S-GSO)和基于荧光素自然感应的萤火虫算法(LNS-GSO).这种改进使学习行为更符合自然界生物的学习规律,更有利于萤火虫发现问题的所有局部最优解.通过6个标准测试函数测试,结果表明结合运用这两种修正的萤火虫算法能够取得良好的收敛性,在寻找多模函数的峰值个数上显示出较强的优势.  相似文献   

8.
运用概念格外延覆盖知识、概念格分层思想及各层格节点之接的约束关系提出了一种新的构造算法,解决了Chein算法存在的产生大量冗余对与最终没有生成Hasse图的问题,通过实例验证了新算法可行性,进一步分析新构造算法与Chein算法的时间复杂度验证新算法的有效性.  相似文献   

9.
在城市交通网络中,为了优化交通流,需要搜索到符合出行需求 K 最短路径,并 将 OD(Origin-Destination)交通流合理分配到这些路径上.本文主要对搜索符合出行需 求的 K 最短路径搜索算法进行了研究,解决了已有算法仅能搜索出单条满足最短及 K 最 短条件路径的问题.根据 Wardrop 第二原则及路段阻抗函数理论,分析了路径集合搜索方 法对优化城市交通流的必要性,并定义了城市交通网络中 K 最短路径集合的概念及选择 条件,提出了一种面向城市交通网络的具有多项式时间复杂度的 K 最短路径集合搜索算 法.仿真结果表明,本文所提算法可以搜索出满足出行需求的所有 K 最短路径集合,在该 路径集合上进行交通流分配的效果明显优于传统方法.  相似文献   

10.
研究求包含空间中给定的若干个点的最小凸多面体的算法。给出了一种算法。其平均计算时间复杂度为空间中给定点的数量的线性函数。  相似文献   

11.
Introduction Bayesian networks are a graphical representa-tion of a multivariate joint probability distributionthat exploits the dependency structure of distribu-tions. Bayesian networks are directed acyclicgraphs(DAG), where the nodes are random vari-abl…  相似文献   

12.
13.
为比较有无转向约束条件下最短路径特征及其搜索算法的异同点,基于对偶图理论证明了转向约束网络中从单个源点到所有弧的最短路径集构成其对偶网络的生成树,提出了对偶最短路径树(DSPT)概念,并利用其分析算法之间的关系。研究结果表明:转向约束下的现有求解方法包括弧标号算法、节点标号算法和对偶网络法都可以统一到DSPT算法框架内,而且与无转向约束的最短路径树(SPT)算法在路径搜索策略上是相同的;对于转向约束网络中的最短路径问题可建立一个DSPT原型算法,结合各种SPT标号技术能设计出更多的有效算法。  相似文献   

14.
如何解决最短路径选择问题一直是城市交通流诱导系统的关键之一.基于群体仿生理论的蚁群算法是解决此问题的一种方法,针对采用蚁群算法进行最短路径选择时易出现的陷入局部最优解问题,引入混沌理论,采用混沌蚁群算法利用混沌初始化进行改善个体质量和利用混沌扰动避免在蚁群算法搜索过程中陷入局部极值,同时降低了蚁群算法的时间复杂度,从而更好的解决了最短路径选择问题.  相似文献   

15.
针对核偏最小二乘法(KPLS)随核函数矩阵维数膨胀而计算量增加的问题,提出分块核偏最小二乘法(BKPLS).BKPLS根据核函数矩阵对称的性质,将KPLS中的批量算法转变成分块算法,不但减小了对计算机硬件的要求,而且减少了计算时间.仿真结果验证了BKPLS的有效性,而且在样本数量巨大,KPLS无法实现的情况下,BKPLS也能保证辨识算法的实现.  相似文献   

16.
基于边需求的抢修分队选址问题   总被引:1,自引:0,他引:1  
为解决机动作战背景下抢修分队的合理选址问题,提高战场装备抢修的时效性,基于不确定决策理论中的拉普拉斯准则以及网络上任意一点均有可能发生任务需求的假设,以整个机动交通网的覆盖率最大为目标,构建了一种新的双重覆盖标准选址模型;设计了边需求下的覆盖率计算方法,采用分区域聚类的方法构造初始解,用改进的遗传禁忌算法精确求解,并加入启发式策略,避免搜索过程中产生大量不可行解.结果表明,所提出的算法计算量小,在不增加网络维度的情况下,解决了边需求选址模型的精度问题.  相似文献   

17.
Support Vector Clustering (SVC) is a kernel-based unsupervised learning clustering method. The main drawback of SVC is its high computational complexity in getting the adjacency matrix describing the connectivity for each pairs of points. Based on the proximity graph model, the Euclidean distance in Hilbert space is calculated using a Gaussian kernel, which is the right criterion to generate a minimum spanning tree using Kruskal‘s algorithm. Then the connectivity estimation is lowered by only checking the linkages between the edges that construct the main stem of the MST ( Minimum Spanning Tree), in which the non-compatibility degree is originally defined to support the edge selection during linkage estimations. This new approach is experimentally analyzed.The results show that the revised algorithm has a better performance than the proximity graph model with faster speed, optimized clustering quality and strong ability to noise suppression, which makes SVC scalable to large data sets.  相似文献   

18.
在对现有的经典路径优化算法性能进行分析基础上,指出现有算法的缺点。通过对布尔可满足性理论的研究,提出基于布尔可满足性的路径优化算法,并结合记忆机制,将其应用在动态路径优化中,减少最短路径的搜索时间和不必要的重复搜索,体现该算法的优势。最后,利用该算法对一简单路网进行验证。  相似文献   

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

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