数学基础回顾：集合论、图论基础、复杂度理论、凸集与凸函数

说实话，很多搞算法的人一上来就撸代码，结果遇到复杂问题就卡壳。为什么？因为数学底子没打牢。我当年刚入行时也犯过这毛病——写了个看似完美的贪心算法，结果跑出来的解连及格线都够不着。后来才发现，问题出在我对问题本身的数学结构理解不够。

这一节，咱们把组合优化需要的数学基础捋一遍。别怕，我不会给你整一堆枯燥的定理证明。咱们要的是「够用就行」，而且我会告诉你每个知识点在实际项目中到底怎么用。

集合论：一切的基础

组合优化，说白了就是在有限集合上找最优解。所以集合论是绕不开的。

我习惯把集合理解成一个「装东西的袋子」。袋子里的东西可以是数字、城市、任务，甚至其他袋子。组合优化里最常见的操作就是：

• 并集：把两个袋子合并，比如「所有可选的城市」
• 交集：找两个袋子里都有的东西，比如「既满足时间约束又满足成本约束的方案」
• 子集：从大袋子里挑出一部分，比如「从10个任务中选3个执行」

嗯，这里要注意一个坑：幂集。一个集合的所有子集构成的集合，大小是 2^n。我在做物流路径优化时，一开始想枚举所有可能的配送组合，结果 n=30 时直接炸了内存。2^30 是什么概念？十亿级别的组合数，暴力枚举根本不可能。

图论基础：建模的利器

图论这东西，我越用越觉得它香。很多现实问题，画成图就一目了然了。

一个图 G = (V, E)，V 是顶点，E 是边。就这么简单。但你能用它建模的东西可太多了：

• 最短路径：地图导航、网络路由
• 最小生成树：铺设电缆、设计通信网络
• 最大流：交通流量、供应链优化
• 匹配问题：人员分配、任务调度

我曾经帮一家快递公司做配送路线优化。一开始他们给的数据是一堆地址和距离，乱糟糟的。我花了一天时间把这些数据转成图——每个地址是一个顶点，道路是边，距离是权重。然后跑了个 TSP（旅行商问题）的近似算法，效果立竿见影。

图论里还有几个概念你得记住：

• 有向图 vs 无向图：单向路还是双向路？
• 加权图：每条边带个数值，比如距离、成本、时间
• 连通性：能不能从 A 走到 B？
• 环：走一圈回到起点，这在 TSP 里特别重要

复杂度理论：别做无用功

这个部分，我建议你认真听。因为搞不清复杂度，你可能会在一个 NP-Hard 问题上浪费几个月时间。

先说说 P 和 NP 的区别。你想想看：

• P 问题：能在多项式时间内找到解。比如排序、最短路径。这类问题，放心大胆去解。
• NP 问题：能在多项式时间内验证一个解对不对。比如数独，给你一个填好的盘面，你很快就能检查对不对。但让你自己填出来，可能得花很久。
• NP-Complete：NP 里最难的那一批。只要有一个能快速解，所有 NP 问题都能快速解。
• NP-Hard：至少和 NP-Complete 一样难，但不一定在 NP 里。

所以我的建议是：遇到问题先判断复杂度。如果是 P 问题，直接上精确算法。如果是 NP-Hard，别死磕精确解，考虑近似算法或启发式算法。

凸集与凸函数：优化的甜蜜区

凸优化为什么这么重要？因为凸问题有「全局最优解」这个好性质。你想想看，非凸问题就像连绵起伏的山脉，你爬到一个山顶，以为到顶了，结果发现旁边还有更高的山。凸问题呢？就像一个碗，你只要往下走，最终一定能走到碗底。

凸集的定义很简单：集合里任意两点的连线，整条线都在集合内。正方形是凸的，五角星不是。

凸函数：函数图像上任意两点的连线，都在函数图像的上方。说白了就是「碗形」的函数。

我在做资源分配优化时，发现目标函数是凸的，约束条件也是凸的。当时心里就踏实了——直接用梯度下降法，保证能找到全局最优。但如果目标函数是非凸的，就得考虑模拟退火、遗传算法这些全局优化方法了。

知识体系总览

下面这张图，把这一节的核心内容串起来了。你可以把它当作一个「思维导图」，以后遇到组合优化问题时，先看看自己卡在哪一层。

这一节的内容，说白了就是给你一套「工具箱」。遇到实际问题时，先用集合论建模，再用图论可视化，然后判断复杂度，最后用凸优化理论指导算法选择。这套流程我用了十年，屡试不爽。

---

公众号:蓝海资料掘金营，微信deep3321