大三的时候做了一道斯坦纳树的题，最近几天朋友跟我讨论某个问题，忽然觉得跟那时候的做法很类似，结果发现自己没有留下任何材料。想了半天把那时候的想法回忆起来了。当时没有留记录是因为想法太简单，算法性能太差。不过现在想想无论好坏，啥想法都应该记下来，以后至少可以在这个基础上继续走。

Steiner Tree, 就是说给定一个图，和他的节点的一个子集。求包含该子集内所有节点的最小生成树（不要求包含全图的所有节点）。其实是算法老师留的作业，那时候也没当回事周末随便写了点。结果发现这个居然是一个NPC问题。只好临时想了一种解法。还是沿着prim算法的思路走，每次向已生成好的树里面增加一个新节点。只不过这次，每次都只增加关节节点集里面的节点。而寻找节点的时候，需要用Dijkstra算法。并且找到需要加入的关键点后，也需要把路径上的其他非关键点也加入进正在生成的树上面去。说到Dijkstra算法，复杂度是n^2, 再加上prim算法复杂度也是n^2，复杂度岂不是到达n^4？其实没有。因为每次使用Dijkstra算法，都把某一个点到其他所有点的路径长度都求出来了。而最终的结果，最坏也不过把所有节点两两之间的最短路径求出来，相当于填了一张n×n的表，n是节点数量。用一次Dijkstra算法可以填一行。总共n行所以复杂度是n^3。恩这里算是用到了动态规划。性能还算是可以接受吧。不过这个算法明显求不出精确解。我也没有证明过他求出的解究竟能多逼近，或者在哪些条件下能求出足够逼近的解。只不过是当时老师给的样例输入正好碰上是返回正确结果，就这样交卷了。

恩后来又在网上查了很多资料，貌似斯坦纳树研究的人还是很多的。不过搜到的资料大多是些没法下载的论文。。。所以也就荒废了没有继续看下去。。今后有机会在继续看吧。这次只是把过去的思路记录一下以后方便捡起来。