最小斯坦纳树解决最优布线问题.docVIP

用最小斯坦纳模型解决布线问题问题描述给出平面上若干个点（不超过10个），用一些水平或者竖直的线段（线段的端点不一定是这些要连接的点）将这些点连接起来，要求线段的总长度最小。如下图所示，其中由红色圆环和黄色实心构成的圆形表示需要连接的点。它们的坐标就是程序的输入信息。绿色的线条表示程序经过计算得到的最优布线方案。注意到，图中还有一些黄色的点。这些点是程序在运行过程中计算出来的点，这些点的位置正好是某一个需要连接的点在这些横着或竖着的线段上的投影。我们可以看到，线段的端点可以是黄色的点也可以是必须要连接的点。算法分析观察上图，我们发现每一条线段上都有若干个点，这些点可能是黄色的点也有可能是需要连接的点。每一条线段上的点将这条线段分为一个一个的小线段。这些小线段之间的交点只可能是小线段的端点。现在我们的问题变为，给出平面上一些需要连接的点集A。在平面上选择一些不属于A的点，这些点组成的集合称为B。设C=AB。我们找一些的水平或竖直的并且端点都属于C的线段，能将C中所有的点连接起来，并且线段的总长度最小。我们称这个问题为问题二。显然问题二和原问题是等价的。我们先来分析一下为使线段的总长度最小，B集合内点的选取可以缩小到什么范围。我们有如下结论：B集合中每一个点的横坐标一定是A集合中某个点的横坐标；B集合中每一个点的总坐标一定是A集合中某个点的纵坐标。为了说明这个结论，我们观察上图。我们能够发现，B集合（所有黄色的点）中任意一个点，对于经过它的水平直线一定穿过至少一个A集合中的点；对于经过它的竖直直线一定穿过至少一个A集合中的点。这个结论的证明思路比较简单，所以这里略去。有了上面这个结论，我们可以对问题二进行初步的处理。对于输入的需要连接的同一平面上的点集A，我们考虑将每个A中的点用一条水平的直线和一条竖直的直线穿过。如果平面上某个点是某一条水平直线和某一条竖直直线的交点，并且这个点不是A中的点，那么我们将这个点加入集合D。我们的算法求出的B集合一定是D的子集。我们可以看到，A中的点和D中的点以及所有穿过A中的点的水平或者竖直的直线构成了一个网格。参见下图，红色圆环黄色实心的圆形表示A集合中的点，黄色的点表示D集合中的点。而我们的算法求解问题二时最后得出的线段集合中的每一条线段一定是下图网格中某两个相邻点的边我们构建一个这样的图G，图的点集V和AD之间存在一一映射的关系。我们称这个映射为g(x)。其中xV，g(x)属于AD。接下来我们来考虑G的边集E。首先，我们称AD以及穿过A的横线和竖线组成的网格为W。对于V中任意的两个不同的点x和y，如果g(x)和g(y)在网格W中是相邻的，那么在G中，x和y之间有边相连，边的权值为g(x)与g(y)在平面上的曼哈顿距离；否则x和y之间没有边相连。这时，我们将问题转化为：给一个无向图G，设G的点集为V。再给出一个点集A，其中A是V的子集。要求在图G中找出一个联通子图G，使得G的点集包括A中所有的点，并且G的边权和最小。我们称这个问题为问题三。显然问题三需要求解的子图G一定是一棵树。而问题三就是一个经典的最小斯坦纳树问题。最小斯坦纳树问题是一个NP问题，目前没有一个多项式算法可以求解。但是一开始的问题描述已经说了，平面上需要连接的点不超过10个，于是在问题三中，A集合的大小也不会超过10。这样，我们就可以用一个基于动态规划的算法来解决问题三。首先，我们定义集合state是A的某个子集，定义root是G中某个顶点。我们用dp(state, root)表示图G中能够连接stateroot中所有点的最小斯坦纳树的边权和。那么，问题三所求的最小斯坦纳树的边权和sum可以满足以下公式sum=mindpA, i iV接下来，我们给出dp(state, root)的状态转移方程。fstate, root=mindpstate, root+dpstate-statestate是state的子集gstate,root=mindpstate,root+w(root,root)root与root相邻dpstate,root=minfstate,root,gstate,root上面的公式中w(root,root)表示图G中连接root和root的边的边权。计算dp(state,root)时，如果直接按照上面给出的状态转移方程去计算是不太容易的，虽然f(state,root)容易计算，但是我们一开始并不能知道g(state,root)的拓扑关系。我们可以这样计算dp(state,root)。我们先按照元素个数从小到大的顺序枚举state，然后利用f(state,root)的状态转移方程求解出G中所有节点v的f(state,v)的值。然后我们构造这样一个新图G，G的点集为Vs，V是G的点集，且s不属于V。然后我们按照以下方法构造G的边集E。初始时，令E = E 。E是G的边集枚举G中所有的点v，在E中加入s和v之间的一条边，边的权值为f(state, v)。这样我们就能构造完E，进而G也就构造完成。我们在G中求点s到其他所有节点v的最短路径dist(s,v)。那么dist(s,v)的值就是dp(state,v)的值。求最短路径时我才用的算法是堆优化的dijkstra算法。另外在实现该算法时，我用0到2A-1之间的整数来表示state。上述算法是求最小斯坦纳树边权和的。而方案的选择已经体现在上述算法中，这里不再详细描述。上述算法求解问题三的时间复杂度是O(3AA2log)。而我们可以用一个多项式的算法将原始问题的输入转化成问题三需要的条件（图G和点集A）。于是原始问题的时间复杂度也就是O(3AA2log)。程序测试我编写了一个java工程用来实现和测试上文所述的算法。源代码存放在目录src中。生成的类文件存放在目录bin中。在终端运行StainerTree.class（目录bin中）后，输入以下指令程序会完成不同的功能。1、 在终端中输入make t n fileName后程序会随机生成t组数据，每组数据的点数为n，点的坐标范围在0到950。这t组数据都保存在名为fileName的文件中。2、 在终端中输入show inputFileName outputFileName后程序会从以inputFileName命名的文件中读取第一组数据并利用最小斯坦纳树的模型计算该组数据的最优布线方案。并将布线方案以图片的形式保存在以outputFileName命名的文件中，并在终端显示最优布线的长度。3、 在终端中输入test inputFileName outputFileName后程序会从以inputFileName命名的文件中读取所有的数据并利用最小斯坦纳树模型计算每一组数据的最优布线方案。并将数据组号、点集大小、计算出来的布线方案的长度、运行时间等信息保存到以outputFileName命名的文件中。如果在终端只输入test inputFileName，那么这些信息将在终端显示。运行结果可以参见下图。如图所示，输入make 30 10 test.txt表示生成30组数据；输入test test.txt表示利用test.txt中的数据测试算法，并将算法的测试结果输出到终端。我们可以图上的终端看到测试结果。终端显示了一个30行4列的表格。第一列表示第几组数据，第二列表示该组输入数据中需要连接的点的个数，第三列表示最优布线的长度，第四列表示算法用时。我们发现，这个算法计算10个点的布线只需要200多毫秒；输入show sample