问题求解(三) Open Topic 15 笔记
OT:在独立、覆盖和支配的基础上,形成了很多扩展的优化问题,例如最小权完美匹配问题(Minimum-Weight Perfect Matching)、最小连通支配集问题等,请调研至少2种问题(其中至多1种来自上述例子,二分图最大匹配问题等仅限制原始问题输入的问题不在调研范围内),讨论适用场景,形式化描述问题,为每种问题结合例子介绍至少1种算法的设计与分析。
OT:在独立、覆盖和支配的基础上,形成了很多扩展的优化问题,例如最小权完美匹配问题(Minimum-Weight Perfect Matching)、最小连通支配集问题等,请调研至少2种问题(其中至多1种来自上述例子,二分图最大匹配问题等仅限制原始问题输入的问题不在调研范围内),讨论适用场景,形式化描述问题,为每种问题结合例子介绍至少1种算法的设计与分析。
OT:除MS和MAX-CUT外,近似算法还可用于解决其它问题,例如SCP(JH算法4.3.2.11)、SKP(JH算法4.3.4.1和4.3.4.2)等,请调研至少2种近似算法(其中至多1种来自上述例子,图上的优化问题不在调研范围内),结合例子介绍算法的设计与分析,重点阐述近似比的证明过程。
OT:除IP外,广义的“松弛-修正”思想还可用于解决其它问题,例如TSP的松弛修正算法、最短超串问题的松弛修正算法等,请调研至少2种算法(其中至多1种来自上述例子),结合例子介绍算法的设计与分析,重点阐述其中的“松弛-修正”思想。
OT:除MAX-SAT和TSP外,分支定界和局部搜索算法还可用于解决其它问题,请为每种算法调研至少1种可以解决的问题,结合例子介绍算法的设计与分析。
OT:除福特-法尔克森算法外,最大流问题还有很多其它算法,例如 Edmonds-Karp 算法、Dinitz 算法、Push-Relabel 算法等,请调研至少2种算法(其中至多1种来自上述例子),结合例子介绍算法的设计与分析,与福特-法尔克森算法比较异同并分析优劣。
OT:请调研并介绍图灵机及其至少 2 种等价模型,讨论图灵机、P、NP之间的关系。
OT:请调研教材中未介绍过的至少2种判定问题和2种优化问题(不能是相互对应版本,也不能是教材中介绍过的问题的对应版本),讨论适用场景,用教材中的方法形式化描述问题。
OT:最小生成树问题有很多相关问题,例如 Steiner tree、k-MST、MBST 等,请调研至少 2 种问题(其中至多 1 种来自上述例子,欧氏最小生成树问题等仅限制原始问题输入的问题不在调研范围内),讨论适用场景,形式化描述问题并概述现有解决方案。
A memory leak issue which might be confusing for students struggling with ICS Project (aka, PA) of Nanjing University.