本文共 1426 字，大约阅读时间需要 4 分钟。
无向图的最大割问题
通过上机实验，要求深度掌握分支限界法的问题描述、算法设计思想、程序设计。
利用优先队列式的分支限界思想，根据题目所给出的条件，求解问题，计算出无向图的最大割。
无向图的最大割问题与最大团问题类似，都可以看作图G的顶点集V的子集选取问题。因此可以用子集树来表示问题的解空间，可以用回溯算法或分支限界法来解题。顶点集内顶点间的边不属于割边，割边是与顶点集U外部顶点与内部相连的边；顶点集U的所有割边构成图的一个割。
与装载问题的剪枝条件类似，如果当前活结点的割边数加上剩余边数（非割边且非顶点集内部顶点间的边）小于等于当前最优值，则可以剪去右子树；最优值的更新应该在每一次进入左子树时进行，及时剪枝。
用最大优先队列存储活结点表，活结点的优先级可以定义为该结点的割边数（当前割边数最大的结点成为下一扩展结点）。
结点信息，包括层次、割数、剩余边数、解向量，结点的构造函数；重构操作符，以结点的割数表示优先级。
利用STL库中的优先队列来实现；子结点（要添加的结点）继承父节点的相关结点信息并更新层数；根据函数的第二个参数判断其是不是左孩子，如果不是则解向量对应位置赋0即可，否则是左孩子就要更新其割数和剩余边数：遍历一次所有顶点，如果顶点v与要加到顶点集中的顶点u间有边，那么判断v顶点是否是顶点集中的顶点，如果是，则割边转化为了顶点集中顶点间的边，cut--；否则是顶点集之外的边，那么剩余的边转化为割边，cut++，e--。
通过时间函数QueryPerformanceFrequency与cpu的主频频率得到程序段的运行时间，可以精确到微妙，比clock函数更精确一些。
①判断当前是否遍历完所有的层，遍历完则更新最优值与最优解；②否则将左子结点加入到优先队列；③判断右子结点是否满足剪枝条件，不满足则加入到优先队列；④优先队列的头结点为扩展结点。
运行结果正确。
最大割问题的解空间为子集树，假设无向图G的顶点数为n，那么搜索子集树的时间复杂度为O（2n）。剪枝策略的时间复杂度为O（1），因此总的时间复杂度为O（2n）。
每一个活结点都需要O（n）的空间来存储结点信息，而子集树一共最多有2n结点进行存储，所以空间复杂度上界为Ω（n2n）。
通过这次实验，我回顾了回溯算法与分支限界法之间的异同点，对剪枝函数有了更深层次理解，这道题比之上面的两道题都要难，难点就在于剪枝函数以及解空间树的遍历顺序。这道题的核心在于加入顶点到顶点集后相应边的变化，割边变为顶点集内部顶点间的边以及剩余边变成割边这两种情况的理解。到这里课程实验就基本上结束了，通过这四次实验，15道线下实验题，我逐步掌握了课本中从第二章分治法到最后一章随机算法的核心思想，对整个课程有了更深的理解。
转载地址：http://qlwv.baihongyu.com/