论文部分内容阅读
针对带有度约束的最小生成树问题，给出了一种快速近似算法．首先给出了快速近似算法的核心思想：在不违反度约束和不形成圈的前提下，每次加入权最小的边．其次给出了实现快速近似算法的具体步骤，并且证明了该算法的计算时间复杂度是图的顶点数的多项式函数，证明了算法的有效性定理．大量的数值试验表明该近似算法性能良好．最后在此算法的基础上，给出了求解TSP问题的一种快速近似算法．