论文部分内容阅读
最小Steiner树(Steiner Minimal Tree，SMT)问题是一个非常经典和重要的组合优化问题，它寻求在某种距离意义下将给定的点用最短的网络连接起来。最小生成树(Minimal Spanning Tree，MST)也是一个非常重要的组合优化问题。它只用以给定的点作为网络中边的端点，目标同样是将所有给定的点以最短的方式连接起来。最小Steiner树并没有对网络中边的端点加以任何限制，它可以引入新的点或者使用给定点以外的点，称为Steiner点，来作为连边的端点，以使所得到的连接网络的边长之和尽可能小。因为最小生成树可以在多项式时间内构造出来，而最小Steiner树不可以(除非P=NP)。所以最小生成树可以作为最小Steiner树的一个近似解，这两个树的长度之比的下确界称为Steiner比.
最小Steiner树问题问题有三个主要的研究模型：欧氏平面上的最小Steiner树问题，Manhattan距离意义下的最小Steiner树问题和网络中的最小Steiner树问题。这些最小Steiner树问题在各种网络的优化设计中有广泛的用途，因此相关研究几十年来一直是组合优化领域的一个热点。特别是在上个世纪九十年代，在欧氏平面上的最小Steiner树研究领域中，先后出现了三个大的突破：堵丁柱与黄光明证明了Gilbert—Polak关于Steiner比的猜想，Zelikovsky从理论上证明了存在比最小生成树更好的近似算法，Arora和Mitchell各自找到了求解最小Steiner树问题的多项式时间近似方案.
随着大规模集成电路技术的发展对布线要求的提高，固定均匀方向上的最小Steiner树问题也引起了人们的关注。这个问题也称为λ-几何下的最小Steiner树问题。特别地，当λ=2，3，4时，连线的合法方向数目分别为2个、3个、4个，其所对应的问题分别称为Rectilinear Steiner树问题，Hexagonal Steiner树问题，Octilinear Steiner树问题，这是三种有重要应用背景的情形.本文研究λ-几何下的最小Steiner树问题，主要比较当λ=2，3，4时，最小Steiner树的长度.
第一章中首先简述最小Steiner树问题的历史，然后介绍固定均匀方向上的最小Steiner树问题及其研究背景，最后概述本文的主要工作.
第二章中主要讨论增加布线合法方向的数目，对最小Steiner树长度的影响。在大规模集成电路技术中，最基本和传统的布线方向为水平和垂直两个方向(即λ=2情形).已有的模拟实验结果表明，当可能合法的布线方向数目从两个增加到三个或者四个以后(即λ=3，4情形)，最小Steiner树的长度可以有显著的减少。为了从理论上分析减少的程度，首先确定了在不同几何结构下最小Steiner树长度比的界。随后假定给定的点随机均匀分布在一个单位正方形中，然后比较了当λ=2，3，4时，最小Steiner树长度的期望值。初步的理论分析说明，给定点的数目越多，最小Steiner树长度的减少越不明显。同时也表明布线方向数目从三个增加到四个所带来的改进，不如布线方向数目从二个增加到三个所带来的改进显著。最后考虑了在任意多个点时，在λ=2，4下最小Steiner树的长度的平均值的上界与下界.
第三章中主要讨论当布线的可能合法方向的数目不变时，旋转布线的方向对最小Steiner树长度的影响。当给定的点的数目充分大时，在平均意义下，旋转布线的方向，对减少最小Steiner树长度的作用不是很大。在几何结构可以旋转的假定下，定义了两个新的Steiner比问题。在第一个推广的Steiner比中，用在旋转下的最小Steiner树与最小生成树分别代替经典定义中的最小Steiner树与最小生成树。第二个Steiner比中，用在考虑旋转情况下最小Steiner树和最小生成树长度比的最大值，来代替经典定义中的最小Steiner树和最小生成树长度的比.给出的两个推广后的Steiner比可以作为最小Steiner树与最小生成树长度的比的下界。刻画了这三个Steiner比的关系，当λ=2，3，4时，分别给出了在三个点的情形下，推广的Steiner比的值；对任意多个点的情形，也给出了推广Steiner比的上界.
第四章中主要讨论在一些特殊情况下，最小Steiner树问题。因为最小Steiner树问题是NP-困难的，所以通常除了寻找一般情况下最小Steiner树问题的(多项式时间)近似算法，对于一些特殊情况寻找多项式时间的精确算法也是很重要的一个研究方向。网格在λ=2时，最小Steiner树与最小生成树相同，因此讨论它在λ=4下的最小Steiner树，也是很有意义的。对于某些特殊情况，得到了最小Steiner树的完整刻画；而对于一般情况，得到了最优的限制Steiner树的完整刻画.