点开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。这里我第一次犯了个低级错误数据文件后缀写成.txtIDE怎么都找不到数据卡了十多分钟。另外提醒一点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只是起点。我的决定是每周固定时间学习绝不攒堆。同时给自己定了一条规矩每个星期先不看新视频先把上周的模型重新默写一遍。如果写不出来就说明上周没学透宁愿多看两周再往下走。我给同样准备开坑的人一个建议不要追求“快速刷完”。这门课的价值在于培养建模直觉这个东西只能靠时间和练习沉淀走不了捷径。如果第一周你觉得有点吃力不用慌那是正常的坚持到第四个星期你会发现自己看问题的眼光已经变了。第一周的内容就记到这里。这周最大的收获不是背下了几个定义而是亲自动手把一个“选择物品装包”的问题变成了一个机器能自动求解的模型。这个过程很神奇也很有成就感。后面我会继续更新约束编程、局部搜索、混合整数规划这些模块的学习笔记如果你也在学这门课或者打算入坑欢迎在评论区交流你的作业进度和踩坑经历。下一周见。