学习的这些方法更像是一种通用的解决问题的思路,而不是一种具体的算法。
将一个复杂的问题分解成若干个规模较小、 相互独立,但类型相同的子问题求解;然后再将各子问题的解组合成原始问题的一个完整答案,这样的问题求解策略就叫分治法。
- 找出简单的基线条件。
- 确定如何缩小问题的规模,使其符合基线条件。
- 快速排序
- 三分搜索算法
- 最优子结构性质 (自底向上)
- 重叠子问题性质
- 贪心法接近于最优解,但不是最优解
- 分治法自上而下,动态规划法自下而上
- 多段图问题、关键路径问题
- 每对结点间的最短路径
- 最长公共子序列
- 0/1背包问题
贪婪算法寻找局部最优解,企图以这种方式获得全局最优解。贪婪算法是易于实现、运行速度快的近似算法。
没有快速算法的问题。使用近似算法,快速找到NP完全问题的近似解。
搜索,也就是对状态空间进行枚举。通过穷尽所有的可能,来找到最优解,或者统计合法解的个数。
DFS 全称是 Depth First Search ,中文名是深度优先搜索,是一种用于遍历或搜索树或图的算法。所谓深度优先,就是说每次都尝试向更深的节点走。
该算法讲解时常常与 BFS 并列,但两者除了都能遍历图的联通块以外,用途完全不同,很少有能混用两种算法的情况。
在搜索算法中,该词常常指利用递归函数方便地实现暴力枚举的算法,与图论中的 DFS 算法有一定相似之处,但并不完全相同。
BFS 全称是 Breadth First Search ,中文名是宽度优先搜索,也叫广度优先搜索。
是图上最基础、最重要的搜索算法之一。所谓宽度优先。就是每次都尝试访问同一层的节点。 如果同一层都访问完了,再访问下一层。这样做的结果是,BFS 算法找到的路径是从起点开始的 最短 合法路径。换言之,这条路所包含的边数最小
回溯法是一种经常被用在深度深度优先搜索(DFS)和广度优先搜索(BFS)的技巧。
其本质是:走不通就回头。
- 构造空间树。
- 进行遍历。
- 如遇到边界条件,即不再向下搜索,转而搜索另一条链。
- 达到目标条件,输出结果。
- 内容: 用分治法实现一组无序序列的两路合并排序和快速排序。
- 要求:理解分治法的算法**,清楚两路合并排序和快速排序算法的基本原理和实施过程,能将输入的一组无序序列排列为有序序列后输出。比较不同排序算法的时间/空间复杂度和改进方法。
- 内容:用动态规划法实现求两序列的最长公共子序列
- 要求:掌握动态规划法的**,及动态规划法在实际中的应用;分析最长公共子序列的问题特征,选择算法策略并设计具体算法,编程实现两输入序列的比较,并输出它们的最长公共子序列
- leetcode: 1143. 最长公共子序列
- 内容:编程实现使用回溯法求解八皇后问题的所有可行解
- 要求:
- 写出相应的显式约束和隐式约束条件。
- 输出所有可行解。
- 分析算法的时间复杂度