第1章组合优化概述

一、组合优化概述：什么是组合优化、核心问题类型、课程目标与学习路径

大家好，欢迎来到《组合优化：从理论到实战》的第一章。

说实话，每次我给新团队讲组合优化，总有人问：「这玩意儿是不是就是算法竞赛里的那些题？」
嗯，有点像，但又不完全是。我个人的理解是——组合优化，就是在有限的选择里，找到那个最好的方案。

你想想看，生活中到处都是这类问题：
快递员怎么走最省油？工厂怎么排产最快？背包里装哪些东西最值钱？
这些问题背后，都有一个共同的数学骨架——组合优化。

组合优化，说白了就是：
给定一个有限的候选集合，从中选出一个子集，使得某个目标函数最优。
听起来很学术？我换个说法——从一堆可能性里，挑出最好的那个。

我在项目中遇到过最典型的例子：
某物流公司要规划100辆车的配送路线。每辆车有几十个站点要跑。
所有可能的路线数量，比宇宙中的原子还多。
暴力枚举？别想了。这就是组合优化的用武之地。

  核心三要素：
  决策变量：你要选什么？（选哪些城市、装哪些物品）
约束条件：不能违反什么？（时间、容量、预算）
目标函数：你要优化什么？（距离最短、利润最大）

为什么叫「组合」？因为你的选择是离散的、有限的。
为什么叫「优化」？因为你要找的是最优解，不是随便一个可行解。

一个小技巧：
我刚开始学的时候，总把组合优化和连续优化搞混。
记住一句话：连续优化是「调参数」，组合优化是「做选择」。
前者像调音量旋钮，后者像选菜单上的菜。

组合优化的问题类型很多，但有三类问题，你无论如何都绕不开。
我建议你先把它们吃透，后面学什么都轻松。

这是组合优化里最出名的问题，没有之一。
问题描述很简单：一个销售员要跑N个城市，每个城市只去一次，最后回到起点，怎么走最短？

听起来简单？N=20个城市时，所有可能的路线数量是 20! ≈ 2.4×10¹⁸。
用最快的计算机枚举，也得算几百年。

我记得有一次帮客户做物流路径规划，对方说「就20个点，你写个循环不就行了？」
我当时差点笑出声。嗯，后来我用启发式算法，几秒钟给出了接近最优的方案。
客户很满意，但我知道——如果他用暴力枚举，等到退休都算不完。

避坑指南：
我曾经犯过一个低级错误：把TSP的对称性忽略了。
城市A到B的距离，和B到A的距离，在很多场景下是不一样的（比如单行道）。
写代码前，一定先确认你的距离矩阵是对称的还是非对称的。

这个问题的场景更接地气：
你有一个背包，容量有限。面前有一堆物品，每个有重量和价值。
怎么装，才能让总价值最大？

背包问题有很多变种，最常用的是这几种：

我在项目中遇到过最坑的事：
某次做资源分配，我用了0-1背包模型，结果发现物品之间还有依赖关系——选了A就必须选B。
嗯，这时候标准背包就不够用了，得用依赖背包或者整数规划。

调度问题，说白了就是「谁先干、谁后干、怎么干最省时间」。
工厂里机器怎么排产？云计算里任务怎么分配？手术室怎么安排？
这些都是调度问题。

调度问题的难点在于：
约束条件特别多。机器有闲置时间、任务有截止时间、工人有排班限制……
我见过最复杂的调度模型，光约束条件就写了200多行。

  调度问题的常见目标：
  最小化总完工时间（Makespan）
最小化总延迟时间
最大化资源利用率
最小化总成本

你想想看，一个工厂里几十台机器、几百个订单，排产方案的数量级比TSP还恐怖。
所以调度问题通常用启发式算法或元启发式算法来解。

这门课的目标很明确：
让你从「知道组合优化」变成「能用组合优化解决实际问题」。

我见过太多人，理论背得滚瓜烂熟，一遇到真实数据就懵了。
为什么？因为真实问题从来不会规规矩矩地写成标准形式。
你需要学会：建模 → 选算法 → 调参 → 落地 这一整套流程。

下面这张图，是我个人总结的学习路径：

具体来说，我们的课程会这样安排：

我的建议：
不要跳着学。我见过太多人直接跳到遗传算法，结果连TSP的数学模型都写不对。
基础打牢了，后面的东西学起来会快很多。
另外，每章后面的练习题一定要做。光看不练，等于白学。

这一章我们聊了：

下一章，我们会深入TSP问题，从数学模型开始，一步步带你写出第一个求解器。
嗯，到时候我会分享一些我踩过的坑，保证让你少走弯路。

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