降阶回溯算法：解决图Steiner最小树的高效优化

图的Steiner最小树问题，简称GSMT，是一个经典的组合优化问题，它源自1971年由Hakimi和Levin提出的图的Steiner树问题，该问题被Karp证明为NP-完全问题。解决GSMT的主要挑战在于找到包含特定点集P的所有正则点以及可能的任意数量的非正则点S的最小生成树，同时确保所有正则点都被包含。尽管精确算法如支撑树穷举和拓扑枚举能够提供最优解，但其时间复杂度非常高，对于大规模问题不适用。 针对这一问题，本文提出了一种降阶回溯算法，它首先介绍了问题的基本概念和数学符号，探讨了该问题的一些关键数学性质。作者通过一种创新的方法，将问题分解为两个子任务：初步降阶子算法和下界子算法。降阶子算法着重于对问题中部分节点进行分支处理，从而显著降低了算法的时间复杂度。这种方法避免了对整个问题空间的全面搜索，提高了计算效率。 为了使算法易于理解和实施，文章提供了具体的实例和详细的分析过程。通过这种方法，非正则点的选择不再局限于全局最优，而是基于局部最优的决策，这使得算法能够在实际应用中找到相对较小规模的解决方案，尤其是在大规模问题中。 这篇论文不仅深化了对图的Steiner最小树问题的理解，还提出了一种有效且时间复杂度较低的求解策略，这对于解决实际问题，尤其是大规模实例，具有重要的理论和实践价值。研究者刘艳芳、宁爱兵和王英磊在文章中展示了他们的研究成果，对计算机工程与应用领域做出了贡献。