斯坦纳树问题及其推广

斯坦纳树算法
斯坦纳树是一棵连接所有图节点的生成树，其边权和最小。

斯坦纳树问题是NP难问题，因此通常需要使用近似算法进行求解。

斯坦纳树算法的基本思想是：将原图中的所有边分解为若干个小图，然后对每个小图分别求解最小生成树。

最后，将所有小图的最小生成树通过一些边连接起来，形成最小斯坦纳树。

斯坦纳树算法的时间复杂度为O(2^n * n^2)，其中n为图中节点的数量。

该算法适用于节点数量较少的图，但对于大规模的图来说，其运行时间会非常长，因此需要结合其他算法进行优化。

- 1 -。

图的steiner最小树问题及其求解摘要:斯坦纳树问题是组合优化学科中的一个问题。

属于NP-难问题,即无法在多项式时间内得到最优解。

本文主要讨论了图的steiner最小树问题,并给出了近似算法,该算法是在破圈法的基础上进行了改进,并且引用了agent的思想。

最后对算法进行了分析。

关键词:Steiner最小树NP-难题破圈法中图分类号:TP312文献标识码:A文章编号:1009-3044(2009)25-7312-02Graphical Steiner Minimum Tree Problem and SolusionYANG Ling-yun(College of Computer and Information Engineering, Henan University, Kaifeng 475001,China)Abstract: Steiner tree problem is one of the subject of combinatorial optimization problem. It belongs to NP-hard problems that cann’t find the optimal solution in polynomial time. This article discusses the minimum steiner tree problem in graphs, and gives the approximate algorithm, which is improved on loop damage method, and quoted the agent's thinking. Finally, an analysis of the algorithm.Key words: steiner minimum tree; NP-hard problem; loopdamage method现实生活中经常要求解决这样的问题,即将若干给定点相连并使连线的总长最短。

最小瓶颈支撑树和斯坦纳树MBST and Steiner Tree设( G, W ) 是无向连通赋权图，G的所有支撑树中权值最大的边的权值最小的支撑树称为G的最小瓶颈支撑树（minimal bottleneck spanning tree, MBST）AE C D 235910F B 478A E C D 2359F B 4AE C D 239F B 78A E C D 59F B 478MST⏹定理❑无向连通赋权图的最小支撑树一定是最小瓶颈支撑树，但最小瓶颈支撑树不一定是最小支撑树⏹证明 —— MST 一定是MBST❑假设最小支撑树 T 不是最小瓶颈支撑树，设 T 的最大权值边为 e ，则最小瓶颈支撑树 T b 的所有边的权值都小于 w (e )❑删除 T 中的 e 形成两棵数 T 1 和 T 2 ❑由于 T b 连通，因此存在 T b 的边 e '，连接 T 1 中某顶点和 T 2 中某顶点。

于是用 e ' 连接 T 1 和 T 2 后得到得到新的支撑树，但其总权值小于 T ，与 T 是最小支撑树产生矛盾 e T 2 e'T 1⏹证明—— MBST不一定是MST❑考虑一个无向连通赋权图，图中仅存在一条桥而且权值最大，则图中每个支撑树（无论是否最小支撑树）都是最小瓶颈支撑树w⏹设( G=(V, E), W ) 是无向连通赋权图，R V，在G的所有包含R中所有顶点的子图中，总权值最小的树称为G的斯坦纳树（Steiner tree）⏹当R = V时，斯坦纳树问题即是最小支撑树问题adc b21 1 12 2 a d cb 1 1 1adc b43 3 34 4 a d c b 4 4⏹虽然斯坦纳树问题与最小支撑树问题具有相似之处，然而斯坦纳树问题则难得多❑属于NPC问题，事实上，它是卡普（Richard Manning Karp）证明的第一批21个NPC问题之一E nd。

斯坦纳树模型在含DG配电网规划中的应用韩翔宇;刘涤尘;廖清芬;贾骏;朱正;胡静竹【摘要】不确定性分布式电源的接入,给配电网规划带来新的挑战.首先将含分布式电源的配电网规划归纳为求解斯坦纳树问题,提出了一种新的配电网规划建模方法.其次通过DG供电分区的划定,将分区内的负荷节点处理为一个不接DG的负荷节点,消除DG对配电网规划的影响.针对斯坦纳树问题传统解法求解时间会随着斯坦纳点的规模成倍增加的缺陷,采用一种改进的粒子群优化(PSO)算法解决斯坦纳树N-P完全问题.结合54节点算例并与传统方法计算结果比较,验证了该方法的有效性.【期刊名称】《电力系统及其自动化学报》【年(卷),期】2016(028)006【总页数】6页(P62-67)【关键词】分布式电源;配电网规划;斯坦纳树;供电分区;改进粒子群优化算法【作者】韩翔宇;刘涤尘;廖清芬;贾骏;朱正;胡静竹【作者单位】武汉大学电气工程学院,武汉430072;武汉大学电气工程学院,武汉430072;武汉大学电气工程学院,武汉430072;武汉大学电气工程学院,武汉430072;武汉大学电气工程学院,武汉430072;武汉大学电气工程学院,武汉430072【正文语种】中文【中图分类】TM715分布式电源DG（distributed generation）是直接接在用户附近或配网中的小型发电设备，它能使清洁能源和分散能源得到充分利用，缓解能源危机。

配电网规划是带有约束条件的非线性混合整数优化问题，DG的加入使规划难度增加。

所以含DG的配电网规划也就成为配电网规划中的一个难点。

含DG的配电网规划可划分为两部分：DG对配电网及规划的影响研究［1］和计及DG的配电网协调规划研究。

目前协调规划的主流求解算法有启发式算法［2］、数学规划算法［3］、随机优化算法［4］等。

启发式算法计算无法保证结果的最优性，数学规划算法无法逃避随着求解规模的增大算法难收敛的问题，以遗传算法［5-6］、蚁群算法与禁忌搜索［7］、粒子群算法［8］等或相应的改进算法为代表的随机优化算法是目前的研究热点。

最⼩斯坦纳树学习笔记定义摘⾃百度百科的定义：斯坦纳树问题是组合优化问题，与最⼩⽣成树相似，是最短⽹络的⼀种。

最⼩⽣成树是在给定的点集和边中寻求最短⽹络使所有点连通。

⽽最⼩斯坦纳树允许在给定点外增加额外的点，使⽣成的最短⽹络开销最⼩。

可以这么理解：⼀个图的⽣成树是构造⼀棵树把所有点给联通，⽽斯坦纳树则是构造⼀棵树把给定的⼏个点联通。

如同⽣成树有最⼩的⼀棵，斯坦纳树也有最⼩的。

如何求最⼩斯坦纳树，是我们今天要探讨的话题。

实现例题：Luogu P6192【模板】最⼩斯坦纳树给定⼀个包含n个结点和m条带权边的⽆向连通图G=(V,E)。

再给定包含k个结点的点集S，选出G的⼦图G′=(V′,E′)，使得：S⊆V′G′为连通图；E′中所有边的权值和最⼩。

你只需要求出E′中所有边的权值和。

n≤100,m≤500,k≤10。

求最⼩斯坦纳树，我们使⽤的是状压DP。

⾸先⾮常显然的是，这个选出来的⼦图G′⼀定是个树。

令f i,S表⽰当前这个树的根为i，选出的点的集合为S（注意这⾥选出的点专指那k个点中的点），这⾥的S在 dp 中是被状压的。

第⼀种转移⽅式：f i,S=f i,T+f i,S−T (T⊆S)这种转移⽅式意义在于把⼀个根可能会连出多棵S互不相交的树，该⽅程可以合并它们。

此时这个根的度数≥1。

以下是⼀个⽰意图，其中 5,6,7 三个点属于⽬标的那k个点，3 是⽬前的i。

第⼆种转移⽅式：f i,S=f j,S+w(i,j)这种转移⽅式意义在于把⼀个根的状态转移到与他相邻的⼀个根上。

此时根i的度数=1。

⽰意图如下，其中i=1，j=3，S={5,6}，橙⾊虚线代表待扩展的边 (i,j)。

Processing math: 100%考虑 dp 顺序，显然S从⼩到⼤枚举即可。

对于第⼀种转移⽅式，只需枚举S的⼦集T。

对于第⼆种转移⽅式，注意到这玩意⼉是个三⾓不等式，联想到最短路也是如此——没错，⽤最短路跑⼀遍就⾏了。

参考代码int n, m, k, f[Maxn][1 << Maxk];struct Edge {int next, to, dis;}edge[Maxm * 2];int head[Maxn], edge_num;void add_edge(int from, int to, int dis) {edge[++edge_num].next = head[from];edge[edge_num].to = to;edge[edge_num].dis = dis;head[from] = edge_num;}queue <int> Q; int dist[Maxn]; bool inq[Maxn];void SPFA(int S) {memset(inq, 0, sizeof(inq));for(int i = 1; i <= n; ++i) {dist[i] = f[i][S];if(dist[i] != 1061109567) Q.push(i), inq[i] = 1;}while(Q.size()) {int u = Q.front();Q.pop();inq[u] = 0;for(int i = head[u]; i; i = edge[i].next) {int v = edge[i].to;if(dist[v] > dist[u] + edge[i].dis) {dist[v] = dist[u] + edge[i].dis;if(!inq[v]) {inq[v] = 1;Q.push(v);}}}}for(int i = 1; i <= n; ++i) f[i][S] = dist[i];}int main() {n = read(); m = read(); k = read();int u, v, w;for(int i = 1; i <= m; ++i) {u = read(); v = read(); w = read();add_edge(u, v, w);add_edge(v, u, w);}memset(f, 63, sizeof(f));for(int i = 1; i <= k; ++i) {u = read();f[u][1 << (i - 1)] = 0;}for(int i = 1; i <= n; ++i) f[i][0] = 0;for(int S = 0; S < (1 << k); ++S) {for(int i = 1; i <= n; ++i)for(int T = S & (S - 1); T; T = S & (T - 1))f[i][S] = min(f[i][S], f[i][T] + f[i][T ^ S]);SPFA(S);}int ans = 2e9;for(int i = 1; i <= n; ++i) ans = min(ans, f[i][(1 << k) - 1]);cout << ans << endl;return 0;}例题[WC2008] 游览计划考虑把每个⽅格当成⼀个点，最⼩斯坦纳树搞它就完了。

图的steiner最小树问题及其求解作者：杨凌云来源：《电脑知识与技术》2009年第25期摘要:斯坦纳树问题是组合优化学科中的一个问题。

属于NP-难问题,即无法在多项式时间内得到最优解。

本文主要讨论了图的steiner最小树问题,并给出了近似算法,该算法是在破圈法的基础上进行了改进,并且引用了agent的思想。

最后对算法进行了分析。

关键词:Steiner最小树 NP-难题破圈法中图分类号:TP312文献标识码:A文章编号:1009-3044(2009)25-7312-02Graphical Steiner Minimum Tree Problem and SolusionYANG Ling-yun(College of Computer and Information Engineering, Henan University, Kaifeng 475001,China)Abstract: Steiner tree problem is one of the subject of combinatorial optimization problem. It belongs to NP-hard problems that cann’t find the optimal solution in polynomial time. This article discusses the minimum steiner tree problem in graphs, and gives the approximate algorithm, which is improved on loop damage method, and quoted the agent's thinking. Finally, an analysis of the algorithm.Key words: steiner minimum tree; NP-hard problem; loop damage method现实生活中经常要求解决这样的问题,即将若干给定点相连并使连线的总长最短。

几类特殊的斯坦纳最小树问题【基金项目】2010 年度浙江省大学生科技创新活动计划 (新苗人才计划)【立项项目】“几类特殊斯坦纳最小树问题的研究”研究成果( 2010R424038).一、斯坦纳最小树的性质1.已知3 点的斯坦纳最小树关于斯坦纳最小树问题，17 世纪法国数学家费马曾有过类似的研究.他提出了费马点问题：“在平面上，任给△ ABC试求一点S，使它到A，B, C三点的距离之和最小•”这个问题在费马提出后不久就被托里拆利解决了，并得到了相关的结论：在△ ABC中，/A为其最大角，S是平面上的点.(1)当/A>xO=[0,1 : >>x=fminunc(f,x0)用MATLAB^件运行，得结果是：x1=1.9671 , x2=1.57，最小距离为5.393.对于4 个点的斯坦纳最小树，如果这4 个点构成凸四边形，类似于正方形，其斯坦纳最小树有2个斯坦纳点S1,S2;如果4个点构成凹四边形，当/ ADB h BDC h CDA=120时，连线段AD,DB,DC即为其斯坦纳最小树，不必添加斯坦纳点.而当/ ADB,Z BDC,Z CDA不全相等时，不妨设/ CDA最小，那么其斯坦纳最小树中斯坦纳点只有1个，该点必为△ ADC的费马点S.其实数学家已经证明了此类问题目前尚未找到有效的算法，即它是个“ NP问题” •例如寻找1个由4点构成的正方形的斯坦纳点的程序：f=(x)sqrt((x(1)-0)八2+(x(2)-0)八2)+sqrt((x(1)-0)八2+(x(2)-1)八2)+sqrt((x(3)-1)八2+(x(4)-0)八2)+sqrt((x(3)-1)八2+(x(4)-1)A2)+sqrt((x(1) -x(3))八2+(x (2)-x(4))A2);>>x0=[0,1,2,3 ]>>x=fminunc(f,x0)用MATLAB^件运行，得结果(即最优解)是：x1=0.2887,x2=0.5,x3=0.7113,x4=0.5 ，连线总长度最小为d=2.7321.上述研究仅是用初等方法给出了不多于4 个点的斯坦纳最小树及其算法，那么5 点甚至更多点的斯坦纳最小树及其算法值得我们进一步研究.。

steiner树问题的近似算法
马绍汉;王锐
【期刊名称】《计算机学报》
【年(卷),期】1989(012)007
【摘要】著名的Steiner树问题是,给定图G=(V、E),QV,在边集E上定义权函数f:E→Z^+,要求在图G上找一子树T=(Y,U),使得QY且∑_(c∈U)f(e)达到极小以后,我们称该问题为ST问题,R.M.Karp曾证明ST问题为NP-完全的,本文作者曾提出图上Steiner树问题:在图G=(V,E),QV上,要求一子树T=(Y,
【总页数】3页(P558-560)
【作者】马绍汉;王锐
【作者单位】不详;不详
【正文语种】中文
【中图分类】TP311.12
【相关文献】
1.改进的基于拓扑分析的Steiner树近似算法 [J], 高磊;张德运;王晓东;安智平
2.关于满Steiner树问题的一个近似算法 [J], 罗美菊;赵传立;唐恒永
3.多材料Terminal Steiner树拼接问题的近似算法研究 [J], 文永松;朱淑娟;庞一成
4.近乎最佳的Manhattan型Steiner树近似算法 [J], 马军;杨波;马绍汉
5.图的Steiner树问题的改进的快速近似算法 [J], 吕其诚
因版权原因，仅展示原文概要，查看原文内容请购买。

第8卷 第15期 2008年8月1671-1819(2008)15-4238-09科 学 技 术 与 工 程Science T echno logy and Eng i neeringV ol 18 N o 115 A ug . 2008Z 2008 Sci 1T ech 1Engng 1综 述数 学Steiner 最小树问题及其应用张 瑾1,2马 良1*(上海理工大学管理学院1,上海200093;河南大学计算机与信息工程学院2,开封475001)摘 要 Ste i ner 最小树问题是一个历史悠久的经典的组合优化问题,由于应用广泛,多年来一直受到研究者的广泛关注。

介绍了各种S teine r 树问题及其求解算法和实际应用。

关键词 Ste i ner 最小树 精确算法 启发式算法 应用中图法分类号 O 224; 文献标志码 A2008年4月21日收到国家自然科学基金项目(70471065)、上海市重点学科建设项目(T0502)资助第一作者简介:张 瑾(1974)),女,河南开封人,博士生1研究方向:系统工程、智能优化。

*通信作者简介:马 良(1964)),男,上海人,博士,教授,博士生导师1研究方向:智能优化。

现实生活中经常要求解决这样的问题,即将若干给定点相连并使连线的总长最短。

在网络通信领域中,该问题被一般化地提为:如果要在n 个区域间铺设通信网,使得各区域之间能实现信息的共享,那么应如何铺设才能使通信线路的总长最短?一般首先想到的可能就是求连接这n 个点的最小生成树(M i n i m um Spann i n g Tree )M ST )这种做法,但如果不拘泥于这n 个点,而引入除这n 个点之外的另外几个点的话,则有可能使连接各区域的通信线路的总长更短。

这是Steiner 最小树问题(Steiner M i n i m u m Tree Prob le m ,简记为S MTP)的来源。

S teiner 最小树问题是经典的组合优化问题,最早可以追溯到17世纪初。