论文部分内容阅读
本文对传统的网络最优化问题灵敏度分析的理论内涵进行了扩展,指出最短路及最小支撑树的灵敏度分析应包含两个内容:(1)弧(边)的容忍度分析;(2)关键弧(边)和关键顶点问题。前者研究的是为保证最短路或最小支撑树的结构稳定,弧(边)权值变化的最大范围,对应了传统的网络最优化问题的灵敏度分析;后者研究的是,如何寻找关键弧(边)或关键顶点,使得与其它弧(边)顶点相比,关键弧(边)或关键顶点失效后,最短路权值的增量最大。目前的最短路灵敏度分析主要针对无向网络,而本文给出了网络中最短路的灵敏度分析算法,其中弧容忍度分析算法和关键弧算法的时间复杂度均为O(m+nlogn),n,m分别为网络的顶点数和弧数。对多条弧的容忍度分析,本文给出了最短路弧容忍度分析基本公式。此外,通过设计辅助网络,我们将最短路关键顶点问题在线性时间内转化为关键弧问题加以解决。在最小支撑树的灵敏度分析方面,Seth Pettie给出了时间复杂度为O(mlogα(m,n))的最小支撑树树上边的容忍度分析算法(称之为SP算法),该算法是现有同类算法中最优的。本文将该算法和Set-Maxima问题相结合,从而给出了完整的最小支撑树边的容忍度分析算法,其时间复杂度为O(m+nlogn)。之后一个简单的时间复杂度为O(mn)的最小支撑树关键边算法,使我们更好地理解了替代边问题和关键边问题之间的关系。最后,通过对SP算法的修改,本文给出了时间复杂度同样为O(m+nlogn)的最小支撑树关键边算法。在通信网络中,最短路在路由算法设计中得到了广泛应用,而采用最小支撑树则是广播和多播的常用方式。本文指出,最短路及最小支撑树的灵敏度分析的应用价值在于:弧(边)的容忍度分析为通信链路可能发生的拥塞现象提供预警,为路由重构提供触发门限;关键弧(边)和关键顶点问题则为路由备份提供依据。本文还基于最短路弧容忍度分析基本公式,建立了通信网络中信息传输路由的一种的可靠性模型,该模型是面向用户的,且能够充分反映业务要求。同时本文还结合通信网络实际给出了一种最短路关键弧的新概念——稳定型关键弧。