点开Coursera上这门Discrete Optimization之前，我被“离散优化”这四个字劝退了整整两个学期。总觉得那是数学系该碰的东西，我一个写业务代码的，何必自找苦吃。直到身边一个做排班系统的朋友说，他工作里最值钱的部分不是写接口，而是怎么把排班规则变成一个可求解的模型，我才下决心跟着课程完整走一遍。第一周introduction学完，我的感受是：这门课确实有门槛，但门槛不在数学基础，而在思维方式的转变。
这篇帖子是系列学习笔记的第一篇，我会把课程内容、我的理解、踩过的坑和作业复盘都写清楚。适合正在犹豫要不要选这门课的人，也适合和我一样刚开始第一周、想找点学习搭子的人。后面每周我尽量保持更新，形成一个完整的跟课记录。
1. 每周的introduction藏着整门课的问题地图
1.1 第一周没有讲太多公式，但给了你一张“问题清单”
第一周的视频里，授课老师Pascal Van Hentenryck没有一上来就扔定义，而是从一堆现实场景切入：从一个城市到另一个城市怎么走路线最短，地图上的相邻区域怎么着色才能保证颜色不冲突，教室和课程怎么排才能满足各种约束，还有旅行推销员、背包携带、蛋白质折叠……这些问题看起来八竿子打不着，但它们背后有一个共同的骨架：决策变量、约束条件、目标函数。
如果你之前没有接触过优化领域，这组概念值得先停下来想清楚。所谓决策变量，就是我们能控制的选择，比如这个物品装不装、这条路走不走；约束条件定义了什么是“合法的方案”，比如背包重量不能超过上限、同一间教室不能同时安排两门课；目标函数则告诉机器我们到底想要什么，是路程最短、价值最大还是时间最省。课程第一周反反复复讲的，就是这三个东西在不同问题里的具体样子。
我记得视频里有一张清单，列举了离散优化在现实中的典型场景。不少例子让我很有共鸣：快递公司每天要规划几百辆车的配送路线，医院要排几千个护士的班次，芯片设计要在有限面积里布置几百万个元件。这些场景以前我只知道“很复杂”，但从没想过它们的底层解法居然有共性。第一周结束的时候，我已经能从任何一个描述性问题上快速提炼出“变量是什么、约束有哪些、目标是什么”，这个能力在后面所有作业里都派上了用场。
1.2 约束满足问题与优化问题：先分清“行不行”和“好不好”
第一周还介绍了一个关键区分：有些问题只要找到一个可行解就行，比如给地图着色，只要相邻国家颜色不同就完成任务，这叫约束满足问题；另一些问题不仅要可行，还要在可行范围里挑最优解，比如背包问题要在所有装得下的组合里挑总价值最高的，这叫优化问题。
这个区分我一开始觉得简单，后来才发现很多建模错误都源于混淆二者。如果你只写“找到任意解”的约束，求解器会随便给你一个可行结果；可你心里想的是最优结果。所以第一周就要养成习惯：先问自己，这个问题到底要求“一个答案”还是“最好的答案”。我在第一次练习时就因为漏了maximize关键字，求解器秒出一个可行解，我还以为程序写错了，白白查了半天。
另一个值得注意的点是，约束满足问题往往也不简单。比如给地图着色，四个颜色够不够？这背后是著名的四色定理，但放到更大规模的图上，颜色数量一旦受限，找可行解本身就可能非常困难。课程提到，很多现实问题本质上是“先满足约束，再谈优化”，两步不能混成一团。理解这个顺序，对后面学习约束编程和局部搜索很有帮助。
1.3 第一周的“Try it”小练习比看视频更让你打脸
课程配套的交互式小练习，第一眼看上去像游戏，实际上才是真正让人“悟”的地方。我在尝试手工规划从起点到终点的路线时，几秒钟还搞得定，等地图规模一大，我发现自己连“接近最优”都做不到，更别提验证是不是最优。另一个练习是手动完成一个区域的着色任务，我明明觉得已经用了最少的颜色，结果系统提示还能更少，那种感觉就像是自己的直觉被当场拆穿。
做这类练习我有个心得：不要只把它当小游戏玩，试着在纸上写下自己的思考过程，再去和视频里讲的方法对照。你会发现，你在小规模问题里凭直觉用的那些规则，恰恰是后面各种算法的雏形。比如我在路径练习里下意识“每次选离目标最近的点”，其实就是贪心策略；在着色练习里“先给最难搞的区域选颜色”，其实就是动态价值排序的思想。第一周视频看似浅显，但如果你愿意多想一层，它其实给了你一张整门课的问题地图。
2. 组合爆炸不是吓唬你：为什么暴力枚举在离散优化里走不通
2.1 20个城市的旅行周游就有约2.43E18条路线
第一周另一个刷新我认知的点是组合爆炸。Pascal讲了一个例子让我印象很深：旅行推销员要去20个城市，暴力枚举所有可能路线的数量是20的阶乘，也就是大约2.43乘以10的18次方。我对这个数字没什么直觉，换算了一下才意识到：就算程序每秒能检查一百万条路线，也得跑上约7.7万年。
这个例子让我彻底理解了为什么离散优化是一门独立的学科。问题本身不一定复杂，但简单的问题稍微放大规模，就会超过人类和计算机的直观处理能力。20个城市听起来真不多，我的外卖路线都可能经过20个取送点，但想靠“遍历所有方案”找到最短路线，完全不现实。这也是课程反复强调的：离散优化的核心任务，是在指数级别的可能性空间里，不靠枚举就找到最优或近似最优的答案。
2.2 背包问题里藏着“指数级”这个老朋友
另一个典型例子是背包问题。假设有50件物品，每件都有选和不选两种状态，可能的组合数量就是2的50次方，约1.125E15种。同样的计算方式，每秒检查一百万次也需要约35年。组合爆炸的可怕之处就在这里：问题规模线性增长，候选方案数量却指数增长。电脑再快也追不上这种增长。
这个道理现在听起来简单，但它改变了我对“算法优化”的认识。以前我写代码，所谓的优化只是把双重循环改成哈希查找，在小数据集上很有效。但在离散优化面前，这种优化是远远不够的，因为你面对的根本不是“快一点还是慢一点”的问题，而是“能不能算出来”的问题。因此这门课后续讲的搜索、剪枝、松弛、局部搜索等方法，本质上都是在和指数增长赛跑，各有各的切入口和取舍。
2.3 人类直觉在组合问题里有多不可靠
第一周还有一段内容让我印象深刻：在组合规模达到几十个变量时，人类手动找最优解的能力其实相当差。我做练习时已经体会到了，后来看了一个研究结论，说人在面对没有即时反馈的复杂决策时，倾向于选“看起来不错”而不是“真的最优”。当你面对几百条路线的配送问题时，所谓经验丰富的老师傅方案，往往也只是某个贪心策略的结果，距离真正的数学最优还有很大差距。
这种认识让我对“凭经验办事”有了新的看法。现实业务里，我们大多靠规则和直觉来安排任务，因为问题规模小的时候，直观方案和最优方案差距不大。一旦规模上来，直觉的退化会非常明显。离散优化这门课提供的就是一套系统方法，把这种“凭感觉”变成“可证明”的决策过程。
3. MiniZinc上手要点：模型、数据与第一个能跑的背包问题
3.1 为什么第一周就要引入建模语言
第一周另一个重点是MiniZinc。很多人不适应：我们明明会写Python，为什么要学一种看起来像“新语言”的建模工具？我的理解是，优化问题最耗时的不是“求解”本身，而是“建模”。MiniZinc用声明式写法把决策变量、约束和目标函数直接描述出来，剩下的搜索工作交给后端的求解器（Gecode、Chuffed等）。同一个模型可以换不同的求解器，而不需要重写整套算法。
打个比方，如果你让程序员手写排序，他可能写出冒泡排序；但真实业务里没有人手写排序，大家都用库函数。MiniZinc就是优化领域的“高级库”，你只管描述问题是什么，不用管内部怎么搜索。当然，这只是第一周的初体验，后面课程会深入讲解不同求解器的原理，但第一周能做到“描述即求解”，已经足够震撼了。
3.2 模型与数据分离：.mzn和.dzn分开写的好处
MiniZinc第一个要理解的设计是模型与数据分离。模型文件（.mzn）放结构，数据文件（.dzn）放具体数值。比如背包问题，模型描述“有一组物品、每个物品有重量和价值、要选一组物品使得在总重量限制内总价值最大”；数据文件则告诉你这次具体是5件物品、容量是10、重量和价值表是什么。
这样做的好处非常实际：换一批数据不碰模型，批量跑实验也很好用。我后来把官方给的示例数据单独存一个文件，自己另写一个测试文件，改动只影响数据，不会碰乱模型结构。如果你做作业时发现“换一个数据就报错”，大概率是模型里把数据的范围写死了，而不是数据本身有问题。
3.3 一个完整可跑的背包模型
我贴一个第一周作业同款的背包模型，注释已经写清楚。建议亲手敲一遍，敲完再换成不同的数据多跑几次，比复制粘贴效果好得多。
% 模型文件：knapsack.mzn int: n; % 物品数量 int: capacity; % 背包容量 array[1..n] of int: weight; % 每件物品重量 array[1..n] of int: value; % 每件物品价值 % 决策变量：take[i] 为 1 表示选第 i 件物品，0 表示不选 var array[1..n] of 0..1: take; % 约束：选中物品的总重量不能超过背包容量 constraint sum(i in 1..n)(weight[i] * take[i]) <= capacity; % 目标：最大化选中物品的总价值 solve maximize sum(i in 1..n)(value[i] * take[i]); % 输出结果，方便检查 output ["take = ", show(take), "\n"];% 数据文件：knapsack.dzn n = 5; capacity = 10; weight = [4, 3, 5, 2, 6]; value = [9, 6, 12, 4, 8];使用MiniZinc IDE打开模型文件，再选择对应的数据文件，点运行即可。运行后输出一个0/1数组，比如take = [1, 1, 0, 1, 0]，可以手动验证重量：4 + 3 + 2 = 9，没有超过容量10。总价值是9 + 6 + 4 = 19。
这里我第一次犯了个低级错误：数据文件后缀写成.txt，IDE怎么都找不到数据，卡了十多分钟。另外提醒一点，var array[1..n] of 0..1里的0..1并不是布尔值简写，它声明的是一个整数域为0到1的变量数组，在优化中常被用来表示“取/不取”。虽然可以用bool变量，但后续做加权和、乘容量时会涉及类型转换，直接用0..1整数更省事。
4. 第一次作业复盘：从读题到提交我踩过的坑
4.1 作业在一开始会给你一个“过于友好”的错觉
第一周的编程作业，我印象里是整个课程里相对友好的：场景比较小，约束也少，基本就是照着课堂示例改一改就能通过。但正因为简单，很多人容易掉以轻心，反而在环境配置和提交环节浪费很多时间。
作业要求通常会写得很细，包括下载MiniZinc IDE、打开模板、修改后提交。官方教学视频里演示的是老版本IDE，和最新版界面有差异，我第一次照着视频找“Run”按钮找了半天，后来才发现新版里运行按钮已经变了位置。这种问题不高深，却特别容易劝退新手。顺便说一下，如果你的机器装了多个版本的MiniZinc，留意环境变量指向哪个版本，否则命令行调用和IDE里运行的求解器可能不一致，结果会莫名其妙地对不上。
4.2 我第一个过不去的坎：模型正确，提交却扣分
我提交第一次作业后，系统显示没有完全通过。第一反应是建模错了，把所有约束翻了一遍，最后才发现问题出在数据类型的边界：我把某个参数写成了固定的小范围类型，测试用例里的值一变大，模型就出界。这暴露的是对变量域理解不够，而不是逻辑错误。
解决方法是把参数声明成合理的整数域，或者干脆让数据文件来约束实际范围，模型里保持相对宽泛的声明。经过这一次，我意识到：第一周作业看似简单，但它真正考察的是你是否理解“模型应当对所有数据有效”，而不只是让当前这个数据跑通。
4.3 Coursera评测的玩法：本地跑通只是第一步
Coursera的作业评测和传统在线评测不太一样，它通常会用隐藏数据跑你的模型，判断模型的正确性和最优性。这意味着几件事：
- 模型必须在多种数据规模上都能在时限内出结果；
- 如果你写的是约束满足而不是优化，只有一个可行解，可能被判为不合格；
- 如果漏了
maximize或minimize，求解器只给你可行解，最优性判定就会扣分； - 模型如果对数据范围做了过多假设，遇到隐藏数据就可能报错或超时。
所以每次提交前，我要求自己至少往数据文件里塞三组自制测试用例：一组极端大、一组极端小、一组重复数据，确保模型不是“只对示例有效”。这种习惯后来一直保留到课程结束，收益很大。它也在逼我从“给题写答案”转变为“写一个能被复用的求解模型”，这本来就是这门课的重要目标之一。
5. 别被第一周的“简单”骗了：学习节奏与资源配置
5.1 第一周投入多少时间合适
如果全职上班或上学，我建议第一周至少留出6到8个小时。视频看起来只有几十分钟，但中间穿插的练习、作业和安装环境非常占时间。我自己的分配大概是：视频浏览1.5小时，Try it练习1小时，MiniZinc环境搭建和基础语法2小时，作业加调试2小时，最后写笔记复盘1小时。时间紧的话可以不写笔记，但作业一定要独立完成，不要边看答案边写。
这里我想特别强调一个容易被忽略的点：第一周的“简单”是相对后面的章节而言的，它给你建立的是操作层面的熟悉感。如果你在这一周没有亲手跑通几个模型，后面讲约束编程和局部搜索时，你会一边学算法一边补MiniZinc语法，两头都顾不上。
5.2 课程论坛和往期笔记值得怎么用
Coursera官方讨论区信息很杂，但每周围绕作业的答疑帖非常值得快速浏览，很多人卡住的地方往往高度一致，比如“为什么找不到数据文件”“为什么模型超时”。看别人踩坑比自己踩坑效率高得多。
另外，这门课是老课，网上有大量往期学习者的笔记和代码仓库。我的建议是：看可以，但一定要在本地亲手跑一遍，然后按自己的理解重新写一版。照抄模型一小时就忘，亲手建一遍才真正理解约束怎么写。如果你能找到那种带中文注释的笔记，初期阅读门槛会低不少，但不要依赖，因为课程版本可能更新，示例可能跑不通。
5.3 如果离校很久，要不要先补数学基础
说实话，第一周不要求线性规划基础，但后续章节会用到不少数学概念。如果离校太久，可以在这一周先把“线性规划”“整数规划”这两个词对应的中文资料扫一遍，不用深究，知道变量、约束、目标函数三个概念就够了。第一周作业真正需要的数学只有求和、比较和一点集合思维。
我个人的方法是每天用二十分钟把当天看的英文术语整理成一张中英对照表，比如feasible solution（可行解）、objective function（目标函数）、constraint（约束）、integer programming（整数规划）。整理术语表看似笨，但对后续看英文课程非常有效。尤其是当你开始看论文和补充材料的时候，这批基础词汇能省去大量查词典的时间。
6. 第一周学完，我对“优化”这件事的三个认知转变
6.1 从“手写算法”到“描述问题”：建模思维比求解技巧更重要
学第一周之前，我遇到优化类问题，第一反应是“用什么算法”：贪心还是动态规划？遗传算法还是模拟退火？学完这一周以后，我意识到更合理的起点是“怎么描述问题”。一旦用变量、约束、目标函数把问题说清楚，求解器会替你想算法。这并不是说算法不重要，而是说算法选择应该是第二步，第一步永远是建模。
这个转变有点像从“自己种菜做饭”到“学会点菜”——你依然可以研究菜是怎么做的，但日常生产力已经完全不同了。现在我看到一个需求，会先问对方：哪些条件是硬性的？哪些是希望尽量好的？这两个问题的答案，基本就是约束和目标函数。
6.2 原来很多“只能靠人工排班”的事情，机器能直接求优
另一个让我意外的收获是，很多我以为“只能靠人工安排”的事情，离散优化都能给出质量和速度都远超手算的方案。课程举的例子包括公司排班、物流路径、门店选址、芯片布线，甚至蛋白质折叠。第一周只是点到为止，但这些应用场景让我知道：这门课学到的能力不是纸上谈兵，而是有真实商业价值的。
我的一个观察是，很多公司招聘算法工程师时，职位描述里写的“熟悉运筹优化”其实就是这类能力。学了离散优化这门课，哪怕只跟到中段不深入，写简历时描述“能利用优化模型解决排班/路径问题”也更有底气。虽然我现在还不是算法岗，但这种额外的视角对我的系统设计能力很有帮助。
6.3 学习计划比课程本身更值得认真对待
这门课的内容密度会逐渐上升，第一周的introduction只是起点。我的决定是每周固定时间学习，绝不攒堆。同时给自己定了一条规矩：每个星期先不看新视频，先把上周的模型重新默写一遍。如果写不出来，就说明上周没学透，宁愿多看两周再往下走。
我给同样准备开坑的人一个建议：不要追求“快速刷完”。这门课的价值在于培养建模直觉，这个东西只能靠时间和练习沉淀，走不了捷径。如果第一周你觉得有点吃力，不用慌，那是正常的；坚持到第四个星期，你会发现自己看问题的眼光已经变了。
第一周的内容就记到这里。这周最大的收获不是背下了几个定义，而是亲自动手把一个“选择物品装包”的问题变成了一个机器能自动求解的模型。这个过程很神奇，也很有成就感。后面我会继续更新约束编程、局部搜索、混合整数规划这些模块的学习笔记，如果你也在学这门课，或者打算入坑，欢迎在评论区交流你的作业进度和踩坑经历。下一周见。
