0%

数据结构与算法学习(三):第三阶段知识总结

1. 动态规划概述

  1. 概念

    • 一个模型(多阶段决策最优解模型

      1. 解决问题的过程,需要经历多个决策阶段
      2. 每个决策阶段都对应着一组状态
      3. 寻找一组决策序列,经过这组决策序列,能够产生最终期望求解的最优值
    • 三个特征

      1. 最优子结构

        • 通过子问题的最优解,推导出问题的最优解
      2. 无后效性

        1. 在推导后面阶段的状态的时候,只关心前面阶段的状态值,不关心是怎么一步一步推导出来的
        2. 某阶段状态一旦确定,就不受之后阶段的决策影响
      3. 重复子问题

        • 不同的决策序列,到达某个相同的阶段时,可能会产生重复的状态
  2. 特点

    1. 从最简单的问题开始,一点一点把问题复杂起来,在这个过程中寻找复杂问题是如何依赖简单问题的
    2. 需要记忆前面简单问题的解,然后用简单问题的解解决后面复杂问题的解
  3. 和分治的区别

    1. 分治是自顶向下解决问题
    2. 动态规划是自底向上解决问题
  4. 解题思路

    1. 状态转移表法:回溯算法实现-定义状态-画递归树-找重复子问题-画状态转移表-根据递推关系填表-将填表过程翻译成代码
    2. 状态方程法:找最优子结构-写状态转移方程-将状态转移方程翻译成代码

2. 贪心算法概述

  1. 概念

    • 每一步选择都采取当前状态下最有利的选择,从而希望结果是最优的
  2. 应用

    1. 适用的场景比较有限,更多的是指导设计基础算法
    2. 经典应用有:霍夫曼编码、Prim 和 Kruskal 最小生成树算法Dijkstra 单源最短路径算法
  3. 解题步骤

    1. 当遇到问题的时候,首先要联想到贪心算法
    2. 尝试看这个问题是否可以用贪心算法解决
    3. 举几个例子看贪心算法产生的结果是否是最优的

3. 分治算法概述

  1. 概念

    1. 将原问题划分成 n 个规模较小、结构与原问题相似的子问题
    2. 递归解决这些子问题,然后再合并其结果,得到原问题的解
  2. 和递归的区别

    1. 分治算法是一种处理问题的思想
    2. 递归时一种编程技巧
    3. 分治算法一般都比较适合用递归来实现
  3. 实现

    1. 分解:将原问题分解为一系列子问题
    2. 解决:递归求解各个子问题,若子问题足够小,则直接求解
    3. 合并:将子问题的结果合并成原问题
  4. 应用条件

    1. 原问题与分解成的小问题具有相同的模式
    2. 原问题分解成的子问题可以独立求解,子问题之间没有相关性
    3. 具有分解终止条件
    4. 可以将子问题合并成原问题

4. 回溯算法概述

  1. 概念

    1. 类似枚举搜索,枚举所有解,找到满足期望的解
    2. 把问题求解的过程分为多个阶段,每个阶段都会面对一个岔路口,先随意选一条路走
    3. 当发现这条路走不通的时候(不符合期望的解),就回退到上一个岔路口,另选一种走法
  2. 实现

    • 递归
  3. 和深度优先的区别

    1. 深度优先遍历的目的是“遍历”,本质是无序的
    2. 回溯的目的是“求解过程”,本质是有序的
  4. 应用

    • 深度优先搜索
    • 八皇后
    • 0-1 背包
    • 图的着色
    • 旅行商问题
    • 数独
    • 全排列
    • 正则表达式匹配

5. 跳表概述

  1. 概念

    • 链表加多级索引结构
  2. 优点

    1. 支持快速插入、删除、查找操作,写起来不复杂,时间复杂度是 O(logn)
    2. 实现非常灵活,可以通过改变索引构建策略,有效平衡执行效率和内存消耗
    3. 为了代码的简单、易读,会用跳表替代红黑树

6. 搜索概述

  1. 图上的搜索算法

    • 在图中找出从一个顶点出发,到另一个顶点的路径
  2. Dijkstra 算法

    • 概念

      1. 计算一个节点到其他所有节点的最短路径
      2. 一种单源最短路劲算法
    • 复杂度

      • 时间复杂度是 O(E*logV)
  3. A* 算法

    • 和 Dijkstra 算法代码的 3 点区别
      1. 优先级队列构建的方式不同
      2. A* 算法在更新顶点 dist 值的时候,会同步更新 f 值
      3. 循环结束的条件不一样
-------------------- 本文结束感谢您的阅读 --------------------