一片自留地 UCB CS170 L14-L22 简述

magicyang · 2021年01月15日 · 993 次阅读

从 L14 开始的内容,已经超出 leetcode 的范围。
L14-L22 介绍的是 Linear Programming(LP 线性规划) 和 NP 相关的内容。
在 LP 章节中,主要是介绍了:
1.MaxFlow 问题定义,Ford-Fulkerson(FF) 算法的实现
2.利用 FF 求解 min s-t cut
3.利用 LP 求解零合游戏
4.LP 的对偶性
5.利用 MaxFlow 求解 Bipartite Matching(BM 二分图最大匹配)

在 NP 的内容中,主要介绍了:
1.NP、P 问题的定义,什么是 np-complete
2.证明了从 CSAT->SAT->3SAT->HC(HAM-CYCLE)->IS(Independent Set) 是等价的 np-complete 问题。
3.解决 np-complete 问题的方法:
3.1 智能穷举(回溯和分支定界)
3.2 近似算法(主要介绍顶点覆盖并证明)
3.3 启发方法(HILL CLMBING/stimulated annealing)

ps:可以不看,我估计自己过两个月也得忘的干干净净。。。

暂无回复。
需要 登录 后方可回复, 如果你还没有账号请点击这里 注册