注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

柳州文铮

CANTOR SET&ART

 
 
 

日志

 
 

最小生成树Minimum spanning tree数学模型股票对冲基金方法  

2012-09-07 12:52:12|  分类: 股票数学模型对冲 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

File:Minimum spanning tree.svg

最小生成树的平面图形 。 每个边缘被标记为与它的重量,而这里是大致正比于它的长度。

给定一个连接 , 无向图 ,该图的生成树是一个子图,这是一个和所有的顶点连接起来。 单个图形可以有许多不同的生成树。 我们也可以为每条边分配的权重 ,这是一个数字,表示它是如何不利,并使用分配权重的一个生成树,生成树中的边的权重计算的总和。 最小生成树(MST)或最小重量生成树一个生成树重量小于或等于其他每个生成树的重量。 更一般地说,任何无向图(不一定连接)具有最小生成树森林 ,这是其连接组件工会最小生成树。

一个典型的例子是有线电视公司铺设电缆到一个新的社区。 如果它被约束为掩埋电缆只沿着一定的路径,然后将有曲线图,表示由这些路径连接点。 这些路径可能会更昂贵,因为他们不再,或要求电缆埋得更深,这些路径将较大的权重为代表的边缘。 有没有循环的路径,图的生成树的一个子集,但仍然连接到每一个房子。 可能有几个生成树的可能。 最小生成树将是一个最低的总成本。

属性
编辑 ]可复


此图显示了可能存在一个以上的曲线图中的最小生成树。 在图中,下面的曲线图的两棵树是给定的图中的最小生成树的两种可能性。

可能有几个最小生成树的具有最小数目的边缘相同的重量 ,特别是,如果一个给定的图中的所有的边的权重是相同的,则该图中每个生成树是最小。 如果有 n个图中的顶点,然后每个树具有 n -1边缘。


编辑 ]唯一性

如果每个边都有一个不同的权重,然后将只有一个,唯一的最小生成树 。 这可以证明通过诱导矛盾 。 这是真实的,在许多现实的情况下,有线电视公司如上面的例子,它是不可能有完全相同的任意两个路径成本。 这可以推广到跨越森林。 如果边的权重不是唯一的,只有多组权重最小生成树是唯一的,是相同的所有最小生成树[1] 。

由矛盾的唯一性的证明如下。 [2]


假设我们有一个算法,发现一个MST(我们称之为A)的结构基础上的图形和顺序的边缘时,下令重。 (这种算法是存在的,见下文。)
假设MST 是不是唯一的。
与同等重量的还有另外一个生成树,说:MST 乙 。
设 e1的边缘是在A,但不是在 B。
由于B是一个MST,{E1} \杯 B必须包含一个圈C。
然后,B应该包括至少一个边缘 e2,是不是在A和位于C 上 。
假设重量的E1是小于对 e2。
更换E2与E1 B 中产生的生成树{E1} \杯 B - { 金汇 },它具有更小的重量比 B。
矛盾。 由于我们假设B是一个MST,但实际上并非如此。

如果E1的重量大于e2时 ,类似的参数涉及树木{ 金汇 } \杯 A - {E1}也导致了一个矛盾。 因此,我们得出这样的结论的假设,可以有第二MST是假的。


编辑 ]成本最低的子

如果权重是积极的,那么最小生成树其实是成本最低的连接所有的顶点,因为子图包含的周期必然有更多的总重量。


编辑 ]周期属性

对于任何周期 ? 在图中,如果一个边缘 ? 的C的重量为大于其他边缘的C的权重,则该边缘可以不属于一个MST。 假设相反 ,即,?属于一个MST T1,然后, 删除电子邮件将打破T1为两个子两端的电子在不同的子树。 C的其余部分重新连接的子树,因此有一个在不同的子树,即,C的端部的边缘f的,它重新连接的子树到重量小于T1的一个树T2,因为f的重量的重量比小于电子 。


编辑 ]剪切财产


此图所示的切割属性MSP.T MST给定的图。 如果S = {A,B,D,E},从而VS = {C,F},则有3种可能性对面的边缘切割(S,VS),他们是边BC,EC,EF的原图。 然后,e是1的最小重量为切割边缘,因此S∪{E}的一部分的MST T.

对于图形的切割 C 在任何一个边e的C的重量是,如果小于的C的所有其它边缘的权重,然后这条边属于曲线图的所有MSTS为了证明这一点, 假设相反 :在在左边的图,边BC(重量)的一部分,MST T代替边e(权重4)。 外加到T将产生一个周期,而更换BC与E会产生MST的权重较小。 因此,树,其中包含BC是不是一个的MST,一个矛盾,违反了我们的假设。


编辑 ]最小的成本优势

如果边缘的最小成本E的曲线图是唯一的,则该边缘被包括在任何MST。 事实上, 如果 e是不包括在MST,除去任何的(较大的成本)的边缘形成的周期后加入e来的MST,将产生较小的权重的生成树。


编辑 ]算法

第一种算法寻找最小生成树的由捷克科学家奥塔卡尔的Bor?vka于1926年(见Bor?vka的算法 )。 它的目的是高效的电动覆盖摩拉维亚 。 现在有两种常用算法, Prim算法Kruskal算法 。 所有这三个都是贪婪算法在多项式时间内运行,这样的问题,发现这些树木是在FP ,以及相关的决策问题,如确定是否有特别的优势是在MST或确定的最低总重量超过一定值时P 。 不常用的另一个贪婪算法是反向删除的算法 ,该算法是反向Kruskal算法。

如果边的权值是整数,然后确定性算法是已知的解决问题的O(M + N)的整数运算。在一个比较模型[3] ,其中边的权重仅允许执行的操作是两两比较, 卡尔格,克莱因&Tarjan的(1995 )发现一个线性时间随机算法基于Bor?vka的算法和反向的删除算法的组合。 [4] [5]无论问题可以解决确定性以线性时间由一个基于比较的算法保持一个开放的问题,但是。 最快的非随机的比较为基础的算法与已知的复杂性, 伯纳德Chazelle ,是基于软堆的近似优先级队列。 [6] [7],其运行时间为? (Mα(M,N)),其中 m是的边的数量,n是顶点的数目和,α是古典官能逆的阿克曼功能 。 函数α生长极为缓慢,所以,对于所有的实际目的,它可以考虑一个常数不大于4;从而Chazelle的算法需要非常接近线性时间。 赛斯Pettie和维贾雅德兰已经找到了一个可证明的最优确定性比较基于最小生成树算法的计算复杂度是未知的。 [8]

也有研究认为并行算法的最小生成树问题。 具有线性的处理器数,它是可能的解决问题 O(\日志n) [9] [10] 贝德聪(2003 )证明,可以计算MSTS快5倍,比8个处理器优化的序贯算法。 [11]后来,Nobari 等人 [12]提出了一种新的算法,可扩展的,平行的最小生成森林的算法(MSF)无向加权图。 该算法利用Prim算法以并行方式,同时扩大几个子集,所计算的MSF。 PMA,制约当地生长的处理器的计算子树,最大限度地减少了在不同的处理器之间的通信。 PMA效果,实现了可扩展性,以往的做法缺乏。 在实践中,PMA,比以前的状态的最先进的基于GPU-MSF算法,而被几个量级更快比顺序的CPU为基础的算法。

其他专门的算法已经被设计为如此之大,它必须在任何时候都存储在磁盘上的图形计算最小生成树。 这些外部存储算法,例如“工程的外部存储器的最小生成树算法”由罗马Dementiev等。, [13]可以操作,由作者的索赔,低至2至5倍的速度比传统的内存中的算法。 他们依靠高效率的外部存储的排序算法图形收缩技术,有效地减少图形的大小。

这个问题也可能在一个分布式的方式接近。 如果每个节点都被认为是计算机,不的节点知道什么,除了它自己的连接的链路,一个可以计算的分布式最小生成树 。


编辑 ]MST完全图

艾伦M. Frieze的发现,给定一个n个顶点的 完全图 ,边的权重是独立同分布的随机变量的分布函数 F 满意的 F'(0)> 0 ,然后随着 N接近+∞重量MST方法 \ζ电(3)/ F'(0),其中 \ zeta电 是的黎曼zeta函数 。 额外的有限方差的假设下,,弗里兹也证明了收敛的概率。 随后, J. 迈克尔·斯蒂尔的方差的假设可以被丢弃。

在以后的工作中, 斯万詹森证明了中心极限定理的MST为重。

对于均匀分布的随机权重 [0,1] 小的完整的图,确切的预期大小的最小生成树计算。 [14]

顶点 预期大小 逼近预期大小
2 1/2 0.5
3 四分之三 0.75
4 31/35 0.8857143
5 924分之893 0.9664502
6 273分之278 1.0183151
7 29172分之30739 1.053716
8 184848378分之199462271 1.0790588
9 115228853025分之126510063932 1.0979027

编辑 ]相关问题

一个相关的问题是的 k-最小生成树的第(k-MST),这是跨越树以最小的重量的曲线图中的某些子集的k个顶点。

K-最小生成树的一组k 的生成树(出所有可能的生成树)的一个子集,没有生成树的子集外,更小的重量。 [15] [16] [17] (请注意,这个问题是无关的 k-最小生成树)。

欧几里德最小生成树边的权重对应的点在平面(或空间)的顶点之间的欧氏距离图的生成树。

直线最小生成树是图的生成树边的权重对应的点在平面(或空间)的顶点之间的直线距离 。

分布式模型中 ,每个节点被认为是一台电脑和任何节点都知道任何东西,除了它自己的连接的链路,可以考虑分布式最小生成树 。 数学定义的问题是相同的,但有不同的方法解决。

最小生成树是一棵树,有一个显着的节点(原产地,或根),每一个连接到节点的子树中包含一个C节点不超过c被称为树的能力。 解决CMST最佳的需要指数的时间,但如以扫 - 威廉姆斯和Sharma产生良好的启发式在多项式时间内的最佳解决方案。

度约束最小生成树最小生成树中的每个顶点连接到不超过d其他顶点,对于给定的数 d。 D = 2的情况下,是一个特殊的旅行商问题的情况下,这样的度约束最小生成树是NP-hard一般。

有向图的最小生成树问题被称为树状的问题,在二次使用Chu-Liu/Edmonds算法可以解决的。

一个最大生成树一个生成树重量大于或等于所有其他生成树的重量。 这样的树后,可以找到与Prim的或Kruskal算法,如边的权重乘以-1的的MST问题上新的图形解决。 最大生成树中的路径是最宽的路径 ,它的两个端点之间的图形:在所有可能的路径,它最大重量的最小权重的边缘。 [18]最大的生成树发现自然语言 解析算法的应用[ 19] ,在训练条件随机域算法。

动态MST的问题涉及在原始图中的边的权重的变化或缺失/插入的一个顶点。 [20] [21]的更新后的先前计算的MST


编辑 ]最小生成树的瓶颈

的瓶颈的边缘是最高的加权边缘,在一个生成树。

生成树是最起码的瓶颈生成树 (或MBST)如果图不包含一个较小的瓶颈边的权重生成树。

一个MST必然是一个MBST(可证明的由切割物业 ),但一个的MBST是不必然的MST。


编辑 ]参见
反向删除算法
Dijkstra算法
生成树协议 ,用于交换网络
最小生成树的图像分割
埃德蒙兹的算法
分布式最小生成树
Prim算法
Kruskal算法
Steiner树
Bor?vka的算法
编辑 ]
^ 不要加权图的最小生成树与一个给定的权重有相同数目的边?
^ 界洛格,RG;,PA Humblet;斯培拉,PM(1983年1月),“A最小权重生成树的分布式算法,ACM编程语言和系统 5(1):66-77, DOI : 10.1145/357195.357200 。
Fredman,ML威拉德,DE(1994年),“跨二分的最小生成树,最短路径算法”, 计算机与系统科学, 48(3):533-551, DOI : 10.1016/S0022-0000(05 )80064-9 , MR1279413 。
卡尔格,戴维·R·克莱恩,菲利普·N. Tarjan的,罗伯特·E. (1995),“随机线性时间的最小生成树算法来寻找” 杂志协会为计算机 42(2):321 - 328 10.1145/201019.201022, MR , DOI : 1409738
Pettie,赛斯德兰,维贾雅(2002年), “最大限度地减少随意性最小生成树,并行连接,并设置最大值算法” ,PROC。 第13届ACM-SIAM离散算法的研讨会(SODA '02),旧金山,加州,第713-722页 。
Chazelle,伯纳德 (2000年),“最小生成树算法与反阿克曼类型的复杂度”, 协会为计算机 47(6):1028至1047年, DOI : 10.1145/355541.355562 , MR 1866456 。
Chazelle,伯纳德 (2000年),“软堆:一个近似的优先级队列中的最优误差率”, 协会为计算机 47(6):1012至1027年, DOI : 10.1145/355541.355554 , MR 1866455 。
Pettie,赛斯德兰,维贾雅(2002年),“最佳最低生成树算法”, 中国的协会为计算机 49(1):16-34, DOI : 10.1145/505241.505243 , MR 2148431 。
冲,嘉皇忆捷汉,林,德华(2001年),“并发线程和最优的并行最低的生成树算法”, 中国的协会为计算机 48(2):297-323, DOI : 10.1145 / 375827.375847 , MR1868718 。
^ Pettie,赛斯;德兰,维贾雅(2002年),“随机工作最优的并行算法寻找最小生成树的森林”, 计算SIAM杂志“ 31(6):1879年至1895年, DOI : 10.1137/S0097539700371065, MR 1954882 。
^ 大卫·贝德,聪,国晶辉(2006),“快 ??速共享内存的算法来计算的稀疏图的最小生成树的森林”, 杂志的并行与分布式计算 66(11):1366年至1378年, DOI : 10.1016 / j.jpdc.2006.06.001 。
Nobari,萨德克 ,曹,THANH东; Karras,帕纳约蒂斯;布雷桑,斯特凡(2012年), “可扩展并行最小生成森林的计算” 进行的第17届ACM SIGPLAN座谈会上的并行程序设计原理与实践(新奥尔良,路易斯安那州,USA:ACM)(11):205-214, DOI : 10.1145/2145816.2145842 , ISBN 978-1-4503-1160-1 。
^ Dementiev,罗马;桑德斯,彼得·舒尔斯特,多米尼克,Sibeyn,:JOP F.(2004), “工程外部存储器的最低生成树算法” ,PROC。 IFIP第18届世界计算机大会上,TC1第3届国际理论计算机科学会议(TCS2004),第195-208页 。
^ J.迈克尔·斯蒂尔 (2002年),“最小生成树的图的随机边长”, 数学与计算机科学,II(凡尔赛宫,2002年),趋势数学,巴塞尔Birkh?user,第223-245页, MR 1940139
^ Gabow,哈罗德·N.(1977),“两种算法,用于生成加权棵生成树”, SIAM杂志“计算 6(1):139-150, MR 0441784 。
Eppstein的,大卫 (1992),“寻找的 k最小生成树的”,BIT 32(2):237-248, DOI : 10.1007/BF01994879 , MR 1172188 。
弗雷德里克森,格雷格·N.(1997),“矛盾的数据结构动态边缘连接和K表最小生成树的” 计算SIAM杂志“ 26(2):484-538, DOI : 10.1137/S0097539792226825 , MR1438526 。
胡锦涛,TC(1961年),“最大容量的路由问题”,运筹学9(6):898-900, DOI : 10.1287/opre.9.6.898 , JSTOR 167055 。
麦当劳,瑞安·佩雷拉,费尔南多; Ribarov,基里尔;Haji?,月(2005年)。 “非投射的依赖解析使用生成树算法” 。PROC。 HLT /的 。
斯培拉,PM,潘,A.(1975),“查找和更新的生成树,最短路径”,SIAM杂志“计算 4(3):375-380, MR 0378466 。
霍尔姆,雅各的克里斯蒂安·利希滕贝格, Thorup,Mikkel (2001年),“聚对数确定的完全动态的连接算法,最小生成树,2 -边,和biconnectivity”, 期刊协会为计算机 48(4):723-760, DOI : 10.1145/502090.502095 , MR 2144928 。
编辑 ]其他阅读
格雷厄姆,RL地狱,帕沃尔(1985年),“历史上的最小生成树问题”, 史册的历史计算 7(1):43-57, DOI : 10.1109/MAHC.1985.10011 , MR 783327 。
奥塔卡尔Boruvka最小生成树问题的两个1926年的论文,评论,历史(翻译)(2000) ,海伦娜·雅罗斯拉夫Nesetril,伊娃MilkováNesetrilová。 (第7节给出了他的算法,它看起来像一个跨之间的Prim和Kruskal)。
查尔斯·E· 托马斯H. Cormen , Leiserson发表的题为 罗纳德L.李维斯特 , 克利福德·斯坦 。 算法导论 (第二版)。 麻省理工学院出版社和McGraw-Hill,2001年,ISBN 0-262-03293-7 。 第23章:最小生成树,第561-579页。
艾斯纳(1997年),贾森。 国家的最先进的最小生成树算法:A教程讨论 。 手稿月,宾夕法尼亚大学。 78页
Kromkowski,约翰·大卫。 “仍然未熔融后,这些年来”,在年度版本,种族和民族关系,17 / E(2009年麦格劳希尔)(最小生成树横跨美国的种族多样性的人口分析方法)。
编辑 ]外部链接
杰夫·埃里克森的MST讲义
在BGL,实施Boost Graph库
石溪算法存储库-最小生成树的代码
。网在QuickGraph实施

  评论这张
 
阅读(424)| 评论(0)
推荐

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017