Last updated by Yarco on Tue, 12 Feb 2019 06:25:45 +0000
#### 教室调度问题 #### 背包问题
局部最优解 得到 全局最优解 的近似值.
### NP 完全问题
元素较少时算法的运行速度非常快,但随着元素数量的增加,速度会变得非常慢。
涉及“所有组合”的问题通常是 NP 完全问题。
不能将问题分成小问题,必须考虑各种可能的情况。这可能是 NP 完全问题。
如果问题涉及序列(如旅行商问题中的城市序列)且难以解决,它可能就是 NP 完全问题。
如果问题涉及集合(如广播台集合)且难以解决,它可能就是 NP 完全问题。
如果问题可转换为集合覆盖问题或旅行商问题,那它肯定是NP完全问题。 (个人认为 指的是 当增加一个条件时, 将影响所有可能的已知答案 -- 点~全局 关联时, 是NP问题)
(个人思考, 适合的情况属于)
### 最长公共子串 #### 最长公共子序列