Uni Reading List
学习指南 /

算法推理：选教材，并证明优化答案

先说明模型、正确性和资源代价，再选择算法。本路线区分免费证明教材、广泛的伪代码参考与偏重实际建模的伴读；选一本主线，遇到明确问题再补读另一种解释，不把买齐三本等同于学会设计。

课程专题: 算法

学习路线与例题编辑责任：University Reading List 编辑项目。 编辑与选书方法 · 来源核验日期:

下载空白任务单（Markdown） ↓

适用范围与编辑责任

适合已学基础编程、递归、数据结构和离散数学的本科读者。Erickson明确假定这些准备，免费并不等于零基础编程书。下面的排程数据、任务与答案由本站创作，不是出版社原题或工作场景实证。

选择你的起点

会编程，但难以解释正确性

能使用归纳法和基本数据结构后，以Erickson免费主线练习；先写不变量或递推式，再翻译成代码。

课程指定CLRS

按第四版指定章节与伪代码约定学习。先选设计章节，不把全书的广度误当作必须逐页读完的任务。

难以认出问题模型

用Skiena整理问题类型和候选方法，再回到证明型解释；实现故事不能自动证明算法正确。

三本书如何取舍

Algorithms

Jeff Erickson · 版次: 1 · 2019

免费证明与设计主线

适合何时选择
已有归纳基础，愿意自己写反例、论证和递推式。
何时另选路线
还需要首次学习栈、散列表或编程语法。
建议阅读范围
2019版第1–4章，然后选择第5–8章的图论内容。
局限与取舍
作者明确列出省略的先修数据结构，也不应读者请求提供练习解答。免费正文不等于公开答案库。

选书前试做

读第3–4章后，用下方五任务说明最早结束规则为何可能不能最大化报酬。

检查标准: 列出贪心方案与一个报酬更高的可行方案，核对任务ID；不能用任务个数替代报酬目标。

官方免费阅读 ↗

书目信息与获取方式 →

算法导论

Thomas H. Cormen et al. · 版次: 4 · 2022

覆盖面广的第四版参考

适合何时选择
课程指定CLRS，或需要跨方法一致的伪代码解释。
何时另选路线
只需短导论，且尚不能选择阅读范围或确认先修。
建议阅读范围
在第四版中定位Dynamic Programming和Greedy Algorithms，按需回看分析与数据结构；以手中版本目录为准。
局限与取舍
2022年所选精装ISBN为9780262046305。教员受限资料不是自学者的公开解答权利，纸本标识也不包含所有数字产品。

选书前试做

先用文字定义一个最优化子问题，再说明最优后续决策可以忽略哪些信息。

检查标准: 状态定义应决定备选项和基例；认得公式外形不等于证明最优子结构。

书目信息与获取方式 →

算法设计手册

Steven S. Skiena · 版次: 3 · 2020

建模与实现伴读

适合何时选择
需要把应用叙述转成组合问题，并比较实现方向。
何时另选路线
希望仅凭问题目录或社区答案替代证明。
建议阅读范围
第三版实用设计部分，尤其第10章动态规划；明确模型后再查问题目录。
局限与取舍
作者站点的解答Wiki明确不保证社区答案正确。把答案当成待检查的论证，而不是裁决。

选书前试做

将同一预约问题写成生活叙述与带权区间模型，列明兼容条件和目标。

检查标准: 每个现实条件要么进入模型，要么明确排除；熟悉的问题名称不能让约束凭空消失。

书目信息与获取方式 →

检查先修准备

可行与最优有什么不同？

可行表示满足全部约束；最优需要与所有可行候选比较目标值。一个看起来不错的方案不能代替这两类一般论证。

递推式为何需要归纳思路？

它把已解的小问题与当前最优解连接起来，必须说明分类覆盖所有可能的最优解。

时间复杂度要交代什么？

定义n、输入表示与所数操作；排序、前驱计算、填表和复原分别计成本。

六步学习与具体成果

勾选用于自我记录，不是成绩评定；标记不会发送给本站。

  1. 先写模型

    建议阅读范围: Erickson第0章与Skiena的建模讨论。

    动手产出: 写清固定起止、半开区间、报酬、单资源及报酬和目标。

    检查标准: 基本模型允许一个任务结束时立即开始下一个；没有暗含路程或准备时间。

  2. 反驳未经证明的捷径

    建议阅读范围: Erickson第4章及CLRS的贪心讨论。

    动手产出: 按最早结束运行一次，再找报酬更高的可行反例。

    检查标准: 展示所选ID。反例否定特定普遍主张，不意味着所有贪心法都失败。

  3. 定义状态

    建议阅读范围: Erickson第3章与CLRS动态规划章节。

    动手产出: 按结束排序，用完整句子解释V(j)、p(j)。

    检查标准: V(j)限于前j个任务；p(j)是与j兼容的最后一个前任务，没有则为0。

  4. 计算并说明表格

    建议阅读范围: 同一动态规划范围。

    动手产出: 每行比较两个选项，记录前驱并复原方案。

    检查标准: 最优解要么不含j，要么包含j及兼容前缀的最优解；说明为何分类完整。

  5. 改变一个约束

    建议阅读范围: Skiena第10章与后面的变式。

    动手产出: 加入规定的准备间隔，重算兼容性后再使用递推式。

    检查标准: 即使报酬和递推外形不变，p数组改变也可能使旧解不再可行。

  6. 提交可审查的结果

    建议阅读范围: 回到最薄弱步骤对应的教材。

    动手产出: 提交模型、反例、表格、复原、复杂度及边界检验。

    检查标准: 另一位读者能重算目标值和可行性；给一个小程序计时不是渐近分析。

原创例题与解析

原创例题：最早结束并不最大化报酬

五个虚构任务的(开始,结束,报酬)为a=(0,3,5)、b=(3,5,4)、c=(0,5,12)、d=(5,7,3)、e=(4,8,11)。一份资源只能执行不重叠任务。求最大报酬，并与最早结束法比较。

前提假设

采用半开区间，允许结束后立即接续；时刻固定、任务不可拆分、非负报酬相加。无准备间隔、路程或不确定性。同结束时刻按b在c前排序，影响表的次序而非最优值。

  1. 最早结束依次选a、b、d，得5+4+3=12；可行的a、e得16，所以该贪心规则不能一般地解决带权目标。
  2. 按a、b、c、d、e排序，前驱p=[0,1,0,3,1]。设V(0)=0，V(j)=max(V(j−1),reward(j)+V(p(j)))，分别对应不选和选j。
  3. 表为V=[0,5,9,12,15,16]。最后一行选择e，回到前驱a，报酬11+5=16。
  4. 排序与二分查前驱可用O(n log n)，填表、复原用O(n)，存储O(n)。五任务的检验与包含/排除的一般论证应分开。

答案与解释

最大值为16，由a与e取得；三任务贪心方案得12。最大化个数与最大化报酬是不同目标。

检验结果

独立枚举全部32个子集，剔除不兼容者，应得到相同最优值。复原后仍须检查端点，不能只相信表里的数。

改变假设，再做一题

变式：任务之间必须留出间隔

保留五任务与报酬，但相邻两个被选任务之间至少留2个时间单位。最后一个任务之后无须间隔，起止时刻不能移动。重求最优值。

  1. 兼容条件改为finish(i)+2≤start(j)，同序p=[0,0,0,1,0]。a能接d，却不能接b或e。
  2. 新表为[0,5,5,12,12,12]。只选c得12；旧a、e因3+2>4而不可行。

答案与解释

新最优值为12，选择c。保留递推式，重建兼容性数据；从旧报酬统一减一笔费用会变成另一模型。

检验结果

用新兼容条件重枚举。单个任务不需末尾间隔；原最优值是放松约束模型的上界，并非这里的可行答案。

常见误区

把伪代码当证明

程序在此例返回正确值，不代表对所有输入正确。有限测试和一般论证各有作用。

用问题名代替模型

准备时间等条件可能破坏熟悉的归约，选择算法前要说明排除了什么。

复杂度只数一部分

不能漏掉排序或二次前驱扫描，再称整个实现线性；上界要对应实际实现。

进入下一阶段之前

  • 能明确目标与每一项兼容规则。
  • 能说明递推并复原可行方案。
  • 能改变一个假设，指出必须改变的数据或论证。

来源与版次核验

来源核验日期:

这些是本站建议的学习活动，并非大学官方作业，也不代表对每本书逐页通读。

编辑与选书方法 →