给出一组任务，要求“选出尽可能多的不冲突任务”，与要求“选出总收益最高的不冲突任务”，看起来只改了几个字，却可能需要完全不同的算法。

前者可以使用贪心策略；后者通常需要动态规划。再把任务间的冲突关系从时间轴推广到任意图，问题又会变得更困难。

本文根据《Design and Analysis of Algorithms》第一讲 Introduction 的知识部分整理。重点回答：

  • 怎样把一句需求变成能求解的问题？
  • 问题、算法、程序分别是什么？
  • 怎样判断一个算法正确且足够高效？
  • 为什么有的问题适合贪心，有的需要动态规划，有的暂时没有已知的通用高效精确算法？

0. 已有知识与本文的位置

需要回顾的知识 已有文章中的位置 本文怎样使用
集合、子集、基数 集合与集合运算 把一个解表示为任务、边或顶点的子集
半开区间 区间与无穷 明确两个任务在端点相接时是否兼容
顶点、边、邻接关系 图的基本概念 表达匹配和独立集的约束
排序方法 排序文章 将任务按结束时间排序，不重复展开排序实现
折半查找 顺序查找和折半查找 高效寻找动态规划中的前驱任务
启发式调度 HEFT解决的问题 对比不同调度模型，理解启发式不等于最优保证

本文的主线是：先写清模型，再研究正确性与资源消耗，最后根据问题结构选择方法。

1. 先区分问题、算法和程序

1.1 问题规定“什么结果算正确”

假设有一个会议室，若干活动都想使用它。一个完整的问题至少要说清四件事：

项目 本例中的含义
输入 每个活动的开始时间和结束时间
输出 被接受的活动编号集合
可行性约束 被接受的活动不能占用同一时刻的会议室
优化目标 被接受的活动数量最多

还要补充边界约定：本文把活动写为半开区间 $[s_j,f_j)$，要求 $s_j<f_j$，且不允许中途拆分活动。

这样，$[1,4)$ 和 $[4,7)$ 可以连续安排；若需要清场时间，就必须修改兼容条件，不能继续直接套用这个模型。

“同一个输入对应确定的答案含义”，不等于“同一个输入只能有一份合法方案”。 课件用输入到输出的函数帮助理解问题，但优化问题可能存在多份同样最优的解。不同程序输出不同的最优方案，也可能都正确；若接口要求结果唯一，需要额外规定平局时的选择规则。

1.2 算法规定“按照什么步骤求解”

对同一个调度问题，可以提出不同算法：

  • 枚举所有活动子集，逐一检查，再选数量最多的。
  • 每次选最早开始的活动。
  • 每次选最早结束的活动。

这些都是明确的操作思路，但它们不一定都正确，也不一定同样高效。

算法通常需要输入、输出、明确且可执行的步骤，并在规定的合法输入上有限终止。伪代码便于表达思路，暂时不必纠结某种语言的语法。

1.3 程序是算法的具体实现

同一个贪心算法可以用 Python、C++ 或 Java 实现。但实现还会引入类型、排序稳定性、边界条件、溢出和数据结构等问题。

从问题模型到算法再到程序的流程，以及正确性和复杂度的检查位置

可以分别检查两层正确性：算法在数学上是否能解决问题；程序是否忠实实现了这个算法。编译通过只能说明语法等检查通过，不能替代这两层判断。

2. 判定、最优值、最优解与数值计算

课件把问题分为判定、优化和数值计算几种类型。优化问题中，又要区分“最优值”和“最优方案”。

用后面的带权调度例子说明：

问题形式 提问方式 输出形式
判定问题 是否存在总收益至少42的兼容方案？ 是或否
最优值问题 最大总收益是多少？ 42
最优解问题 哪些任务能实现这个最大收益？ 任务 d、h

知道最优值是42，并不自动等于已经知道选哪些任务。动态规划如果只保存最优值，通常还需要回溯才能恢复方案。

反过来，有了一个最优方案，通常可以直接计算它的目标值。对整数目标且已知上下界的问题，也常能把优化问题与多次判定联系起来，但需要分析调用次数与数值编码长度，不能无条件认为两种形式完全相同。

数值计算则可能要求求出具体数值。例如：

$$ 2x+y=5,\qquad x-y=1 $$

消去变量得到 $x=2,y=1$。更一般的数值问题还要说明允许误差、数值稳定性和精度要求；“输出一个数”不代表可以忽略这些要求。

3. 分析算法时，至少问三个问题

3.1 它会不会结束

例如每轮从有限任务列表中处理一个未处理任务，最多处理完全部任务就停止。循环“直到找到最优解”则不够，必须说明怎样识别最优解、为什么最终能找到。

3.2 它是否对所有合法输入都正确

测试几个例子没有出错，不能证明对所有输入都正确。常见的证明方法包括循环不变式、归纳法和交换论证。

反过来，要否定“每次选最早开始的活动一定最优”，只需要一个反例：

$$ a=[0,10),\qquad b=[1,2),\qquad c=[2,3),\qquad d=[3,4) $$

最早开始策略会先选 a，只得到1个活动；选 b、c、d 可以得到3个。这个反例推翻的是该策略，不是推翻整个区间调度问题存在高效算法的可能性。

3.3 它消耗多少时间和空间

先定义输入规模，再讨论复杂度。活动数量可以记为 $n$；图问题常用顶点数 $n=|V|$ 和边数 $m=|E|$。

对 $n$ 个任务，每个任务有“选”与“不选”两种状态，子集数量是 $2^n$：

任务数量 子集数量
10 1,024
20 1,048,576
40 1,099,511,627,776

而检查一个子集是否可行，还要额外花时间。因此不能把 $2^n$ 直接当成完整运行时间。

还要区分“一个数的大小”和“表示这个数需要的位数”。若整数 $N$ 用二进制编码，输入长度约为 $\log_2 N$，循环 $N$ 次并不一定是关于输入长度的多项式时间。位数与取值数量的区别，可以回看上一篇的对数例子。

4. 区间调度：为什么选择最早结束的任务

4.1 沿用课件中的8个任务

课件第27页与第28页使用相同的时间区间；后一页为每个任务增加权重。

任务 开始时间 结束时间 权重
a 0 6 23
b 1 4 12
c 3 5 20
d 3 8 26
e 4 7 13
f 5 9 20
g 6 10 11
h 8 11 16

本节先忽略权重。目标是找一个兼容任务子集 $S$，使 $|S|$ 最大，而不是让时间轴尽量被占满。

4.2 按结束时间排序，依次扫描

排序后的顺序为 b、c、a、e、d、f、g、h。

当前任务 检查 决定
b：$[1,4)$ 当前还没有任务 选择，结束时间变为4
c：$[3,5)$ 开始时间3早于4 跳过
a：$[0,6)$ 开始时间0早于4 跳过
e：$[4,7)$ 开始时间4等于4 选择，结束时间变为7
d：$[3,8)$ 开始时间3早于7 跳过
f：$[5,9)$ 开始时间5早于7 跳过
g：$[6,10)$ 开始时间6早于7 跳过
h：$[8,11)$ 开始时间8不早于7 选择

得到 $S=\{b,e,h\}$，共3个任务。

课件8个区间任务，以及数量最优方案b、e、h和权重最优方案d、h的比较

4.3 “最早结束”为什么能保证最优

直觉是尽早释放会议室，但直觉本身不是证明。可以用一次交换说明第一步没有损失：

  1. 取任意一个最优方案，把其中任务按时间排列，设第一个任务是 o。
  2. 贪心选的任务 g 在所有任务中最早结束，因此 $f_g\le f_o$。
  3. 用 g 替换 o 后，原方案中其余任务仍在 $f_o$ 之后开始，也就仍能接在 g 后面，任务数没有减少。
  4. 因而至少存在一个以 g 开头的最优方案。再对 g 结束后的剩余任务重复同样的论证。

关键不是“局部选了一个看起来不错的任务”，而是证明这一步能被某个全局最优解接纳。

排序花费 $O(n\log n)$，扫描花费 $O(n)$，总时间为 $O(n\log n)$。若输入已经按结束时间排序，扫描部分只需线性时间。

5. 带权区间调度：目标一变，贪心就不够了

5.1 最大数量不一定对应最大收益

仍使用上面的8个任务。最早结束策略得到 b、e、h，总权重为：

$$ 12+13+16=41 $$

而 d、h 只有两个任务，却有：

$$ 26+16=42 $$

所以不能把无权问题的最优性证明直接搬过来。之前用 g 替换 o 保持了任务数量，却不一定保持收益。

5.2 状态与前驱分别表示什么

仍按结束时间排序，并用 $j=1,\ldots,n$ 给任务重新编号。

  • $OPT(j)$：只允许从前 j 个任务中选择时，能得到的最大总权重。
  • $p(j)$：排在 j 前面、结束时间不晚于 j 的开始时间的最大编号；不存在时取0。
  • $OPT(0)=0$：没有任务可以选时，收益为0。

为什么只要记住一个前驱编号？因为结束时间有序，与 j 兼容的前面任务恰好形成一个前缀，编号不超过 $p(j)$。

5.3 最优方案只有“选j”和“不选j”两类

不选 j，只能从前 j-1 个任务中选择，最优值为 $OPT(j-1)$。

选 j，则所有同时选的更早任务都必须在 j 开始前结束，最优收益为 $v_j+OPT(p(j))$。

两种情况覆盖全部可行方案，因此：

$$ OPT(j)=\max\bigl(OPT(j-1),\ v_j+OPT(p(j))\bigr) $$

这不是试出来的公式，而是对所有最优方案作了不遗漏的分类。

5.4 把整张表算出来

j 任务 区间 权重 p(j) 选当前任务 不选当前任务 OPT(j)
0 无 无 0 无 无 无 0
1 b $[1,4)$ 12 0 12+0=12 0 12
2 c $[3,5)$ 20 0 20+0=20 12 20
3 a $[0,6)$ 23 0 23+0=23 20 23
4 e $[4,7)$ 13 1 13+12=25 23 25
5 d $[3,8)$ 26 0 26+0=26 25 26
6 f $[5,9)$ 20 2 20+20=40 26 40
7 g $[6,10)$ 11 3 11+23=34 40 40
8 h $[8,11)$ 16 5 16+26=42 40 42

例如计算 h 时，$p(8)=5$ 表示 d 恰好在时间8结束。选择 h 可以接上前5个任务的最优方案，而不是只能接“单个前驱任务 d”；只是本例中这个前缀的最优方案恰好只有 d。

5.5 从最优值回到最优解

从最后一行往回看：

  1. $16+OPT(5)=42>OPT(7)=40$，选 h，跳到第5行。
  2. $26+OPT(0)=26>OPT(4)=25$，选 d，跳到第0行。
  3. 结束，按时间顺序返回 d、h。

前驱可以用折半查找在每个任务上花 $O(\log n)$ 时间预处理，填表与回溯均为 $O(n)$，整体仍为 $O(n\log n)$ 时间、$O(n)$ 额外空间。

6. 用Python核对两种调度结果

下面只使用标准库。每个任务用 (名称, 开始, 结束, 权重) 表示；半开区间满足开始时间严格小于结束时间。平局时动态规划选择“不选当前任务”，因此回溯与填表的规则一致。

from bisect import bisect_right


def order_jobs(jobs):
    ordered = sorted(jobs, key=lambda job: (job[2], job[1], job[0]))
    if any(start >= finish for _, start, finish, _ in ordered):
        raise ValueError("Each job must have start < finish")
    return ordered


def interval_scheduling(jobs):
    selected = []
    last_finish = float("-inf")
    for name, start, finish, _ in order_jobs(jobs):
        if start >= last_finish:
            selected.append(name)
            last_finish = finish
    return selected


def weighted_interval_scheduling(jobs):
    ordered = order_jobs(jobs)
    finishes = [job[2] for job in ordered]
    n = len(ordered)
    previous = [0] * (n + 1)
    best = [0] * (n + 1)

    for j, (_, start, _, weight) in enumerate(ordered, start=1):
        # The eligible prefix ends strictly before the current array entry.
        previous[j] = bisect_right(finishes, start, 0, j - 1)
        best[j] = max(best[j - 1], weight + best[previous[j]])

    selected = []
    j = n
    while j > 0:
        name, _, _, weight = ordered[j - 1]
        if weight + best[previous[j]] > best[j - 1]:
            selected.append(name)
            j = previous[j]
        else:
            j -= 1
    selected.reverse()
    return selected, best[n]


jobs = [
    ("a", 0, 6, 23),
    ("b", 1, 4, 12),
    ("c", 3, 5, 20),
    ("d", 3, 8, 26),
    ("e", 4, 7, 13),
    ("f", 5, 9, 20),
    ("g", 6, 10, 11),
    ("h", 8, 11, 16),
]

print(interval_scheduling(jobs))
print(weighted_interval_scheduling(jobs))
assert interval_scheduling(jobs) == ["b", "e", "h"]
assert weighted_interval_scheduling(jobs) == (["d", "h"], 42)
assert weighted_interval_scheduling([]) == ([], 0)

输出：

['b', 'e', 'h']
(['d', 'h'], 42)

bisect_right 返回满足条件的前面任务数量，恰好对应这里1开始编号的前驱下标。使用右侧插入位置，意味着结束时间等于开始时间的任务也被视为兼容；hi=j-1 则把搜索限制在当前任务之前。

这两种方法都是各自模型下的精确算法，并不是“贪心一定不精确、动态规划一定更高级”。先看模型，再讨论算法性质。

7. 二分图匹配：选的是边，不是顶点

7.1 把“能不能分配”表示成边

二分图把顶点分成两侧 $L,R$，每条边连接不同侧的顶点。例如左边是求职者，右边是岗位，边表示具备对应资格。

匹配 $M\subseteq E$ 是一个边集合，其中任意两条边都没有公共端点：一个人最多拿到一个岗位，一个岗位最多给一个人。

课件第29页展示的一个匹配为：

$$ M=\{(A,1),(B,2),(C,4),(D,3),(E,5)\} $$

所有边都存在，而且没有重复使用任何端点，大小为5。左右两侧各只有5个顶点，任何匹配都不可能超过5条边，所以这个匹配已经达到上界，是最大匹配。

7.2 被占用的岗位，不一定永远不能再考虑

考虑一个更小的二分图：A 可以匹配岗位1或2，B只能匹配岗位1。

如果先选 A-1，B 就无岗位可选。直接停止只能得到1条边，但可以先把 A 调整到2，再把1分配给 B。

二分图中的增广路：撤销A到1，再加入B到1和A到2，使匹配数从1增加到2

路径 B → 1 → A → 2 上，未选边、已选边、未选边交替出现。把这条路径上的选择状态全部翻转，会删掉1条已选边、增加2条未选边，匹配数净增1。

这叫增广路。它说明“没有一条边能直接加进去”，不等于“不能通过重新安排得到更大的匹配”。

对一般二分图，重复寻找增广路可以求最大匹配；此处先理解调整过程，不展开完整匹配算法。

课件第29页的目标是无权最大匹配，第32页汇总又提到了带权匹配。两者目标不同：一个最大化边数，一个最大化边权总和。算法名称和复杂度也需要跟具体版本对应，不能把汇总中的简略复杂度直接当作所有匹配算法的统一界限。

8. 独立集：把任意冲突关系表示成图

8.1 独立集要求选中的顶点之间没有边

给定无向简单图 $G=(V,E)$，独立集是满足下式的顶点集合 $S\subseteq V$：

$$ \forall u,v\in S,\ u\ne v\Longrightarrow\{u,v\}\notin E $$

如果顶点代表任务，边代表冲突，那么独立集就是一组两两不冲突的任务。

沿用课件第30页的图，其边为：

1-2, 1-3, 2-3, 2-4, 2-5, 3-6, 4-7, 5-7, 6-7

其中 $S=\{1,4,5,6\}$ 是大小为4的独立集。

同一个图中的最大独立集与极大但非最大的独立集

为什么不可能选5个？顶点1、2、3构成三角形，最多选1个；剩下只有4、5、6、7，其中7与另外三个都有边，最多选3个。因此任何独立集大小最多是 $1+3=4$，上述方案达到上界。

8.2 最大与极大，差一个字但不是一回事

  • 最大独立集：在所有独立集中，顶点数量最多。
  • 极大独立集：在当前独立集基础上，不能再直接加入其他顶点。

本图中的 $\{2,7\}$ 是极大独立集：其余每个顶点都与2或7相邻，所以不能直接添加。但是它只有2个顶点，不是最大独立集。

与匹配中的重新安排类似，局部“加不进去”不代表全局最优。

8.3 区间调度为什么没有因此变难

可以把每个区间当作一个顶点，有重叠的区间之间连边。于是无权区间调度对应这个冲突图上的最大独立集，带权调度对应最大权独立集。

关键区别在于：区间之间形成的是具有特殊结构的区间图，而不是任意图。时间轴的顺序结构支持前面的贪心和动态规划。

一个问题在某种特殊图上容易，不代表推广到一般图后仍然容易；反过来，一般图上的困难性，也不妨碍特殊图上的高效算法。

9. P、NP与NP完全：到底在分类什么

9.1 首先明确讨论的是判定问题

P：能在输入编码长度的多项式时间内求解的判定问题类。

NP：对于答案为“是”的实例，存在长度为输入长度多项式界内的证书，可以在多项式时间内验证。这里不是要求对所有“否”实例也有同样形式的证书。

例如独立集的判定版本是：“图中是否存在大小至少 k 的独立集？”别人交来一个顶点集合，可以检查大小是否达到 k，并检查图中每条边的两个端点是否都被选入。这个检查可在多项式时间内完成。

但检查“这个集合可行且大小达到 k”，不等于检查“这是全局最大的独立集”。更不能因为能验证一个候选解，就断言能快速找到最优解。

$$ \mathrm P\subseteq\mathrm{NP} $$

能快速直接解决的问题，当然也能快速验证；NP不是“非多项式”的缩写，更不是“所有困难问题”的统称。定义可参考 Stephen Cook 的官方问题说明。

9.2 NP完全不是“已经证明只能穷举”

一个判定问题 C 是 NP完全（NP-complete，简称NPC），需要同时满足：

  1. C 属于NP。
  2. 所有NP问题都能在多项式时间内归约到 C。

“把 A 归约到 B”可以理解为：高效地把 A 的实例变成 B 的实例，使对 B 的求解能够回答原来的 A。方向不能写反。

因此，只要某一个NP完全问题存在多项式时间算法，就会推出 $\mathrm P=\mathrm{NP}$。目前这一等式是否成立仍是未解决问题，不能把常见的示意图理解为已经证明P与NPC完全分离。Clay Mathematics Institute 的问题页面仍将其列为未解决问题。

课件中的“独立集是NP完全”，严格来说指它的判定版本。求最大独立集的优化版本通常称为NP困难（NP-hard），不要混用两种说法。

9.3 算法的上界，不是问题的下界

我们写出一个指数时间算法，只说明“这个算法可能很慢”，不等于证明“所有算法都必须这么慢”。

同样，多项式时间也不等于实际一定快：很高的次数、大常数和大规模输入都可能让它不实用。理论复杂度、实现开销和实际数据分布要一起看。

10. 遇到难问题，并不只有穷举或放弃

课件列出几类思路。区别不在于名字听起来是否高级，而在于放弃什么、保留什么保证。

方法 保留或追求什么 需要注意
启发式算法 尽快找到质量较好的可行解 通常没有统一的最优性或近似比保证
近似算法 多项式时间，并提供明确的解质量保证 保证必须有证明，不是只看测试平均效果
快速精确算法 仍返回真正最优解 最坏情况时间可能仍是指数级
参数化算法 利用某个参数较小的特点 要说清参数是什么，以及时间怎样依赖它

启发式并不等于“输出是否可行都不知道”。例如可以始终保持方案可行，只是不保证它全局最优。已有的HEFT文章就是理解启发式调度的一个入口，但它处理的是带依赖与异构处理器的另一种模型，不是本文的单会议室区间选择。

10.1 用一个数理解近似保证

对非负目标值，采用 $\rho\ge1$ 的比值约定：最大化问题的 $\rho$ 近似保证可写为 $ALG\ge OPT/\rho$；最小化问题则写为 $ALG\le\rho OPT$。

例如，最大化问题的最优值是100，一个有2近似保证的算法至少要得到50。这个例子只解释保证的含义，不是在声称任意问题都存在2近似算法。

课件还提到PTAS。它是多项式时间近似方案，不是与P、NP相同意义的判定复杂性类。对最小化问题，给定误差参数 $\varepsilon>0$，要求得到至多 $(1+\varepsilon)OPT$ 的可行解；对每个固定的误差参数，时间关于输入规模是多项式。

但时间可能形如 $n^{O(1/\varepsilon)}$，误差要求很小时仍可能不可用，不能理解成“误差随便调小且始终很快”。参见 Cesati 与 Trevisan 对PTAS效率的说明。

10.2 “参数较小”需要有明确的时间表达式

固定参数可解的一种典型形式是：

$$ T(n,k)=f(k)n^c $$

其中 c 不随参数 k 改变。例如 $2^k n^2$ 的指数代价集中在 k 上；当 k 很小时可能有用，但不表示 k 任意大时仍高效。仅仅说“对每个固定 k，$n^k$ 是多项式”还不满足上述形式的要求。

11. 竞争选址：一份好方案不等于一套必胜策略

11.1 规则里增加了一个会回应的对手

课件第31页给出一个带顶点权重的图。两名玩家轮流选择尚未被选、且不与任何已选顶点相邻的顶点，获得自己所选顶点的权重；没有合法位置时游戏结束。

问题是：给定阈值 B，后手是否有一种策略，无论先手怎样行动，都能得到至少 B 的总收益？

注意三个区别：

  • 选出的所有顶点合起来是独立集，但权重由实际选中它们的玩家分别获得。
  • 不再是一个人一次性挑选最佳集合，而是双方轮流行动。
  • 问的是“面对所有对手应对都能保证”，不是“存在某一局碰巧得到高分”。

11.2 先手不同，后手能拿到的收益也不同

先看一个补充的小例子：三个顶点连成路径 $u-v-w$，权重依次为2、9、2。

三顶点竞争选址博弈树：先手选中间会使后手无路可走，因此后手最坏保证收益为0

先手选择 后手还有什么可选 后手最终收益
u w 2
v 没有合法顶点 0
w u 2

因此，后手“某一局能得到2”是真的，但“保证至少得到2”是假的：先手可以直接选 v。

计算保证收益时，后手在自己的回合取最大值，先手的回合则考虑最不利于后手的选择，取最小值：

$$ \min(2,0,2)=0 $$

11.3 用递归核对课件中的10个顶点

课件使用一条10个顶点的路径，权重为：

10, 1, 5, 15, 5, 1, 5, 1, 15, 10

下面计算后手的最坏保证收益，不假定先手会配合后手得高分。

from functools import lru_cache


def second_player_guarantee(weights):
    n = len(weights)
    blocked = []
    for v in range(n):
        mask = 1 << v
        if v > 0:
            mask |= 1 << (v - 1)
        if v + 1 < n:
            mask |= 1 << (v + 1)
        blocked.append(mask)

    @lru_cache(None)
    def solve(available, second_turn):
        if available == 0:
            return 0
        outcomes = []
        for v, weight in enumerate(weights):
            if available & (1 << v):
                remaining = available & ~blocked[v]
                future = solve(remaining, not second_turn)
                outcomes.append(future + (weight if second_turn else 0))
        return max(outcomes) if second_turn else min(outcomes)

    return solve((1 << n) - 1, False)


assert second_player_guarantee([2, 9, 2]) == 0
weights = [10, 1, 5, 15, 5, 1, 5, 1, 15, 10]
print(second_player_guarantee(weights))  # 20

available 用二进制位表示哪些顶点仍然合法。选择 v 后，清除 v 及相邻顶点的位；只有后手选择时才把权重计入后手收益。递归返回的是从当前状态开始的未来保证收益，因此缓存不需要记录已经获得的分数。

结果为20，与课件中的“可以保证20，但不能保证25”一致。这个程序只核对路径图的小规模实例；它不是一般图竞争选址问题的高效求解器，状态数最坏仍可能随顶点数指数增长。

11.4 为什么课件会提到PSPACE

一般图上的竞争选址判定问题是PSPACE完全问题，课件在这里用它提示“策略问题”与“找一份候选方案”的不同；相关结论可参见 Kevin Wayne 的PSPACE讲义。

PSPACE关注多项式空间。搜索树可能有很多分支，但深度最多是顶点数量，可以按深度优先方式逐个探索，不需要同时保存整棵树。时间很长与空间很多是两种不同的资源消耗。

这不代表已经证明PSPACE严格大于NP；已知包含关系是 $\mathrm P\subseteq\mathrm{NP}\subseteq\mathrm{PSPACE}$，本篇不展开完整性归约与这些类之间的开放问题。

12. 把几个代表性问题放在一起复习

问题 选什么 约束 目标或提问 本讲的关键思路
区间调度 任务 时间不重叠 数量最多 最早结束贪心
带权区间调度 带权任务 时间不重叠 总权重最大 选与不选的动态规划
二分图匹配 边 端点不能重复 匹配边数最多 通过增广路重新安排
最大独立集 顶点 选中顶点之间无边 顶点数最多 一般图与特殊图要区分
竞争选址 轮流选顶点的策略 已选顶点及其邻居不可再选 后手能否保证阈值收益 最坏应对与策略树

建议按以下顺序继续学习：

  1. 补牢渐进符号、最坏情况、循环不变式与归纳证明。
  2. 从区间调度学习贪心的交换论证，再比较不同目标下的反例。
  3. 从带权区间调度学习状态、转移、前驱、表格和方案恢复。
  4. 学习图遍历、增广路与网络流，把匹配问题串起来。
  5. 在判定问题的框架下学习多项式归约、NP完全性。
  6. 根据需求继续学习近似、精确搜索、参数化和博弈策略问题。

遇到一个新题目，先写出“输入、可行解、目标、资源限制”，再问它是否有可以利用的结构，不要先按关键词硬套算法名字。

13. 巩固练习

以下是围绕本文知识补充的练习，并非课件布置的作业。建议先写出理由，再看下一节答案。

练习1：问题形式

“有没有总收益至少40的兼容方案？”“最大收益是多少？”“请返回实现最大收益的任务编号。”分别属于什么问题？只输出42，能否完整回答第三个问题？

练习2：端点约定

按本文模型，$[1,4)$ 与 $[4,6)$ 是否兼容？如果两场活动之间必须留1个时间单位准备，应把兼容条件怎样修改？

练习3：手动运行贪心

有四个任务 A：$[0,3)$，B：$[1,2)$，C：$[2,4)$，D：$[4,5)$。最早结束策略会选哪些任务？用它说明“最早开始”和“最早结束”不是同一种策略。

练习4：手动填动态规划表

给上题的 A、B、C、D 分别赋权10、4、4、3。按结束时间排序，写出各任务的前驱与最优值，再恢复一个最优方案。

练习5：恢复方案

如果带权区间调度只返回 $OPT(n)$，却没有输出所选任务，是否已经回答“最优解是什么”？回溯中选了任务 j 后，为什么要跳到 $p(j)$ 而不是继续到 $j-1$？

练习6：匹配中的重新安排

A可以去岗位1或2，B只能去岗位1。当前只有边 A-1。它是不是“极大但非最大”的匹配？写出增广后的匹配，并说明翻转后数量为什么增加1。

练习7：可行、极大与最大

回到第8节的7顶点图。集合 $\{2,7\}$ 是否为独立集、极大独立集、最大独立集？分别给出理由。

练习8：复杂性判断

判断并解释：NP表示“非多项式”；属于NP的问题都不属于P；一个指数时间算法证明了问题不存在多项式算法；检查一个大小为k的独立集，与检查它是不是最大独立集，是同一件事。

练习9：保证收益

三顶点路径的权重改为4、1、7。如果先手选左端，后手能得到多少？如果先手选中间呢？后手能否保证至少4？

练习10：方法保证

一个最大化问题的最优值为100。算法在一批测试上都得到90以上，能否据此声称它有2近似保证？若另一算法已经证明为2近似，它在任意合法实例上至少达到最优值的多少？

14. 参考答案与解析

练习1解析

依次是判定问题、最优值问题和最优解问题。第三个问题还需要返回可行且达到最优值的任务集合，仅返回42不够。

练习2解析

兼容，因为前一个任务在4结束，后一个从4开始。若准备时间为1，按时间顺序的两个任务 i、j 应满足 $f_i+1\le s_j$。原来的时间轴、前驱计算和实现都要相应修改。

练习3解析

按结束时间排序为 B、A、C、D。依次选 B、跳过与B冲突的A、选C、选D，得到3个任务。若先选最早开始的A，之后只能接D，得到2个任务。

练习4解析

j 任务 权重 p(j) 选当前任务 不选当前任务 OPT(j)
0 无 0 无 无 无 0
1 B 4 0 4 0 4
2 A 10 0 10 4 10
3 C 4 1 4+4=8 10 10
4 D 3 3 3+10=13 10 13

回溯：选择D，跳到第3行；跳过C，退到第2行；选择A，结束。因此最优方案是A、D，总权重13。D的前驱是C所在的前缀，但不要求最终方案一定包含C。

练习5解析

只返回最优值，还没有返回最优方案。选j后，编号大于 $p(j)$ 且小于j的任务都与j冲突，不能继续把它们当成候选前缀，因此要直接跳到 $p(j)$。

练习6解析

是。当前不能直接增加一条边：B-1与A-1共用岗位1，A-2与A-1共用A，因此它是极大的。但移除A-1，加入B-1、A-2，就得到2条匹配边，所以原匹配不是最大的。增广时增加2条、移除1条，净增1。

练习7解析

它是独立集，因为2与7之间没有边；是极大独立集，因为其余顶点都与2或7相邻，不能直接加入；不是最大独立集，因为 $\{1,4,5,6\}$ 是一个更大的独立集。

练习8解析

四句都不正确。NP是非确定性多项式时间的缩写，可用正实例证书验证来刻画；P包含在NP中。一个算法慢，不能排除存在别的快算法。检查候选集合是否达到k且无冲突，不要求排除所有更大的可行解，而验证最大性还涉及这个额外条件。

练习9解析

先手选左端，后手可以选右端，得到7；先手选中间，则后手没有合法顶点，得到0；先手选右端时，后手得到左端的4。最坏保证为 $\min(7,0,4)=0$，不能保证至少4。

练习10解析

不能。有限测试的表现不是对全部合法实例的近似保证。对已经证明为2近似的最大化算法，保证为 $ALG\ge OPT/2$；在最优值100的实例上至少得到50，但在最优值不同的实例上应按对应最优值计算，而不是统一保证50。

课件与补充资料

本文主要依据周毅（Yi Zhou）《Design and Analysis of Algorithms》第一讲 Introduction，原文件 01Introduction.pdf，共34页，署名按讲义首页记录。

  • 第15至20页：问题、问题形式、算法设计目标，以及算法与程序的关系。
  • 第21至25页：应用、问题复杂性与应对困难问题的方法。
  • 第27至32页：区间调度、带权调度、二分图匹配、独立集、竞争选址与方法汇总。

本文保留上述知识主线，对P、NP、NP完全和PTAS的简略表述作了必要区分；未复述课程管理信息。动态规划完整表格、Python程序、补充图例和习题解析为本文整理与扩展，并非逐页转录。

补充核对来源：Stephen Cook：P与NP问题说明、Clay：P与NP问题状态、Cesati与Trevisan：PTAS的效率、Kevin Wayne：PSPACE与竞争选址。