算法设计与分析期末
暴力法
回溯法---深度优先
解空间
各种可能的情况的各种组合
解空间结构：子集树，排列数
子集树：从集合中找出满足条件的子集时，相应的解空间
排列树：找到满足条件的排列时，相应的解空间
剪枝函数：约束函数，限界函数
问题的解空间至少包含一个最优解
回溯法是一种带有 系统性 和 跳跃性 的搜索算法
分支限界法---广度优先
常见的两种分支限界法：队列式（FIFO）分枝限界法，优先队列式分枝限界法
分治法
能解决的问题的特征：
- 可分解性
- 可合并性
- 独立性（不必须）
步骤：分解-求解子问题-合并
贪心法
分步求解，每一步的局部最优解”算是“ “凑合下” 整体的最优解。在某种情况下，凑巧能得到真正的最优解。
能解决的问题的特征：
- 最优子结构：问题的最优解包含其子问题的最优解
- 贪心选择性质（局部最优选择）（基本要素）
动态规划法
保存子问题的最优解，利用原问题和子问题间的递推公式，求得原问题的最优解。
能解决的问题的特征：
- 最优子结构：问题的最优解包含其子问题的最优解
- 重叠子问题（最显著特征）：问题被分解后的子问题间不是独立的，其中一些子问题在后面的决策中可能被多次重复使用
- 无后效性
步骤：问题结构分析-递推关系建立-自底向上计算-最优方案跟踪