算法设计
分治
- 分解
- 求解
- 合并
动态规划
- 找出最优解的性质
- 递归定义最优解的值
- 自地向上计算出最优值
- 根据计算最优值时得到的学习，构造一个最优解
贪心
- 根据当前已有的信息作出选择
- 不能改变已作出的选择
回溯
- 按照深度优先策略搜索解空间树
- 找出满足约束条件的所有解
分支限界
- 按照广度优先搜索解空间树
- 找出满足约束条件的一个解
- 或找出满足约束条件的所有解中的最优解
概率
- 输入原问题，随机数序列
- 执行某些步骤可以随即选择下一步如何进行
- 允许结果以较小概率出现错误
数值概率
- 近似解
Monte Carlo
- 精确解
- 无法有效判断解是否正确
Las Vegas
- 正确题
- 对相同实例问题反复求解多次可使求解失效概率任意小
Sherwood
- 一个正确解
近似
- 近似最优解
- 放弃最优解