题目：CMST问题的算法的研究与实现

随着人类步入21世纪，以计算机网络和通信网络为代表的各种网络在世界范围内正处于迅猛的发展阶段，无论是西方发达国家还是发展中国家，网络设计的经济综合优化问题都是一个重要的研究课题。其中，经济指标永远是网络设计者追求的最重要的目标之一。由于网络设计中存在诸多的约束限制条件，使得寻求这一目标的最优解的过程变得尤为复杂。网络设计经济综合优化问题 (Network Economic Synthesis, NES) 正是针对这一目标而建立的模型。NES是网络设计研究中的基础问题之一，具有流量约束的最小生成树问题(Capacitated Minimum Spanning Tree, CMST)问题正是这一基础问题的基本的且重要的子问题。本文首先分析了国内外对CMST问题的研究进展，指明本文的研究内容和目标。通过从数学角度对CMST问题进行模型理论分析，并分别从精确算法和启发式算法两方面分析了可供选的研究方法，得出该论文的研究方案和对研究方法进行评估的标准。目前已有的基于边的精确算法虽然处于国际领先水平，但是通过对该分支定界方法的下界公式进行分析，发现现有算法的搜索策略可以进一步优化。该论文提出基于PEMST的快速剪枝前进策略，并以此为基础设计并实现了新的精确算法，降低了原有算法的局部复杂度，并通过实验对比结果表明了新算法的性能改善。对于基于点的分支定界算法，该论文结合分支方法提出了更紧的下界构造策略，继而得到新的定界公式，改进了原有算法的求解效率。对启发式算法的研究和探索主要集中在邻近搜索算法中的邻居结构的产生规则，提出新的移动规则，得出改进的启发式算法。结合这一改进的特点，将其用于产生精确算法的初始解，使得精确算法的性能有了极大的改善。论文工作的特点体现在如下四个方面：1). 研究并实现了增强型的基于边的分支定界算法，提高了精确方法求解CMST问题的效率。2). 对现有的基于点的分支定界算法提出了更紧的下界公式，得到效率更高的精确算法。3).研究并实现了基于改进的邻居移动规则的邻近搜索算法，得到了快速收敛的启发式算法。4). 将改进后的启发式算法应用于精确算法的初始解产生过程，进一步加快了精确算法的求解速度。