算法分析与设计第 4 次实验

时间

2020.5.17

 实验名称

无向图的最大割问题

实验目的

通过上机实验，要求深度掌握分支限界法的问题描述、算法设计思想、程序设计。

实验原理

利用优先队列式的分支限界思想，根据题目所给出的条件，求解问题，计算出无向图的最大割。

实验步骤

 问题分析：

与最大团问题类似，都可以看作图G的顶点集V的子集选取问题；

因此可以用子集树来表示问题的解空间，可以用回溯算法或分支限界法来解题；

顶点集内顶点间的边不属于割边，割边是与顶点集U外部顶点与内部相连的边；顶点集U的所有割边构成图的一个割；

举例：

对于该无向图：

当顶点集U={1}时，2,3,4∈V-U，(1，2)、(1，3)、(1，4)∈E，为顶点集U的割边，与顶点1相连的边都是U的割边，割边数是3

当顶点集U*={1，2}时，3,4,5,6∈V-U*，(1,3)、(1,4)、(2,5)、(2,6)∈E，为顶点集U*的割边

剪枝条件：

与装载问题的剪枝条件类似，如果当前活结点的割边数加上剩余边数（非割边且非顶点集内部顶点间的边）小于等于当前最优值，则可以剪去右子树；最优值的更新应该在每一次进入左子树时进行，及时剪枝；

优先队列式分支限界法解题：

用最大优先队列存储活结点表，活结点的优先级可以定义为该结点的割边数（当前割边数最大的结点成为下一扩展结点）；

 算法步骤：

1、加入根结点到优先队列（此时顶点集U为空，cut=0，剩余边e=m）；

2、从优先队列中取出头结点作为当前扩展结点；

3、对当前扩展结点，先将它的左孩子加入到优先队列（对应着下一层的顶点加入顶点集U），接着用剪枝策略判断右子树是否可以剪去，不可以则同样加入优先队列；

4、 重复步骤2和3，直到活结点队列为空。

关键代码

关键代码（带注释）

1. 结点信息

  结点信息，包括层次、割数、剩余边数、解向量，结点的构造函数；

重构操作符，以结点的割数表示优先级；

2. addNode添加结点函数

利用STL库中的优先队列来实现；子结点（要添加的结点）继承父节点的相关结点信息并更新层数；根据函数的第二个参数判断其是不是左孩子，如果不是则解向量对应位置赋0即可，否则是左孩子就要更新其割数和剩余边数：

遍历一次所有顶点，如果顶点v与要加到顶点集中的顶点u间有边，那么判断v顶点是否是顶点集中的顶点，如果是，则割边转化为了顶点集中顶点间的边，cut--；否则是顶点集之外的边，那么剩余的边转化为割边，cut++，e--。

3. 计算时间部分代码

通过时间函数QueryPerformanceFrequency与cpu的主频频率得到程序段的运行时间，可以精确到微妙，比clock函数更精确一些；

4. 搜索子集树过程代码

①判断当前是否遍历完所有的层，遍历完则更新最优值与最优解；

②否则将左子结点加入到优先队列，

③判断右子结点是否满足剪枝条件，不满足则加入到优先队列；

④优先队列的头结点为扩展结点；

测试结果

运行结果截图及分析

对于题目样例：

     输出结果：

运行正确；

时间复杂度分析：

    最大割问题的解空间为子集树，假设无向图G的顶点数为n，那么搜索子集树的时间复杂度为O（2n）

剪枝策略的时间复杂度为O（1），因此总的时间复杂度为O（2n）

 空间复杂度分析：

每一个活结点都需要O（n）的空间来存储结点信息，而子集树一共最多有2 n结点进行存储，所以空间复杂度上界为Ω（n2n）。

实验心得

通过这次实验，我回顾了回溯算法与分支限界法之间的异同点，对剪枝函数有了更深层次理解，这道题比之上面的两道题都要难，难点就在于剪枝函数以及解空间树的遍历顺序；

这道题的核心在于加入顶点到顶点集后相应边的变化，割边变为顶点集内部顶点间的边以及剩余边变成割边这两种情况的理解。

到这里课程实验就基本上结束了，通过这四次实验，15道线下实验题，我逐步掌握了课本中从第二章分治法到最后一章随机算法的核心思想，对整个课程有了更深的理解。