创新实训团队记录 : 为BR-MTC问题设计近似算法

• 阅读书籍和论文
• 近似算法设计思路变化总结
• • 算法框架
  • 改变初始顶点集
  • 继续添加路径，作为新的初始顶点集
• 程序验证
• • 近似解与最优解存在差距&&优化后的近似解比优化前更逼近最优解
  • • 构建最优解已知的图
    • 比较最优解和近似解（优化前、后）
  • 优化效果在什么时候达到最好

阅读书籍和论文

《computational complexity》

• chapter 1、2 P versus NP（季炜丹）

《approximate algorithms》

• chapter 1 Introduction 近似比、最大匹配和最小点覆盖（季炜丹）
• chapter 2 Set Cover 分层技术求解顶点覆盖问题（刘忠航）
• chapter 3 Steiner Tree and TSP 斯坦纳树和旅行商问题（孙凡雯）
• chapter 4 Multiway Cut and k-Cut 最小割和K割问题（黄舒漪）
• chapter 5 k-center k-中心问题（季炜丹）
• chapter 6 Feedback Vertex Set 反馈顶点集问题（刘忠航）
• chapter 7 Shortest Superstring 最短超串问题（孙凡雯）
• chapter 8 Knapsack 背包问题的多项式时间近似解（黄舒漪）

“A 2+ε approximation algorithm for the k-MST problem”

近似算法设计思路变化总结

算法框架

• 1). 输入：输入一个给定的加权无向图 $G=(V,E)$ ，在图的结点中给定一个根结点$r\in V$，并且给定一个最大的预算范围B
• 2). 初始化：$V_{new}=$ {$r$}, $E_{new}=$ { }为空；
• 3). 重复下列操作，直到$V_{new}=V$:
  • a. 在集合E中选取权值最小的边$<u,v>$，其中$u$为集合$V_{new}$ 中的元素，而$v$不在集合$V_{new}$ 当中，并且$v\in V$（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
  • b.将$v$加入集合$V_{new}$中，将$<u,v>$边加入集合$E_{new}$中；
  • c.将集合$E_{new}$中的边权值相加，未超过B则返回步骤a；超过B，则将新加入的边移出集合$E_{new}$中，跳出循环；
• 4). 输出：使用集合$V_{new}$和$E_{new}$来描述所得到的包含根节点r的子树。

改变初始顶点集

优化步骤2). 初始化：$V_{new}=$ {$r$}, $E_{new}=$为空
优化：分成两步

• 一、计算根节点$r$到其他所有节点的最短路径，得到$n-1$条最短路径，每一条最短路径的顶点集和边集用$V_{shortest},E_{shortest}$;
• 二、基于初态顶点集$V_{shortest}$、边集$E_{shortest}$找子树，对比子树顶点数，选取最优子树

一、计算根节点$r$到其他所有节点的最短路径，得到$n-1$条最短路径，每一条最短路径的顶点集和边集用$V_{shortest},E_{shortest}$；

• 1). 将根节点$r$作为初始点，看作一个集合，其他$n-1$个点看作一个集合；
• 2). 根据初始点，求出其它点到初始点的距离$d[i]$（若相邻，则$d[i]$为边权值；若不相邻，则$d[i]$为$\infty$）
• 3). 选取最小的$d[i]$加入$E_{shortest}$(记为$d[x]$)，并将此$d[i]$边对应的点(记为$x$)加入集合$V_{shortest}$；
• 4). 再根据$x$，更新跟 $x$ 相邻点 $y$的 $d[y]$值：$d[y]=min${$d[y],d[x]+w[x][y]$}，即松弛操作；
• 5). 重复3)、4)，直到所有顶点都在集合$V_{shortest}$内，$d[i]$即为一条最短路径；

二、基于初始顶点集$V_{shortest}$找子树，对比子树顶点数，选取最优子树

• 1). 对于每一条最短路径得到的初始顶点集$V_{shortest}$和初始边集$E_{shortest}$，我们进行之前找子树的操作，共$n-1$次循环，得到$n-1$棵子树；
• 2). 比较$n-1$棵子树的顶点数，选择最多顶点数的子树，作为我们的输出结果

继续添加路径，作为新的初始顶点集

我们认为对于步骤2)，仍可以继续优化。
目前我们已经有$n-1$条最短路径作为$n-1$个初始顶点集，基于不同的顶点集得到不同的子树，得到$n-1$棵子树，选择$n-1$棵子树中顶点数最多的作为输出结果；我们可以添加其他的路径作为新的初始顶点集，如果基于这种顶点集得到的子树顶点数更多，我们就达到了优化效果。
至于，选择添加怎样的路径作为新的初始顶点集，我们提供了一种思路。

• 我们选择某些“具有代表性”的点，构成集合$V_{represent}$;如何选择：
  • 1). 我们设置参数：大边值$bigdis$，边数$num$，小边值$smalldis$；
  • 2). 先遍历所有边找到$weight\ge bigdis$的边；放在集合$E_{big}$；
  • 3). 遍历集合$E_{big}$中所有边的左右端点，放在集合$V_{big}$；
  • 4). 遍历集合$V_{big}$中所有点的所有“覆盖”的边，如果对于集合中的一个点$v$，所有“覆盖”的边中$weight\le smalldis$的边数超过$num$，那么我们将这个点$v$加入集合$V_{represent}$；
• 将根节点$r$加入集合$V_{represent}$，计算集合$V_{represent}$内所有顶点的steiner tree，形成初始顶点集$V_{represent}$和初始边集$E_{represent}$

程序验证

近似解与最优解存在差距&&优化后的近似解比优化前更逼近最优解

BR-MTC问题，显然，当 $B$等于图 $G$ 最小生成树的权重之和时，该最小生成树是该问题的解。而当预算$B$ 是作为问题输入给定的一个新参数，这使问题具有了 $NP$ 性。当$P\ne NP$ 成立时，对于该类问题，不存在多项式时间内求得精确解的算法。
但是我们需要用程序验证，最优解和近似解的差距，于是我们在这里考虑逆向思维。我们通过构造出最优解已知的图，基于这样的图运行近似算法。

构建最优解已知的图

• 1). 给定参数$V、E$，最大权值$maxCost$，障碍分支个数$h$；
• 2). 计算出一个障碍分支所需要的点数$v1$和边数$e1$，(我们定义下图为障碍分支)，蓝色部分为$(v2,e2)$；
• 3). 根据剩余的顶点数$v’=V-v1$和$e’=E-e1$，随机生成图$G=(v’,e’)$，并求出图$G$的最小生成树，最小生成树的耗费加上障碍分支（蓝色部分）的耗费（即$e2$）为障碍图的预算；
• 4). 最小生成树上加入障碍分支，得到障碍图$G’=(v’+v1\ast h,e’+e1\ast h)$，输出障碍图$G’$，预算$B’$；
• 5). 此时，最优解就是$v’+v2\ast h$
  

比较最优解和近似解（优化前、后）

从下图可以看出：

• 1). 红色线与绿、蓝色线存在差距，即最优解与近似解存在差距；
• 2). 绿色线是优化后的近似解，永远在蓝色线上方，甚至有时候与红色线重合；即优化后得到的近似解比优化前得到的近似解更加接近最优解；

以上两点都符合我们的预期。

以下是举几个例子：

优化效果在什么时候达到最好

给定顶点500-1500，间隔100，预算为400，500，600，700；纵坐标是优化前后的顶点数差值，即优化效果的直观体现

• 1). 当顶点数为800时，预算400的红色线优化效果较好；
• 2). 当顶点数为1200时，预算600的绿色线优化效果较好；
• 3). 当顶点数为1400时，预算700的黄色线优化效果较好；

可以看出，预算与顶点数的比值在50%左右，优化效果最好

总结

以上是生活随笔为你收集整理的创新实训团队记录：为BR-MTC问题设计一个近似算法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。