1. 项目概述：从一道经典难题说起

如果你在算法竞赛或者图论研究的圈子里待过一阵子，大概率会听说过“最大割问题”。这可不是什么新潮的概念，它就像算法世界里的“老朋友”，看似简单，却总能以各种方式让你重新认识计算的边界。简单来说，给你一张图，比如一个社交网络或者一个电路连接图，你的任务是把图里的所有节点分成两个阵营，目标是让连接这两个阵营的“跨阵营边”数量尽可能多。听起来是不是有点像在玩一个策略游戏？但别小看它，这个问题是计算机科学中“NP难”问题的经典代表之一，意味着在一般情况下，我们很难在多项式时间内找到绝对最优解。

这恰恰是它的魅力所在。最大割问题绝不仅仅是一道抽象的数学题。在集成电路设计里，它关乎如何最优化地布局元件以减少信号干扰；在社交网络分析中，它可能对应着识别出观点最对立的两个群体；甚至在机器学习的一些聚类算法里，也能看到它的影子。理解最大割，就等于掌握了一把钥匙，能帮你打开优化、近似算法和计算复杂性理论的多扇大门。今天，我就结合自己这些年折腾算法和解决实际优化需求的经验，来拆解一下这个“老朋友”，聊聊它的核心、解法、实操中的坑，以及那些教科书里不太会写的“手感”。

2. 核心概念与问题形式化拆解

要动手解决问题，首先得把问题本身看得清清楚楚。最大割问题的定义非常直观，但里面的门道需要我们一层层剥开。

2.1 图与割的严格定义

我们首先得统一语言。这里说的“图”，通常指无向图 G = (V, E)，其中 V 是顶点的集合，E 是边的集合。每条边连接两个顶点。所谓一个“割”，就是指将顶点集合 V 划分成两个互不相交的子集 S 和 T（即 S ∪ T = V 且 S ∩ T = ∅）。这个划分本身，我们就称之为一个割 (S, T)。

那么，这个割的“权重”或者“大小”指的是什么呢？就是所有那些一头在 S 里、另一头在 T 里的边的集合。这个边的集合，记作 δ(S)，它的基数（边的条数）或者如果边有权重的话就是所有权重之和，就是这个割的值。最大割问题，就是要找到所有可能的割 (S, T) 中，使得 |δ(S)|（或权重和）最大的那个。

举个例子，假设我们有一个4个顶点的环（正方形），顶点是A, B, C, D，边是 (A-B), (B-C), (C-D), (D-A)。如果我们把 A 和 C 分到集合 S，B 和 D 分到集合 T，那么跨阵营的边有哪些？A-B（A在S，B在T），B-C（B在T，C在S），C-D（C在S，D在T），D-A（D在T，A在S）。看，四条边全部都是跨阵营的！所以这个割的值是4，对于这个环来说，这就是最大割（因为总边数就4条，全被切开了）。但如果我们把 A 和 B 分到S，C和D分到T，那么跨阵营的边就只有 A-D, B-C 两条，值就是2。

注意：这里有一个初学者容易混淆的点。割 (S, T) 和 (T, S) 被视为同一个割，因为划分是无序的。我们关心的是两个集合之间的边，而不是哪个集合叫S哪个叫T。

2.2 NP难的本质与为何“难”

为什么最大割这么出名？因为它被证明是NP难的。这意味什么？简单粗暴的理解就是：当图的规模（顶点数 n）变大时，想要找到那个绝对最优的最大割，所需要的时间在最坏情况下会随着 n 增长而指数级爆炸。你无法找到一个“万能高效算法”对所有图都快速求出精确解。

其NP难性的证明通常可以通过从另一个著名的NP难问题（比如“最大布尔可满足性问题 Max-E3-SAT”）进行“规约”来完成。这个证明过程本身很精巧，但对我们实践者来说，更重要的启示是：不要执着于对所有情况都追求精确解，对于大规模问题，我们必须转向寻找“足够好”的近似解或利用问题本身的特殊结构。这也是为什么研究最大割的近似算法和启发式算法如此重要的原因。

2.3 加权最大割与更一般的场景

刚才我们讨论的是边没有权重的情况，每条边价值相同。但实际问题中，边往往带有权重。比如在电路设计里，不同信号线之间的干扰程度不同；在社交网络里，不同用户之间的连接强度（互动频率）也不同。这就引出了加权最大割问题：每条边 e 有一个非负权重 w(e)，我们要最大化跨割边的权重之和 Σ_{e ∈ δ(S)} w(e)。

加权版本不仅更贴合实际，也使得问题在算法设计上有了更多变化。有些算法对无权图很有效，但加上权重后可能就需要调整。不过，核心的NP难性质并没有改变。

3. 经典求解算法思路剖析

面对一个NP难问题，算法工具箱里通常有几类武器：精确算法（用于小规模问题）、近似算法（保证解的质量在一定比例内）、以及启发式算法（不保证理论界限，但实际效果好）。我们一一来看。

3.1 精确算法：穷举、分支定界与整数规划

对于顶点数 n 较小（比如 n <= 30）的图，我们依然可以尝试寻找精确最优解。

1. 暴力穷举法：每个顶点有两种选择：属于 S 或属于 T。所以总共有 2^n 种可能的划分。对于每一种划分，计算割的值需要检查所有边，是 O(m) 的时间（m为边数）。所以总时间复杂度是 O(2^n * m)。当 n=20 时，2^20 约等于100万，尚可应付；n=30时，就超过10亿了，基本不可行。这是最直接但也最慢的方法。

2. 分支定界法：这是一种系统化的智能枚举。它通过构建一棵搜索树来枚举所有可能解，但同时利用“界”来剪掉不可能产生更优解的分支。对于最大割问题：

• 上界计算：对于一个部分解（部分顶点已分配阵营），剩余未分配顶点可能贡献的最大割值是多少？一个简单的上界是：已确定的割值 + 所有与未分配顶点相连的边的权重之和（因为最乐观的情况是所有连着未分配顶点的边最终都成为割边）。如果这个上界已经小于当前已知的最佳解，那么这条分支就可以剪掉。
• 分支策略：通常选择一个未分配的顶点，分别尝试将其放入 S 或放入 T，形成两个子分支。 我在处理一些顶点数在40左右的结构化图时，配合好的上界函数，分支定界法往往能在几分钟内找到最优解，比纯暴力快好几个数量级。

3. 整数规划方法：这是将最大割问题形式化为一个整数规划模型，然后用专业的求解器（如CPLEX, Gurobi）来求解。模型可以这样建立：

• 为每个顶点 i 定义一个二进制变量 x_i：x_i = 1 表示顶点 i 在集合 S 中，x_i = 0 表示在 T 中。
• 为每条边 (i, j) 定义一个二进制变量 y_{ij}：y_{ij} = 1 表示这条边是割边。
• 目标：最大化 Σ w_{ij} * y_{ij}。
• 约束：需要确保 y_{ij} 的逻辑与 x_i, x_j 一致。即，当且仅当 x_i 和 x_j 取值不同时，y_{ij} 可以为1。这可以用线性约束来表达：y_{ij} <= x_i + x_j，且 y_{ij} <= 2 - x_i - x_j。同时，y_{ij} 本身是0或1。 将模型输入求解器，它内部会使用割平面法、分支定界等一系列高级技术来求解。对于中等规模的问题（几百个顶点），整数规划求解器通常非常强大。实操心得：构建模型时，约束的写法会影响求解效率。对于最大割，还有一种更紧凑的二次整数规划模型，但需要求解器支持二次项。直接使用专业的数学规划求解器是解决中小规模精确问题最省心、最可靠的方法。

3.2 近似算法：理论保证的“安慰剂”

既然精确求解难，我们退而求其次，寻找能在多项式时间内给出解，并且这个解的值至少是最优值的某个固定比例的算法。这个比例称为近似比。

随机分配算法：最简单、最经典的算法。独立地、随机地将每个顶点以1/2的概率分到 S，1/2的概率分到 T。对于任意一条边，它成为割边的概率正好是1/2（因为它的两个端点被分到不同集合的概率）。因此，算法期望得到的割的权重是总边权重之和的一半。由于最优解的最大割值不可能超过总权重，所以这个随机算法的期望近似比是 0.5。 这虽然听起来很弱，但它是一个基线。而且它极其高效，时间复杂度是 O(n)。在实际中，我们可以运行这个随机算法多次，取最好的结果，往往能得到一个不错的起点。

Goemans-Williamson 算法（半正定规划松弛）：这是近似算法史上的一座里程碑。对于最大割问题（这里特指加权最大割，权重可为负，但通常我们考虑非负权重），Goemans和Williamson在1995年提出了一个基于半正定规划（SDP）松弛的算法，其近似比至少为 0.878...。这是目前已知的、对一般图最好的近似比（假设一个著名的猜想P≠NP成立）。 算法步骤简述：

1. 松弛：将每个顶点 i 映射到一个单位球面上的向量 v_i。原问题中顶点属于 {0, 1}，松弛后变成了向量。目标是最大化 Σ w_{ij} * (1 - v_i·v_j) / 2。因为当 v_i 和 v_j 方向相反时（点积为-1），该项贡献为1；方向相同时（点积为1），贡献为0。
2. 求解SDP：求解这个向量形式的优化问题（这是一个凸问题，可在多项式时间内求解到任意精度）。
3. 随机舍入：随机选取一个超平面（其法向量随机均匀选取），根据顶点向量 v_i 落在超平面的哪一侧，来决定将其分到 S 还是 T。 这个算法的理论和实践意义都非常大。实操中的坑：虽然理论保证很美，但实际实现SDP求解并不简单，需要专门的库（如CVXOPT, SDPA）。而且对于大规模图（上万顶点），SDP求解本身计算量和内存消耗会很大。因此，G-W算法更像一个理论标杆和中等规模问题的优质选择，对于超大规模图，我们可能还得依赖更轻量的启发式方法。

3.3 启发式与元启发式算法：实践中的主力军

当问题规模很大，或者需要快速得到一个优质解时，启发式算法是工程实践的首选。它们没有严格的近似比保证，但在许多实际实例上表现卓越。

1. 局部搜索（Local Search）：从一个初始解（比如随机分配）开始，反复尝试进行“局部改动”来改进解。对于最大割，最自然的局部操作是“移动一个顶点”：将一个顶点从当前集合移到另一个集合，如果这个操作能增加割的权重，就接受它。反复进行，直到没有单个顶点的移动能带来改进为止，此时达到一个“局部最优”解。

• 问题：容易陷入平庸的局部最优。
• 改进策略：
  • 多起点随机重启：从多个不同的随机初始解开始运行局部搜索，取最佳结果。
  • 模拟退火：以一定的概率接受使解变差的移动，初期概率高，后期概率逐渐降低，帮助跳出局部最优。
  • 阈值接受：接受比当前解差，但差得不太多（在一个阈值内）的移动。

2. 贪心算法及其变种：一种直观的贪心策略是：逐个考虑顶点，将其放入能使得当前割权重增加最多的那个集合，如果放入哪个集合都不增加（甚至减少），则暂时搁置或根据某种规则决定。 更高级的一种是Delta-Gain 贪心：

• 初始化所有顶点未分配。
• 维护每个顶点当前的“增益”：如果将其加入S或T，能给当前割带来的增量（考虑其已分配邻居的影响）。
• 每次选择增益最大的顶点进行分配，并更新其邻居的增益。
• 这个过程有点像Prim算法求最小生成树，但目标是最大化割。 这种贪心法通常能快速得到一个比随机解好得多的解，常作为其他更复杂算法（如局部搜索）的优质初始解。

3. 进化算法与遗传算法：将割的编码（每个顶点的0/1分配）看作一个“染色体”。

• 种群：维护一组解（个体）。
• 选择：根据适应度（割值）选择优秀的个体。
• 交叉：将两个父代解的部分进行混合，产生子代。例如，随机选择一个切割点，子代一部分来自父代1，另一部分来自父代2。
• 变异：以较小概率随机翻转某些顶点的分配。
• 迭代：不断进化，期望种群质量越来越高。 这类算法需要调参（种群大小、交叉率、变异率），但对于复杂、多峰的问题空间，有时能发现意想不到的好解。

4. 基于深度学习的启发式：这是近年来的研究热点。思路是用图神经网络（GNN）来学习图的特征，然后直接输出一个割的分配，或者输出一个策略（比如下一个该移动哪个顶点）。这需要大量的训练数据（不同结构的图及其优质解），训练好后，对新的同类图可以做到快速推理。目前这更多处于前沿探索阶段，离普适、稳定的工业应用还有距离，但潜力巨大。

4. 实战：针对特定图结构的策略与优化

理论算法是通用的，但实际问题中的图往往具有特殊结构。利用好这些结构，能极大提升求解效率和解的质量。

4.1 二分图与完全图：两种极端情况

• 二分图：如果图本身就是一个二分图，那么最大割是平凡的。因为二分图的定义就是顶点集可以划分为两个集合，使得所有边都在这两个集合之间。所以，直接采用这个二分划分，就能得到包含所有边的最优割。
• 完全图：n个顶点的完全图，任意两个顶点之间都有边。它的最大割值是多少？直觉上，我们应该尽可能平均地分配顶点。如果n是偶数，最优解是两边各 n/2 个顶点，割边数为 (n/2)(n/2) = n^2/4。如果n是奇数，最优解是两边分别 (n+1)/2 和 (n-1)/2 个顶点，割边数为 ((n+1)/2)((n-1)/2) = (n^2-1)/4。随机算法在这里的期望值是总边数的一半，即 n(n-1)/4，与最优解的比值当n很大时趋近于1，所以随机算法在完全图上表现反而很好。

4.2 稀疏图与大直径图

• 稀疏图（边数 m 远小于顶点数 n 的平方）：例如社交网络、道路网络。这类图通常存在社区结构。一种有效的策略是先使用图聚类算法（如Louvain算法、谱聚类）识别出紧密的社区，然后将不同的社区整体分配到不同阵营。这相当于在更高层次上进行决策，可以避免在社区内部进行无谓的顶点摇摆。实操心得：对于社区结构明显的稀疏图，先聚类再分配的策略，其解的质量和求解速度往往远超通用的启发式算法。
• 大直径图：图的直径大，说明信息传播慢。局部搜索在这类图上可能效率较低，因为一次移动一个顶点的影响范围有限。可以考虑使用“大规模邻域搜索”，即每次尝试交换一组顶点，或者使用基于路径的改进策略。

4.3 处理负权重边

标准的“最大割”通常假设边权重为非负。但如果允许负权重，问题就变成了“最大权割”。对于负权重边，我们希望它不要成为割边（因为会减少总权重）。这等价于我们希望它的两个端点在同一侧。这其实可以通过一个简单的变换，转化为一个等价的全非负权重最大割问题加上一个常数偏移。具体做法是：设原图G有权重w_{ij}（可正可负）。构造一个新图G‘，它与G有相同的顶点集，边权重 w‘{ij} = max(0, w{ij}) - min(0, w_{ij})。同时，计算一个常数 C = Σ min(0, w_{ij})。可以证明，原图G上任意割(S, T)的权重，等于新图G‘上同一个割的权重加上常数C。由于C是固定的，在新图G‘（其边权全为非负）上求最大割，就等价于在原图上求最大权割。这个技巧非常实用，能让我们将处理负权重的算法统一到非负权重框架下。

5. 性能评估与结果分析框架

当我们实现了一个或多个算法后，如何科学地评估它们？不能光看一个例子就说谁好谁坏。

5.1 测试数据集构建

需要不同规模、不同结构的图来测试算法的鲁棒性。

1. 随机图：Erdős–Rényi 模型 (G(n, p))，每个边以概率p独立存在。可以测试算法在无结构图上的表现。
2. 规则图：如网格图、环图、完全图。这些图有明确的最优解或理论值，便于验证算法正确性和评估近似比。
3. 具有社区结构的图：使用随机块模型生成，顶点属于不同的社区，社区内部连接概率高，社区之间连接概率低。测试算法能否发现这种宏观结构。
4. 真实世界图：从斯坦福网络数据集（SNAP）等公开库获取，如社交网络、合作网络、网页链接图。这是算法的终极考场。
5. 加权图：在以上图的基础上，为边赋予随机权重（均匀分布、正态分布等）。

5.2 评估指标

1. 解的质量：

   • 割值：算法找到的割的权重。绝对值。
   • 近似比：对于已知最优解的问题，计算算法结果 / 最优解。对于不知道最优解的大规模问题，可以用算法结果 / 理论上界来估算。例如，总边权重和就是一个简单的上界。
   • 与基准对比：与随机算法、简单贪心算法的结果进行对比，看提升幅度。

2. 运行时间：记录算法从开始到结束的CPU时间或墙上时钟时间。对于大规模问题，时间是关键考量。

3. 稳定性：对于随机性算法（如随机舍入、多起点局部搜索），运行多次，计算结果的均值和方差。方差小说明算法稳定。

4. 可扩展性：测试算法在不同规模图（从几百顶点到几万顶点）上的表现，观察运行时间和解的质量随规模增长的变化趋势。

5.3 结果可视化与解读

• 收敛曲线：对于迭代算法（如局部搜索、遗传算法），绘制“迭代次数 vs 当前最佳割值”的曲线，观察算法收敛速度。
• 解分布图：对于多次随机运行的结果，绘制直方图，了解解的质量分布。
• 顶点分配可视化：将最终得到的割 (S, T) 在图上用两种颜色标记顶点，直观地看划分是否合理（例如，在社区结构图中，同一社区的顶点是否被分到了同一边）。

一个完整的评估报告应该结合以上多个维度和多种图例，才能令人信服地说明某个算法的优劣和适用场景。

6. 常见陷阱、调试技巧与优化实录

在实际编码和调试最大割算法时，我踩过不少坑，也总结了一些技巧。

6.1 数据结构的选择

图算法的效率很大程度上取决于数据结构。

• 邻接表 vs 邻接矩阵：对于稀疏图，绝对要用邻接表（或压缩稀疏行格式CSR），存储空间 O(m+n)，遍历邻居也快。邻接矩阵 O(n^2) 的空间在 n 较大时是灾难。
• 增益的维护：在局部搜索或贪心算法中，需要频繁计算移动一个顶点带来的割值变化（Delta Gain）。如果每次都去遍历该顶点的所有邻居重新计算，效率太低。应该维护一个数组gain[v]，动态更新。当移动一个顶点 u 时，对于 u 的每个邻居 v：
  • 如果 v 和 u 原来在不同集合，移动 u 后它们就在同一集合了，所以边 (u, v) 从割边变成非割边，gain[v]需要减去这条边的权重（因为v未来可能移动，这条边不再可能因v的移动而成为割边）。
  • 如果 v 和 u 原来在同一集合，移动 u 后它们就在不同集合了，所以边 (u, v) 从非割边变成割边，gain[v]需要加上这条边的权重。
  • 同时，gain[u]本身需要取反（因为移动后，u的所有邻边状态翻转）。 这样，每次移动的增益更新成本是 O(degree(u))，而不是 O(n)。

6.2 局部搜索的停滞与跳出

局部搜索最头疼的就是陷入局部最优。除了模拟退火，还有一些技巧：

• 禁忌表：记录最近几次移动的顶点，禁止在短期内再次移动它们，强制算法去探索其他区域。
• 扰动：当搜索停滞时，不是完全重启，而是对当前解进行一个较强的扰动（比如随机移动一批顶点），然后从这个扰动后的解继续局部搜索。这被称为“迭代局部搜索”。
• 多层级策略：对于大规模图，可以先对图进行粗化（将紧密连接的顶点合并成超顶点），在粗化图上进行搜索得到一个划分，再将这个划分映射回原图并进行精细化局部搜索。这能帮助算法跳出细粒度的局部最优。

6.3 整数规划求解器的调参

使用CPLEX/Gurobi求解整数规划模型时，默认参数可能不是最优的。

• 强调可行性 vs 最优性：如果只想要一个可行解，可以调高启发式算法的强度。如果更关注证明最优性，可以调强割平面生成。
• 设定时间/内存限制：对于大规模问题，提前设定运行时间限制或内存上限，避免程序无限制运行。
• 利用初始解：如果你通过启发式算法得到了一个优质解，可以将其作为“MIP起始解”提供给求解器，这能大大加快求解进程，尤其是帮助提升下界（对最大化问题是上界）。
• 关注日志：求解器会输出详细的日志，包括当前上下界、间隙、找到的整数解等。通过日志可以判断求解进程是否健康，是否卡住。

6.4 算法组合的威力

在实际项目中，我很少只依赖单一算法。一个常见的有效模式是：

1. 快速生成初始解：使用随机算法或多起点贪心算法，快速产生一批候选解。
2. 局部强化：对每个优质初始解，进行局部搜索（如使用模拟退火或禁忌搜索）进行深化。
3. 种群进化：将局部搜索得到的一批优质解作为初始种群，运行遗传算法进行交叉和变异，探索更广的空间。
4. 最终抛光：对进化算法得到的最佳解，再进行一轮细致的、允许接受轻微变差的局部搜索（如阈值接受），进行微调。

这种“组合拳”往往比任何单一算法都能得到更稳定、更优质的结果。关键在于不同阶段算法间的衔接和数据（解）的传递。

7. 从理论到应用：最大割的现实映射

理解了算法，我们再来看看最大割问题究竟能用在哪些地方。这能帮助我们更好地建模，也能在面试或项目讨论中，清晰地阐述工作的价值。

7.1 集成电路设计与布局布线

这是最大割最早、最经典的应用领域之一。在芯片设计时，需要将数百万个逻辑门（顶点）放置到芯片的不同区域，并用导线（边）连接。我们希望将整个电路划分到两个芯片上，或者划分到芯片的两个区域上，同时满足两个目标：

1. 两个部分之间的连接（即割边）数量尽可能少？等等，不对，这里应该是尽可能多吗？不，在布线中，跨区域的连线通常更“昂贵”（延迟大、占用通道），所以我们希望它少。这听起来像是最小割问题。
2. 但最大割的应用场景在于测试。为了测试芯片，我们有时需要最大化两个部分之间的信号交互，以确保所有跨区域的通路都能被充分测试。或者，在某种编码和通信方案中，最大化两个模块间的差异可能有利于错误检测。

更常见的相关问题是最小割或平衡割（在割边尽量少的同时，两个部分大小尽量均衡）。最大割和最小割在计算复杂性上是等价的（求一个图的最大割等价于求其补图的最小割？这里需要小心，对于一般图，最大割和最小割并不直接对偶）。但在实际中，划分问题的约束和目标多种多样，最大割模型是其核心组成部分之一。

7.2 社交网络分析与社区发现

在社交网络中，我们可能想找出观点最对立、互动模式最迥异的两个群体。例如，在一个政治讨论论坛中，用户（顶点）之间的连接可以是回复、引用或赞同关系。如果我们能找到一个割，使得跨割的互动（边）最多，那么这两个群体很可能代表了两种核心的、对立的立场。这可以用于：

• 极化研究：量化社群的极化程度。一个高度极化的网络，其最大割值会接近总边数的一半（如果完全随机，期望值就是一半）。如果实际能找到的割值远高于一半，说明存在明显的对立结构。
• 对抗社区检测：不同于寻找内部连接紧密的社区，这是寻找那些之间连接异常密集的“对抗社区”。这在安全领域（如识别网络中的敌对阵营）可能有应用。

7.3 统计学与机器学习中的聚类

在一些聚类任务中，特别是二聚类，最大割提供了一种视角。我们希望将数据点分成两类，使得两类之间的“差异”或“不相似性”最大。如果把数据点看作顶点，点之间的不相似度作为边的权重（注意，这里权重越大表示越不相似），那么最大化割的权重，就等于最大化两类之间的总不相似度。这有时被称为“最大割聚类”。不过，更常见的聚类目标是最大化类内相似度（即最小化类内距离），这与最大割的目标看似相反，但通过巧妙的图构建（例如，用相似度负值作为权重），它们可以相互转化。

7.4 组合拍卖与资源分配

想象一个场景：有一组物品要分配给两个买家。买家对不同的物品组合有不同的估值。边可以表示某种关联，比如两件物品是互补品（一起买价值更高）或替代品。最大割模型可以用来建模如何划分物品，使得两个买家获得的“交叉价值”或某种特定形式的效用总和最大。这是一个高度简化的模型，真实拍卖要复杂得多，但最大割作为组合优化问题的基本模型，为其提供了理论基础。

理解这些应用场景，最大的帮助是在面对一个新问题时，能够判断它是否“长得像”一个最大割问题，从而可以尝试套用现有的算法工具箱。这种建模能力，往往比单纯会写算法代码更重要。

折腾最大割问题这些年，我的一个深刻体会是：NP难问题就像一座高山，精确求解的顶峰难以抵达，但这并不意味着我们只能在山脚下徘徊。近似算法、启发式算法以及针对问题特性的优化，就像不同的登山路径和装备，能带领我们到达不同的高度，看到不同的风景。最重要的是，清楚你的目标是什么——是要一个理论上可证明的“还不错”的解，还是要一个实际中“非常好”的解，抑或是必须得到那个绝对最优解？不同的目标，决定了你该选择哪条路径，以及该在哪个环节投入最多的精力。对于最大割，从简单的随机算法到复杂的元启发式组合，工具箱很丰富，关键是根据问题的规模、结构和实时性要求，做出合适的选择和搭配。