序

这节讲优化问题，怎样找到最优解。

大概分成三种问题：爬山问题、线性规划问题，以及约束问题。

爬山问题

爬山问题比较经典，解决的问题是：如何在一群状态中找到最值。

什么叫状态呢？状态就是一种方案。比如说，在哪里建医院可以让附近的居民区到达各自最近医院的路径开销最小；再比如，外卖平台怎样安排送餐顺序才能让所用路径最短等等。

有的时候，追求最大值，这种函数叫 Optimal Function，有时候追求最小值，这种函数叫 Cost Function。总而言之就是寻找最值。

解决这种问题最经典的思路是（以找最大值为例），从一个点开始，环顾四周（邻居），有更高的，则向上前进，否则就到了一个极值点。

注意我说的，这里到了一个极值点，而不是最值点。找到的只是一个相对优的解，但并不是最好的，总结来讲，有如下的问题：

  1. 找到的是极值点，是局部最值，而不是全局；
  2. 遇到大片相等的值时，会卡住，无路可走（因为是严格大于）；
  3. 贪心，有时候走些弯路会爬的更高。

修改后的爬山算法

要对算法进行优化，有许多思路。有一些地方可以做文章：

  • Steepest-ascent 选爬升最多的邻居（其实就是刚刚的思路）；
  • Stochastic 随机选一个邻居；
  • First-choice 选第一个升高的；
  • Random-restart 从不同的地方开始；
  • Local Beam Search 维护许多更高的邻居。

整体看下来，我比较喜欢的是 Random-restart 算法，它可以打破局部最值的界限，放眼全局。

不过这些算法还是只解决了上文提到的第一个问题，后面的问题没有解决，因为本质上还是在选取更大的值，不愿意走弯路。

说到这，我又想起来之前班主任对我们说过的：

你们在学算法，不知道你们学没学到「贪心算法」。贪心，嗯，贪心一定是最好的吗？好，我们开始上课。

所以有另外一个算法，应该是从其他学科那里借鉴的经验，叫模拟退火。

模拟退火

什么意思呢，这个算法模拟了一个淬炼的过程。一开始，温度很高，算法更倾向于选择那些可能会走弯路的邻居。每次操作，温度都会降低，就更倾向于选择那些提升更大的邻居。说起来，怎么有点像少年老成的感觉呢？

不过不管怎么说，这种模拟的算法，就可以解决不愿意走弯路的问题。它会根据当前的温度，以及选择这个邻居导致的能量变化，根据一个公式来抉择到底是否走弯路。

旅行商问题

说到这，就不得不提大名鼎鼎的旅行商问题。学图论、学组合数学的时候已经听说过了，这是一个 NP-难问题，什么是 NP-难，我不想深究定义。但感性上认识，这是一个很难的问题，需要很多运算才能找到最优解，而且复杂度不可接受。

因此，可以通过爬山算法来找到相对比较好的解。因为有时候，我们只是在意一个不错的解，而不是最优的解。所以可以把旅行商问题进行解释与转换，转换为爬山问题，比如关于邻居的定义、对于高度的定义等等。

转变为熟悉的问题之后，就可以用已知的库来解决了。

线性规划问题

有时候，会遇到找线性表达式的最优值的题目。线性，看到了吗，就像线性代数一样，其实生活中的许多问题都是线性的。我们在乎的，是线性问题。

线性问题有以下两个基本组成成分：

  • 代价函数 - 是我们要求最值的一次多项式；
  • 约束 - 对每个变量与变量之间有约束。

这种都有成熟的库来调用。当然也可以用一些线性代数的方法来求解。

约束满足问题

线性规划是约束问题的一种，更广义的约束问题是这样的：

  • 变量的集合；
  • 每个变量的定义域；
  • 约束。

一个例子是安排考试。不同学生有不同的考试，一个学生的不同考试不能在同一个时间段。

这个问题中，每个考试就是一个变量，定义域是星期几，约束取决于每个学生选择的课程，可以用图这种数据结构来表示。

其实这种问题说到底是一种染色问题。给了一种图，每个变量是一个结点，用定义域的值给这些结点染色，找到一种可能的涂色方案。

哈！哈！哈！

解决问题的大致思路是这样的：

  1. 先解决一元约束，也就是对某个变量取值的限制。如某门课不能在星期一考试；
  2. 再解决二元约束，也就是两个变量之间的关系。例如两门课不能在同一个日子考试。

概括一下，前者解决的是结点的约束；后者解决的是边的约束。

第一点很好解决，一个 $O(n)$ 的遍历即可，这里的 $n$ 指的是 node。第二点就有些名堂了。

要考虑边的问题，要先选出一条边。考虑边两侧的结点 A 和 B。如果对于 A 定义域中的每个选择，B 中都能给出对应的选择。说明二者无冲突。否则，就要把 A 中让 B 拿不出对应选择的那个选择删除掉。

不过我感觉，这种检查应该是相互的，两个方向的。

每条边是可以解决了，但如何把不同的边联系在一起呢？可以用回溯法，是的，就是八皇后问题的回溯法。具体来讲，我觉得是 trial and error，如果找到了解，就返回；如果走到了死胡同，就退回到之前的状态，换个值再次查找。

诶，和搜索算法比较像？只不过搜索算法搜的是路径，这里搜索的是值。其实确实差不多，就是目标不同。

再优化

其实这里还有许多优化的空间，每一点都可以做文章。

  • 对于一个结点，要从值域中优先选取哪个值呢？
  • 对于一堆结点，要先选择哪个呢？
    • 如果定义域不同，怎么选？
    • 如果定义域相同，但度数不同，怎么选？
  1. 对于一个结点，选消除其他结点选择少的，因为这样在下一次递归中，我们有更多路可以走。
  2. 对于一堆结点，每个节点的定义域不同，选定义域少的。因为这样可以更快速的帮我们定位到解。怎么理解这点？因为如果有解的话，那 OK。如果无解的话，只需要递归最少的次数就可以发现，其他的点则需要递归更多次。
  3. 对于一堆结点，度数不同，则选度数大的，这样可以更多的减少需要考虑问题的规模。

这些地方，看上去有些矛盾。总的来说，目标是：减少问题规模、减少递归次数。

分别解释一下。

对于第一点，为什么不选消除多的，是因为这样会扼杀很多种可能性。很可能有一种选择方法就被抛弃了。

对于第二点，为什么不选定义域多的，是因为这样不会降低问题的规模。考虑假如有一个结点只剩下一个值可选，那必然要选它。有解的话，肯定就是它了；无解的话，通过它也可以最快的发现无解。

有人可能会说，这样不会扼杀很多种可能吗？放着多的不选。事实上，仔细思考，这并不会扼杀很多种可能。摆在我们面前的只是选择比较多，它和可能不在一个层次。就像是 C++ 对于重载运算符的匹配顺序一样。是，这个结点的选择很多，但是选择了之后，并不能保证扼杀的可能就小。

但能够确定的是，选定义域比较小的，可以有效的减少递归的层数。很好理解，假如一个结点就剩下两个值，另一个剩下十个值。那么，选前者，最多两次递归就能知道是否有解；后者，需要尝试很多次。

对于第三点，度数怎么选呢？这里还是从问题的规模来看。虽然说，选择了度数多的，会扼杀很多种可能，和第一点看似矛盾。确实矛盾，但一种解释是，可以快速地排除掉某些导致无解的选择。

总结一下吧，其实第一点主要是为了避免过早剪枝，第三点是为了加快问题收敛。

方案 选度数小的变量 选度数大的变量
搜索策略 保留更多可能性，避免过早剪枝 加速约束传播，减少搜索空间
适用于 搜索过程中解的密度较高（即解比较多） 搜索过程中解的密度较低（即解较少）
缺点 可能导致搜索空间过大，回溯较多 可能过早剪枝，导致找不到解

两种方案各有利弊，还是要根据具体问题来具体分析。

现实问题

其实如果从学校的现实背景来看，排课是个和这次主题很相似的问题。

每门课有许多时间段，有一些约束需要满足。这里

  • 每门课就是一个结点；
  • 结点的定义域是周次、时间段、教室；
  • 连边表示两门课之间有约束关系。

就像 SQL 一样，虽然教师也作为要考虑的约束，但最终我们的定义域不考虑教师。

这里的二元约束就有好多种啦。

  • 一位老师不可能同时讲两门课，但有时候也会有这种情况，比如说我的专业课拓扑学和一门选修课实际上在一个时间段；
  • 一个教室不能同时承担两门课的教学。还是上面的情景，这回确实不一样，公选课显示在博楼，专业课显示在学院教室；
  • 学生不能同时上两门培养方案在同一学期的专业课。

除此之外，还可能有一些一元约束，比如必须要智慧教室，不要南校区等等。

问题看上去很复杂，但如果归结为之前的问题，就很好解决了。