算法策略

贪心算法

一个贪心算法总是做出当前最好的选择,也就是说,它期望通过局部最优选择从而得到全局最优的解决方案。

  • 做出选择 不可反悔
  • 可能得不到最优解
  • 贪心策略决定算法好坏

确定贪心策略 选择当前看上去最好的方案

一步一步得到局部最优解

将所有局部最优解合并称为一个原来问题的最优解

  • 冒泡排序就使用了贪心算法

原则

  • 贪心原则
    • 所谓贪心选择性质是指原问题的整体最优解可以通过一系列局部最优的选择得到
  • 最优子结构

    • 当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质
  • 背包问题

选择一个最好的贪心策略

物品可分割称为背包问题 物品不可分割称为0-1背包问题

  • 会议安排问题
  • 最短路径问题
  • 哈夫曼编码
  • 最小生成树

分治法

其本质就是将一个大规模的问题分解为若干个规模较小的相同子问题,分而治之

  • 递归

分支算法要素

  • 原问题可以分解为若干个规模较小的相同子问题
  • 子问题相互独立
  • 子问题解可以合并为原问题的解

  • 二分查找
  • 归并排序
  • 快速排序
  • 大整数乘法

动态规划

基础

动态规划的思想类似于分治法

不过动态规划是从最小子问题求起 将小问题的解存储起来

求解大问题时 如果需要用到小问题的解 直接使用即可 无需再重复计算

要素

  • 最优子结构
    • 问题的最优解包含其子问题的最优解
  • 子问题重叠
    • 不是必要条件 但是是动态规划的优势

  • 兔子序列
  • 最长公共子串

回溯法

回溯法是一种选优搜索法,按照选优条件深度优先搜索,以达到目标。当搜索到某一步时,发现原先选择并不是最优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术称为回溯法,而满足回溯条件的某个状态称为“回溯点”。

要素

  • 解空间
    • 由所有可能解组成的空间
    • 将这些解按一定结构组织起来:解空间树
  • 隐约束
    • 不满足隐元素的分支无需搜索 直接剪掉 也称为剪枝函数

  • 0-1背包
  • 最大图
  • 地图着色
  • n皇后

分支限界法

  • 广度优先

回溯法找出所有解

分支限界法找出一个接

回溯法深度优先 分支限界法广度优先

回溯法搜索一次生成一个孩子节点 分支限界法一次生成所有节点

线性规划网络流

解决

  • 确定决策变量
    • 哪些变量对模板有影响
  • 确定目标函数
    • 含有决策变量的线性函数
  • 找出约束条件
    • 将对决策变量的约束表示为方程或者不等式
  • 求最优解

results matching " "

No results matching " "

results matching " "

No results matching " "