III. Classic Algorithms

倒排索引 Inverted File Index

Optimize a Search Engine

读取时的处理：

• word stemming
• stop words

阈值(thresholding)：

• document: 只检索前面 $x$ 个按权重排序的文档
• query：把带查询的 terms 按照出现的频率升序排序

搜索引擎的相关性度量(relevance measurement)：

• 准确率(precision)：指检索出相关文档数与检索出的文档总数的比率，衡量的是检索系统的查准率 $P_R=R_R/(R_R+I_R)$。
• 召回率(recall)：指检索出的相关文档数和文档库中所有的相关文档数的比率，衡量的是检索系统的查全率 $R_R=R_R/(R_R+R_N)$。

回溯 Backtracing

• 解空间约束

求解问题的一个可靠方法是找出所有可能得情况，逐一检查，找到正确答案。回溯(backtracing) 算法利用了剪枝(pruning) ，可以减少对大量已知不可能的情况的显示检查。

• 尽量选择从少到多的搜索方式，这样在剪枝的时候可以一次性剪掉更多的情况数。

Minimax Search & α-β Pruning

定义 goodness 函数为 $f(P) = W_\text{Computer} - W_\text{Human}$，则 Human 想要最小化 $f(P)$ 而 Computer 想要最大化 $f(P)$。

$\alpha-\beta$ 剪枝的核心思想：根据当前局面可以推定不会影响上层节点结果的就可以进行剪枝。

习题

Given the following game tree, which node in the right subtree is the first node to be pruned with α-β pruning algorithm?

答案

D。可以分析而知：无论节点 $d$ 的值是多少，都不会影响到根节点 $68$ 的值，故可以进行剪枝。

另外左子树中可以减掉的节点是 $38$。

Examples

Eight Queens

（八皇后问题）在棋盘中找到八个位置放置皇后，使得它们都不同行且不同列，也不能同时位于对角线上。

在游戏树上进行 DFS 搜索。

Turnpike Reconstruction Problem

在一条直线上找到 $n$ 个地方建立加油站，已知它们两两之间的距离（共 $\dfrac{n(n-1)}{2}$ 对），求出所有加油站的位置，假定第一个加油站的坐标是 $0$。

就是暴搜。在 DFS 过程中维护未分配的距离集合，还有当前的处理区间，每次从距离集合中找到最大的距离 $D$，看新的加油站应当放在 $x_1+D$ 的位置还是 $x_n-D$ 的位置即可。

Stick Problem

给一个从若干根长度为 $L$ 的大棍子里切出来的小棍子长度集合，求最小的可能的 $L$。

从小到大枚举 $L$ 然后将原来通过回溯法进行搜索。

Tic-tac-toe Game (play with computer)

经典井字棋小游戏。

这里定义 $W_\text{Player}$ 为 Player 能够赢得胜利的可能数（如果把剩下所有各自都填上你的棋子，可以有多少个三连），可以一定程度上表征局面对于自己的优劣情况。定义 goodness 函数 $f(P)=W_\text{AI}-W_\text{Player}$，使用 Minimax 搜索交替进行选手——计算机的对弈，需要使用 $\alpha-\beta$ 剪枝。

分治 Divide & Conquer

• 分治(divide conquer)

Complexity Analysis

分析分治算法的复杂度有三种常用的方法：

• 代换法(substitution method)：先猜对答案，然后使用数归证明。
• 递归树法(recursion-tree method)：写成多叉线段树的形式，每一层分别计算，最后加起来。
• 主方法(master method)：用主定理解决。

Master Theorems

主定理(master theorems)

习题

For each of the following recurrences, choose the one that we cannot apply the Master Theorems to solve.

A. $T(n) = 3 T(n/3) +n / \lg n$

B. $T(n) = 4 T(n/2) +n / \lg n$

C. $T(n) = 4 T(n/2) +n^2 / \lg n$

D. $T(n) = 3 T(n/4) +n \lg n$

答案

AC？然而 pta 上的答案是 A。

Examples

Closest Point Problem

给平面上 $n$ 个点，求解最近点对。

动态规划 Dynamic Programming

• 背包问题(the knapsack problem)

Examples

Fibonacci Numbers

$a_n=a_{n-1}+a_{n-2}$，求解 $a_n$。

两种实现：启发式搜索或者直接序列 DP，都是用一张表来存 $a_n$。

Ordering Matrix Multiplications

安排 $n$ 个矩阵的乘法的计算顺序，最小化计算量。（第 $i$ 个矩阵 $M_i$ 的大小是 $r_{i-1}\times r_i$）

区间 DP，$f[i][j]=f[i][k]+f[k+1][j]+r[i-1]\times r[k]\times r[j]$。

Optimal Binary Search Tree

给 $n$ 个词的搜索频率，应如何构建 BST 以最小化 access 期望代价？相比于 Haffman 编码问题，我们确定了中序遍历，且内部节点上也能有键值。

从最优子结构转移：最优方案的两棵子树一定是最优方案。定义 $w_{i,j} =\sum_{k=i}^j p_k$，$c_{i,j}$ 表示给区间 $[i,j]$ 节点建树的最小花费，则有转移：

$$c_{i,j} = \min\limits_{i\le k\le j} \{p_k + w_{i,k-1} + c_{i,k-1} + w_{k+1,j} + c_{k+1,j} \} = w_{i,j} + \min \{c_{i,k-1}+c_{k+1,j}\}$$

All-Pairs Shortest Path

求任意两点间最短路径。

我看了看怎么感觉就是 Floyd 啊？

Product Assembly

有 $n$ 步的工序，可以在两条生产线之间切换，消耗的时间和本次及上千次在哪条生产线完成有关，求最优生产流程。

我看了看怎么感觉就是直接 DP 啊？

贪心 Greedy

Examples

Activity Selection Problem

DP 做法：设 $dp_{i}$ 表示前 $i$ 个单位时间里最多选几个，找到所有 $f_t-1=i$ 的活动，从 $dp_{s_t - 1} + 1$ 转移。时间复杂度 $O(n^2)$，不够优秀。

贪心做法：把所有区间按照右端点排序，每次取右端点最小的，即选择尽早结束的活动（反过来也可，即选择最迟开始的活动），然后把有重合的都删掉，如此循环直到结束。时间复杂度 $O(n\log n)$。

Huffman Codes

哈夫曼编码问题。

建 Huffman 树的过程正体现了贪心思想。

近似 Approximation

Approximation Ratio

设 $C$ 为我们算法的 cost，$C^\ast$ 为最优解的 cost，定义近似率(approximation ratio) 为：

$$\max\left(\dfrac{C}{C^\ast},\dfrac{C^\ast}{C}\right) \le \rho(n)$$

• 称这样的算法为 $\rho(n)$-approximation algorithm
• approximation scheme: 近似率 $\rho(n)=1+\epsilon$ 的算法，即 $(1+\epsilon)$-approximation algorithm
• PTAS：polynomial-time approximation scheme 关于 $n$ 成多项式复杂度的算法 (设 $\epsilon$ 为常数)
• FPTAS：fully polynomial-time approximation scheme 关于 $n$ 和 $\epsilon$ 都成多项式复杂度的 算法

On-line & Off-line Algorithms

在读入数据的时候进行决策，一旦决策之后不能修改。

Examples

Approximate Bin Packing

Given $N$ items of sizes $S_{1},S_{2},\cdots,S_{N}$, such that $0<S_i\leq1$ for all $1\leq i\leq N$. Pack these items in the fewest number of bins, each of which has unit capacity.

——这一问题是 NP-Hard 的。

Next Fit 做法：依次读入每个物品，看看是否能和前一个物品放在同一个 bin，如果不行的话就开一个新 bin。

证明：设最优解为 $M$，则用 Next Fit 做法得到的解不超过 $2M-1$。

设用 Next Fit 做法生成的解为 $2M$（或 $2M+1$），那么有 $S_{2i-1}+S_{2i} > 1 \space (1\le i\le M)$，故 $\sum_{i=1}^{2M} S_i > M$，故至少需要 $M+1$ 个 bin。

First Fit 做法：依次读入每个物品，扫描所有已有的箱子，找到第一个能放下的放，如果不存在则新开一个箱子放。设最优解为 $M$，则得到的解不超过 $1.7M$。

Best Fit 做法：依次读入每个物品，在可以放下这一物品的箱子中选剩余空间最小的，如果不存在则新开一个箱子放。设最优解为 $M$，则得到的解不超过 $1.7M$。

这里的 Next Fit、First Fit 和 Best Fit 做法都是在线做法，如果允许离线，则可将所有物品按照体积从大到小排序，然后应用 First Fit（或 Best Fit）做法。设最优解为 $M$，则得到的解不超过 $\dfrac{11 M+6}{9}$。

The Knapsack Problem (0-1 Version)

就是 0-1 背包问题。

• 用 DP 解决的复杂度是指数级的，因为物品大小和 $n$ 不同阶，实际上 Knapsack 问题是 NP-Hard 问题，Knapsack 的判定是 NPC 问题。
• 如果将物品的大小缩放到 $poly(n)$ 的范围，则有多项式复杂度的 DP，但算法也变成了近似算法。

如果使用贪心做法，每次选（可选的）里价值最高或性价比最高的（两种做法分别做一次），可以证明近似比为 $2$。

证明：贪心做法的近似比为 $2$。

这里 $P_\text{Greedy}$ 是两种贪心做法得到结果的 max。

The K-center Problem

平面上给定 $n$ 个点，确定 $K$ 个圆心的位置覆盖所有点并使最大圆的半径最小。

定理：除非 $\text{P}=\text{NP}$，否则不存在 $\text{ratio}<2$ 的解法。

若 K-center 存在 $(2-\epsilon)$-approximation，则可用于精确求解 Dominating Set 问题，而后者是一个 NPC 问题。

局部搜索 Local Search

• $S \sim S'$：$S'$ 是 $S$ 的一个相邻解(neighboring solution)，只需要对 $S$ 进行一个微小的修改就可以得到。
• $N(S)$：$S$ 的邻域(nerghborhood)，即 $\{S'\mid S\sim S'\}$。
• 称 $S^\ast$ 是 $S$ 的 local optimum，即 $S^\ast\in N(S)$ 且是其中最优的。

Gradient Descent

爬山——梯度下降法：每次在邻域中选一个最优的转移，如果找不到则退出。

容易陷入局部最优解中。

The Metropolis Algorithm

模拟退火——Metropolis 算法：每次在邻域中随机选一个转移，如果比当前情况更有则以一定概率 $-e^{\dfrac{\Delta cost}{k T}}$ 接收，否则概率接收且这一概率随迭代次数指数下降。

Examples

Vertex Cover Problem

最小点覆盖问题。

直接使用爬山问题容易陷在 e 局部最优解，建议使用模拟退火算法。

Hopfield Neural Network

给定 $G=(V,E)$ 其中边权有正负，给每个节点分配一个 $s_u\in\{-1,1\}$，称一个点是 state assignment 当且仅当

state-flipping 算法：每次反转一个不稳定的节点作为转移。

证明：State-flipping 算法一定能达到一个稳定状态，且最多反转 $W = \sum_e |w_e|$ 次。

Maximal Cut Problem

最大割问题。把点集划分为两部分 $A,B$，最大化 $w(A,B) = \sum_{u\in A, v\in B} w_{u,v}$。

采用类似于上一问的转移，即翻转一个点的状态。若进行爬山算法，可以得到一局部最优解 $A,B$。设最优解为 $A^\ast,B^\ast$。

证明：$w(A,B) \ge \dfrac{1}{2} w(A^\ast, B^\ast)$。

big-improvement-flip 算法：当新的局部最优解的增长的幅度小于 $\dfrac{2\varepsilon}{|v|} w(A,B)$ 的时候就停止，这样算法可以在一定近似比的代价下保证在多项式复杂度内结束。

定理

这样就有 $(2+\varepsilon) w(A,B) \ge w(A^\ast, B^\ast)$，可以在最多 $O\left(\dfrac{n}{\varepsilon} \log W\right)$ 次翻转后结束。

随机化 Randomize

有两种随机算法：

• 有非常高的概率给出正确答案。efficient randomized algorithms that only need to yield the correct answer with high probability
• 总是正确的，并在期望中运行的很有效率。 randomized algorithms that are always correct, and run efficiently in expectation

Random Shuffle

给每个元素分配一个随机的 key：a[i].key = rng() % (n * n * n)，然后根据 key 进行排序。根据生日碰撞，这里取 $N^3$ 作为模数就能有一个不错的效果。

Examples

The Hiring Problem

• Hire an office assistant from headhunter.
• Interview a different applicant per day for $N$ days.
• Interviewing Cost = $C_{i} \ll$ Hiring Cost $=C_{h}$
• Analyze interview & hiring cost instead of running time
• Assume $M$ people are hired. Total Cost: $O(N C_{i} + M C_{h})$.

总花费 = 面试次数 $\times$ 每次面试的花费 $+$ 雇佣人数 $\times$ 雇佣费用。

一种简单的做法：看到比先前更好的人就雇佣，但是在面试者按照优秀程度递增顺序进来的时候就会爆炸。不妨进行随机排序，则期望花费为 $O(C_h \ln N + N C_i)$。

Online Hiring Problem - Hire at Once

将前面的问题改为在线，但只能雇佣一次。

一种较高概率成功的解：先面试前 $k$ 个人但一定不从中雇佣，然后依次面试第 $k+1\cdots N$ 个人，其中第一个满足比前 $k$ 个人优秀即 $A_j = \max_{i=1}^k A_i$ 的人进行雇佣。可以证明取 $k = \dfrac{N}{e}$ 时最优。

证明：最优解 $k = \dfrac{N}{e}$。

根据微积分的知识我们有：

$$\ln N-\ln k = \int_k^N \dfrac{1}{x}\text dx \le \sum_{i=k}^{N-1} \dfrac{1}{i} \le \int_{k-1}^{N-1} \dfrac{1}{i} \text dx = \ln (N-1) - \ln(k-1)$$

那么取到最优解的概率为：

$$Pr[S] = \sum_{i=k+1}^N Pr[S_i] = \dfrac{k}{N} \sum_{i=k}^{N-1} \dfrac{1}{i} \sim \dfrac kN \ln \left(\dfrac Nk\right)$$

根据高中数学的知识可以知道取 $\dfrac N k=e$ 时最大即 $k=\dfrac{N}{e}$，且概率为 $\dfrac{1}{e}$。

Quicksort

众所周知，直接选中间位置作为 pivot 的快速排序是可以被卡到 $O(n^2)$ 的，那应该怎么选呢。

随机一个数作为 pivot，但如果这一 pivot 是最小的 1/4 或最大的 1/4 则重选，期望意义下只重选一次。

这样至少会将规模划分为 $\dfrac{n}{4}$ 和 $\dfrac{3n}{4}$，可以证明复杂度是 $O(n\log n)$。

并行算法 Parallel Algorithm

两个模型：Parallel Random Access Machine (PRAM)；Work-Depth (WD)。

PRAM Model

WD Model

【WD-presentation Sufficiently Theorem】An algorithm in the WD mode can be implememnt by any $P(n)$ processors within $O(W(n)/P(n) + T(n))$ time, using the same concurrent-write convention as in the WD presentation.

Maximal Finding

找 $n$ 个数的最大值，并行算法。

• Replace ”+” by “max” in the summation algorithm. $T(n)=O(\log n),\ W(n)=O(n)$
• Compare al pairs (find $B(i)=0$). $T(n)=O(1),\ W(n)=O(n^{2})$
• Doubly-logarithmic Paradigm: Parition by $n^{1/2}$. $T(n)=O(\log \log n),\ W(n)=O(n \log \log n)$
• Paritition by $h=\log \log n$. $T(n) = O(\log \log n),\ W(n) =O(n)$
• Random Sampling. $n^{7/8}=n^{3/4} \times n^{1/8},\ n^{3/4}=n^{1/2} \times n^{1/4}$. $M(n^{7/8}) \sim T = O(1),\ W=O(n)$.

外部排序 External Sorting

我们只有有限的内存（只能存放 $M$ 个数）和若干 tape（一种特殊的存储结构，只能顺序读写），需要解决排序问题。

这个具体的过程特别抽象我懒得记录了，可以看一下别人的笔记。不过别因为这个是最后一讲就不看了，似乎是每年必考的内容。