其实从6.1组队完成，我们就开始阅读书籍了，每2、3天讨论一次，对自己所负责的章节进行整理并分享，讨论算法思路和近似比的分析。《computational complexity》第1章和第2章是P&NP的概念，使我们对复杂性类别有基础的理解；《approximate algorithms》前8章是8个不同的近似算法，算是最基础的近似算法。我负责第1章和第5章的学习；我一共阅读4章内容，整理链接如下。
《computational complexity》
chapter 1、2 P versus NP（季炜丹）《approximate algorithms》
chapter 1 Introduction 近似比、最大匹配和最小点覆盖（季炜丹）chapter 5 k-center k-中心问题（季炜丹）阅读书籍后，了解了一些近似算法和复杂性类别的基础知识，我们开始针对BR-MTC问题设计近似算法。BR-MTC问题是NP问题，无法在确定性多项式时间内计算出精确解。我们需要先找到一个能计算出可行解的算法框架，再通过算法优化，使近似解逐步逼近最优解。通过阅读论文，发现BR-MTC问题与MST（最小生成树）有关联，借鉴解决MST问题的经典算法之一：prim算法，结合预算B，我提出近似算法框架；在框架的基础上，黄舒漪提出了可以从除根节点外的所有顶点出发，找最短路径，借鉴最短路的经典算法之一：Dijkstra，通过讨论，我和刘忠航将其简化从根节点出发，并提出基于Steiner Tree 斯坦纳树的进一步的优化算法。
验证程序的主体，图类的封装等，是由我们组员刘忠航独立完成的。我和黄舒漪共同完成了具体的程序验证过程，通过不同的点数、边数、最大权值和预算，反复循环得到大量数据，我编写程序可视化曲线图，分析近似算法的效果。
我们对近似算法这个领域都不是很熟悉，
P&NP、近似比、k-中心、最小点覆盖、最大匹配等一系列新名词；巧妙的近似比求解方法，如三角不等式还有边的端点覆盖等；常用的近似比求解套路：求不出OPT，就先求OPT的上限（对于求解最小化问题是找下限），然后希望我们的近似算法能找到上限的常数倍，那么这个常数就是近似比；这些新知识需要我们在短时间内理解并学会运用，是有难度的。
找到可行解，再逐步优化逼近最优解，是很常见的求解思路。其实BR-MTC问题的可行解有很多，BR-MTC与K-MST是目标对偶，很容易就联想到MST，经典的prim算法必定能得到可行解。 可是优化是有难度的，我们通过找反例来进行算法优化。 比如，对于下面这个图，预算为6时，最优解是蓝色部分的顶点数，为5。 但是基于prim算法的近似算法框架得到的近似解如下，顶点数为4。 我们只有先知道从r到A的最短路径，再去算生成树，才能得到更优解： 通过这个例子，我们把最短路径加入算法框架的初始顶点集，得到该例的最优解。
那么，如果有更多像A这样的点呢？如下图： 如果预算是29，那么最优解如下，顶点数为22； 结合最短路径的prim算法得到的解如下，顶点数为21； 所以我们应该先把所有像A的点，即连着一条大边，又连着许多条小边的点，先用最短网络连接起来，即通过steiner tree得到如下图的初始顶点集和边集，再进行生成树的寻找。
我们已经设计出近似算法了，而且也已经优化了，现在需要验证算法的性能，即近似解与最优解的关系，以及我们对于算法优化的效果。 近似比的直接分析难度很大，我们设计的启发式算法用程序验证算法效果，分析何时近似算法的优化最有效。这一步也是有难度的，我们需要设置不同的点数、边数、最大权值和预算，大量随机生成图，代入算法得到数据，通过图可视化来分析变量对于优化效果的影响。
我们跑了大量数据，验证算法优化的确有效，且发现预算与顶点数的比值在50%左右时，优化效果最好。以下是可以验证我们发现的2个例子。
给定顶点500-1500，间隔100，预算为400，500，600，700；纵坐标是优化前后的顶点数差值，即优化效果的直观体现
1). 当顶点数为800时，预算400的红色线优化效果较好；2). 当顶点数为1200时，预算600的绿色线优化效果较好；3). 当顶点数为1400时，预算700的黄色线优化效果较好；可以看出，预算与顶点数的比值在50%左右，优化效果最好。
第2个例子：验证100以内的顶点数，最优解、近似解的关系
1). 红色线与绿、蓝色线存在差距，即最优解与近似解存在差距；2). 绿色线是优化后的近似解，永远在蓝色线上方，甚至有时候与红色线重合；即优化后得到的近似解比优化前得到的近似解更加接近最优解；以上两点都符合我们的预期。
