前言

• 众所周知，ACGN是二次元文化圈中的拓展词汇，其中C代表的正是Combination，数学的一个分支——组合学。顺带一提，A是algebra（代数），G是geometry（几何），N是number theory（数论），绝对不是什么英文Animation（动画）、Comic（漫画）、Game（游戏）、Novel（小说）的合并缩写。

本文主要是对堵丁柱的《组合优化导论》的学习笔记。看生肉教程，翻土味情话。实话说，对于introduction类型的书，一般是入门用的，而这本书疑似有点太极端了，不好确认是萌新该看的。

正文

第一章是介绍，默认了读者学习过一点基础数学（集合论等）的知识。开门见山，组合优化就是在有限集（finite set）中，找到最优对象（optimal object）。你的人生就是一个组合优化问题，找不到对象，就是数学不好（学数学学的）。当然还有别的例子：

• 最小生成树（minimump[^1] spanning tree），带着非负权边的有限图集G=(V,E)，找到权值最小的生成树，生成树就是包含G中所有顶点的树，显然是这个问题中的可行解（feasible solution），且是有限的，而最小的权值代表最优，最优的那个可行解称为最优解（optimal solution）。类推一下，最大生成树也是组合优化问题。
  [^1]: minimum是最低的，而minimal是最小的

这里稍微提一下已经学了很多遍的Kurska’s

• 最短长度路易十六断头台分割（Minimum Length Guillotine Partition），一个矩形里面有几个点，你要分割矩形为几个小矩形，而且每个小矩形中都不包含这些点，要求分割线段最短。有无限个分割方案（线段的无限细分），所以不是个组合优化问题，不过确实可以找到一个最优解。断头台分割指的是用一条横线或竖线将一个大矩形分割为两个小矩形。使用这种分割，那么一个含有有限点的矩形的分割方案是有限的（less than 2^n）。简单的线段分割包含断头台分割，要是能证明断头台分割包含最优分割，则能转化为组合优化问题。

断头台是直译，下文皆使用更一般的翻译：二分分割是由一系列二分线组成。

引理1（标准分割）：最短长度二分分割中的每一条二分线都经过一个点

证明 反证法，假设存在一条不经过任何点的二分线AB，不妨假设AB是竖线，假设AB左边接触的二分线有n1条，AB左边接触的二分线有n2条，不妨假设n1>=n2，那么，可以将AB向左平移，此操作不增加长度，直到AB经过左边某个点，或者与其他线重合。别的情况也是同理，就可以删除二分线AB，所以不存在这么一个偷懒的二分线。