Chapter 2 绪论
这章特别长，大概会讲 14 个学时，鉴于 Jim 到了第 7 个学时才来上课，丢了很多东西，所以这里会补充的比较细。
2.1 组合最优化问题
我们很容易知道，组合最优化问题是指，给定一个可行域 \(F=\{x|x\in D, g(x)\geq 0\}\)，和一个目标函数 \(f(x)\)，求解 \(f(x)\) 在 \(F\) 上的最优解。也就是：
\[ \begin{aligned} \min_{x \in S} f(x) \\ \text{s.t. } g(x) \leq 0, \\ x \in D \end{aligned} \]
Example 2.1 (0-1背包问题) 假设有一个容积为 \(b\) 的背包，\(n\) 个尺寸为 \(a_i\,(i=1,2,\ldots,n)\)，价值分别为 \(c_i\,(i=1,2,\dots, n)\) 的物品，求解如何选择物品，使得背包中物品的总价值最大。这个问题可被表示为：
\[ \begin{aligned} \max &\sum_{i=1}^n c_i x_i \\ \text{s.t. } &\sum_{i=1}^n a_i x_i \geq b \\ x_i &\in \{0, 1\}, \quad i=1,2,\ldots, n \end{aligned} \]
Example 2.2 (旅行商问题) 假设有 \(n\) 个城市，每个城市之间的距离为 \(d_{ij}\)，求解一个最短路径，使得经过所有城市，且回到起点。这个问题可被表示为：
\[ \begin{aligned} \min &\sum_{i=1}^n d_{ij} x_{ij} \\ \text{s.t. } &\sum_{j=1}^n x_{ij} = 1, \quad i=1,2,\ldots, n \\ &\sum_{i=1}^n x_{ij} = 1, \quad j=1,2,\ldots, n \\ x_{ij} &\in \{0, 1\}, \quad i,j=1,2,\ldots, n \end{aligned} \]
这是一种基于图的问题，我们可以将城市看作图中的节点，城市之间的距离看作图中的边，这样就可以将问题转化为图的最短路径问题。
Example 2.3 (（一维）装箱问题) 假设有 \(n\) 个一维的箱子，每个箱子的尺寸为 \(d_i<1\,(i=1,2,\ldots,n)\)，求解如何以个数最少的长度为 \(1\) 的箱子装下所有的箱子。这个问题可被表示为：
\[ \begin{aligned} \min &\sum_{i=1}^n y_i \\ \text{s.t. } &\sum_{i=1}^n d_i x_{ij} \leq 1, \quad j=1,2,\ldots, n \\ x_{ij} &\in \{0, 1\}, \quad i,j=1,2,\ldots, n \\ y_{j} &\in \{0, 1\}, \quad j=1,2,\ldots, n \end{aligned} \]
以上三个问题都是组合最优化问题。
2.2 计算复杂性
计算复杂性的概念是为评估算法的计算耗用时间和解的偏离程度等指标而提出的。它以目前 2 进制计算机中的储存和计算为基础，以理论的形式系统描述。这一套理论产生于 20 世纪 70 年代，目前仍然是评估算法性能的基础。
2.2.1 规模
首先，我们考虑一个数在计算机中的表示。对于一个正整数 \(x \in [2^s, 2^{s+1}),x\geq 2\)，我们可以用 \(s+1\) 位二进制数表示它，即 \(x = \sum_{i=0}^s 2^i b_i\)，其中 \(b_i \in \{0, 1\}\)。这样，我们就可以用 \(s+1\) 位二进制数来表示一个正整数。
我们对 \(x\) 的存储空间做一个估计：
\[ 2^s \leq x < x+1 \leq 2^{s+1} \leq 2^{\log_2 x+1} \]
则
\[ \log_2(x+1) \leq s+1 \leq \log_2 x + 1 \]
因为
\[ \log_2 x + 1 - \log_2(x+1) < 1 \]
所以可以估计存储空间 \(l(x)\) 为
\[ l(x) = \left\lceil \log_2(x+1) \right\rceil \]
然后我们来计算线性规划实例规模：
对于问题
\[ \begin{aligned} \min c^Tx \\ \text{s.t. } Ax = b \\ x \geq 0 \end{aligned} \]
对于每一个条件，规模分别是：
\[ \begin{aligned} L_1 & = 2n+\sum_{i=1}^n \lceil \log_2(|c_i|+1) \rceil \\ L_2 & = 2mn+\sum_{i=1}^m\sum_{j=1}^n \lceil \log_2(|a_{ij}|+1) \rceil \\ L_3 & = 2m+\sum_{i=1}^m \lceil \log_2(|b_i|+1) \rceil \end{aligned} \]
总位数为 \(l(I)=4+\lceil \log_2(m+1) \rceil+\lceil \log_2(n+1) \rceil+L_1+L_2+L_3\)，可以得到：
\[ 2(mn+m+n+2)+\log_2 |P| < l(I) \leq 3(mn+m+n+2)+\log_2 |P| \]
2.2.2 计算量
O(x) 的含义是：一个实例为 \(I\)，实例规模为 \(l(I)\)，算法 \(A\) 在求解 \(I\) 时的计算量（基本计算总次数，包括加减乘除、读写、比较）为 \(C_A(I)\)。当存在一个函数 \(g(x)\) 和一个正常数 \(\alpha\)，使得对于该问题任意实例 \(I\) 均满足
\[ C_A(I) \leq \alpha g(l(I)), \forall I \]
则称算法 \(A\) 的计算复杂度为 \(O(g(l(I)))\)。
注：对多项式 \(g(x)\) 才有意义。
2.2.4 举例
Example 2.4 (求最大数) 给定 \(n\) 个数，求最大的数。
暴力枚举好了：从第一个数开始，读出赋值，比较大小，如果比当前最大值大，则更新最大值，否则不变。这样，对于 \(n\) 个数，需要 \(n\) 次读入，需要 \(n-1\) 次比较，每次比较需要 \(1\) 次赋值和 \(1\) 次比较，不管怎样，算法都是 \(O(n)\) 的。
Example 2.5 (TSP 问题) 给定 \(n\) 个城市及城市间距离，假定最大距离不超过 \(K\)，求解最短路径。
简单的方法是全排列，实例规模为 \(l(I)=O(n^2)\)，但是这样算法复杂度是 \(O(n!)\) 的，显然不可取。
接下来考虑一种短视方法：
- 记录一个行走城市路径和长度。初始行走路径为出发城市，长度为0。
- 算法的终止条件是：行走路径长度为 \(n\)，且行走路径的最后一个城市和出发城市相同。
- 循环计算一个城市到可以直接到达并且未经过的城市的距离，选择最小的距离，将城市加入行走路径，更新行走路径长度。
- 若路径中最后一个与第一个城市有直接连接，加入连接，得到一个可行解。
这样实例规模的下界为 \(O(n^2)\)。
我们来估计一下算法复杂度：假设目前已经走过 \(k\) 个城市，对行走路径的最后一个城市 \((i)\)，从第一个城市 (\(j\)) 开始的每个城市先判断下是否有直接路径，再判断是否已经走过，再决定是否加入行走路径中，最后更新目前行走的长度和城市列表。这样对于一个城市的最坏情况就应该是 \(O(n^3)\) 的。
所以 \(g(x)=x^{3/2}\)。