【中文配音】斯坦福算法专项④｜最短路·NP完全·近似算法完整课·Roughgarden

Parts

1. P1 · [中文] 01 单源最短路再访：Dijkstra不够用的时候
2. P2 · [中文] 02 Bellman-Ford最优子结构：负权边怎么切子问题
3. P3 · [中文] 03 Bellman-Ford基本算法I：松弛操作从哪来
4. P4 · [中文] 04 Bellman-Ford基本算法II：实现与复杂度
5. P5 · [中文] 05 检测负权环：最短路何时没有答案
6. P6 · [中文] 06 Bellman-Ford空间优化：从平方到线性
7. P7 · [中文] 07 互联网路由I：Bellman-Ford如何驱动协议（可选）
8. P8 · [中文] 08 互联网路由II：为什么会数到无穷大（可选）
9. P9 · [中文] 09 全源最短路：问题定义与三种算法版图
10. P10 · [中文] 10 全源最短路最优子结构：中间点怎么切
11. P11 · [中文] 11 Floyd-Warshall算法：O(n³)动态规划一次算全图
12. P12 · [中文] 12 重加权技巧：负权图也能跑Dijkstra
13. P13 · [中文] 13 Johnson算法I：势函数与重加权
14. P14 · [中文] 14 Johnson算法II：全流程与复杂度
15. P15 · [中文] 15 多项式时间可解：P类问题长什么样
16. P16 · [中文] 16 归约与完备性：证明「一样难」的钥匙
17. P17 · [中文] 17 NP完全性定义与解读I：证书与验证
18. P18 · [中文] 18 NP完全性定义与解读II：为什么它是「最难」
19. P19 · [中文] 19 P vs NP：计算机科学最深的未解之谜
20. P20 · [中文] 20 NP完全不是死刑：求解策略全景
21. P21 · [中文] 21 顶点覆盖：从定义到暴力搜索
22. P22 · [中文] 22 更聪明的顶点覆盖搜索I：剪枝从哪下手
23. P23 · [中文] 23 更聪明的顶点覆盖搜索II：指数级加速
24. P24 · [中文] 24 旅行商问题TSP：暴力为什么炸
25. P25 · [中文] 25 TSP动态规划：Held-Karp比枚举快在哪
26. P26 · [中文] 26 贪心背包启发式：NP难也能先抓大的
27. P27 · [中文] 27 贪心背包分析I：50%近似比怎么证
28. P28 · [中文] 28 贪心背包分析II：最坏例子与紧性
29. P29 · [中文] 29 背包动态规划启发式：精度和速度怎么换
30. P30 · [中文] 30 再访背包动态规划：多项式时间近似方案
31. P31 · [中文] 31 动态规划启发式分析：误差从哪来
32. P32 · [中文] 32 最大割问题I：局部搜索的第一个靶子
33. P33 · [中文] 33 最大割问题II：为什么能保证50%最优
34. P34 · [中文] 34 局部搜索原理I：邻域、爬山与局部最优
35. P35 · [中文] 35 局部搜索原理II：怎么逃、怎么停
36. P36 · [中文] 36 2-SAT问题：局部搜索如何高效求解
37. P37 · [中文] 37 直线上的随机游走：为什么随机化有效
38. P38 · [中文] 38 Papadimitriou算法分析：2-SAT随机局部搜索
39. P39 · [中文] 39 稳定匹配：Gale-Shapley从理论到代码（可选）
40. P40 · [中文] 40 匹配、流与布雷斯悖论（可选）
41. P41 · [中文] 41 线性规划及其外（可选）
42. P42 · [中文] 42 终章：最短路、NP完全与实战策略