算法导论-2025fa-wzx最后一课
五大常用算法总结。
分治法
- 基本思想。
- 将一个问题，分解为多个子问题，递归的去解子问题，最终合并为问题的解。
- 适用情况。
1.问题分解为小问题后容易解决。
2.分解后的小问题解可以合并为原问题的解。
3.小问题之间互相独立。 - 实例。
0. 二分查找。
1. 快速排序。
2. 合并排序。
3. 大整数乘法。
4. 循环赛日程表。
动态划分算法
- 基本思想。
- 将问题分解为多个子问题（阶段），按顺序求解，前一个问题的解为后一个问题提供信息。
- 适用情况。
1.最优化原理：问题的最优解所包含的子问题的解也是最优的，即最优子结构。
2.无后效性：某个状态一旦确定，就不受以后决策的影响。
3.有重叠子问题。 - 说明。
- 递推关系是从小的问题开始到较大问题的转化，往往可以用递归来实现，可以利用之前产生的子问题的解来减少重复的计算。
贪心算法
- 基本思想。
- 不从总体最优考虑，仅考虑局部最优解，问题必须具备后无效性。
- 步骤。
- 将问题分解为多个子问题。
- 得到问题的局部最优解。
- 合并子问题的局部最优解。
- 适用情况。
1.局部最优策略能导致全局最优解。
2.子问题后无效性。
回溯法
- 基本思想。
- 选优搜索法，走不通就退回重选，按照深度优先搜索的策略，从根节点出发，深度搜索解空间。
- 步骤。
- 确定解空间。
- 确定节点的扩展搜索规则。
- 深度优先方式搜索解空间，用剪枝法避免无效搜索。
分支界限法
- 基本思想。
- 与回溯法类似，也是在解空间里搜索解得算法，不同点是，回溯法一般寻找所有解，分支界限法搜索一个解或者最优解。
- 分支：广度优先策略或者最小耗费（最大效益）优先。
- 分支搜索方式：FIFO、LIFO、优先队列式、分支界限搜索算法。
课程总结
一、回溯法与分支限界
回溯法:
- 本质：穷举法/枚举法
- 核心思想：为提高效率，需要合理组织解空间
- 解空间组织：
- 子集树
- 排列树
- 搜索策略：深度优先搜索（DFS）
- 剪枝函数：
- 约束函数：控制左子树（满足约束条件才能进入）
- 限界函数：控制右子树（必须得到更好或同样好的解才能进入）
- 适用场景：寻找所有最优解（如图的着色问题、n皇后问题、货郎担问题、最大团问题等）
分支限界法:
- 解空间组织：与回溯法相同（子集树或排列树）
- 搜索策略：广度优先搜索（BFS）或最大效益优先
- 实现方式：队列式、优先队列式（实际中多采用优先队列式）
- 适用场景：寻找一个最优解（以最快速度找到最优解即停止）
两者区别:
- 回溯法：寻找所有最优解
- 分支限界：寻找一个最优解
二、动态规划
前提条件:
- 最优子结构性质：原问题的解包含子问题的最优解
- 子问题重叠性质：原问题可分解成多个相互重叠的子问题
核心思想:
- 自顶向下分析：建立递推表达式
- 自底向上求解：从小规模问题逐渐扩大到原问题规模
特点:
- 保证全局最优：考虑了所有情况
- 示例：矩阵连乘问题求n个矩阵的最优解时，同时得到n-1个、n-2个…矩阵的最优解
三、贪心算法
核心思想:
- 不从总体考虑最优，仅考虑局部最优解
- 多阶段决策，每步选择当前最优
全局最优保证:
- 需要证明策略具有贪心选择性质
与动态规划的关系:
- 动态规划能求解的问题范围更广
- 能用贪心解决的问题一定能用动态规划解决（反之不成立）
- 能用贪心且保证全局最优时，优先使用贪心（更简单）
- 典型区分：背包问题（可用贪心）vs 0-1背包问题（需用动态规划）
四、分治与递归
适用条件:
- 子问题与原问题相同
- 子问题之间相互独立
核心思想:
- 将大规模问题分解为小规模问题
- 递归求解子问题
- 合并子问题的解
示例：搜索、排序等算法
五、算法复杂性分析
复杂性类型:
- 时间复杂性
- 空间复杂性
（本课程重点关注时间复杂性）
影响因素:
- 算法本身
- 输入数据
- 问题规模
分析方法:
- 渐进性态分析
- 递推表达式推导
- 大O表示法
分析要素（递归算法）
- 分解成几个子问题
- 每个子问题是原问题规模的多少
- 分解和合并的额外代价
题目形式:
- 复杂性分析
- 具体问题求解：
- 写出解题思路
- 可用伪代码或文字描述（第一步、第二步、第三步…）
- 关键是讲清楚思路
- 算法选择：根据题目要求选择合适方法（贪心/动态规划等）
- 解空间绘制：
- 回溯或分支限界的解空间类型
- 遍历过程中的剪枝结果（重点掌握）
六、文字记录
比方说 图的着色问题,比方说 n皇后问题 对吧?货郎担问题他可能他的最优解,比如最大团问题,对吧?他的最优解可能不是一个,它有很多个,他有很多个。
那么这个回溯法一般用于去寻找所有的解,你要把最优解都给我找出来。
当然在这个过程中,我用剪枝策略,我左减右减,那么分支限界他一般来说我就找一个解就行了,我就想以最快的速度,采用优先队列的方式对吧,你以最快的速度导向我,引导着我去找着一个最优解,我什么时候到叶子,什么时候我就停了，这是我们说分支限界和回溯。有的教材上叫做分支界限,有的教材上叫分支限界,它指的是同一类方法,这是我们说回溯和分支限界这两种方法求解问题的时候,大概就是这个思路。
其实相对而言,就这两种方法求解问题的时候,其实是比较简单的,因为你你想一下,你就,实际上你就是你确定是什么树,然后你遍历就完事了。
那么除此之外，那么我们还讲了两类方法，用来做多步骤决策的。
一个是什么呢?动态规划,一个是贪心,我们讲到了动态规划和贪心他们都是解决多阶段决策问题,都是解决多阶段决策问题。
那么动态规划,动态规划我们要去求解这个问题的时候,求解这个问题的时候,一一讲到这个动态,一讲到动态规划,就是求解这个问题。
他有它有两个前提，它有两个前提，一个是什么呢？就是最优子结构性质。
你这个问题要具有最优子结构性质。
什么叫最优子结构性质?就是就是原问题的解,里面包含有子问题的最优解,我们称为最优子结构性质。
另外一个子问题重叠性质,就是我把它原问题分解成很多小的相互重叠的那些子问题,你把这些子问题都求完了,你自然能得到原问题的解,这是我们说动态规划求动态规划这一章我们花费的时间很多,因为这一章它很难,它很难,讲到动态规划,我们就必须要讲两句话两句话,哪两句话自顶向下的去分析,自底向上的去求解。
对吧，你自顶向下去分析的过程，实际上就是你要建立一个递推表达式的过程，然后有了这个表达式，那我们就可以自底向下，自底向上去求。
嗯，就是我们先从小规模的对吧求出它的解规模逐渐变大,逐渐变大，这就是什么？这就是我们说的动态规划。
动态规划，它求解问题就什么呢？就是说它一定能够保证是全局最优的因为他把所有的情况都考虑了一遍。
你可以想一下,咱讲的那个动态规划,那些例子,他把所有情况都考虑了一遍。
你比如像矩阵连乘,对吧?两个矩阵连乘,三个矩阵连乘,三个矩阵连乘你从不同的位置开始,到不同的位置结束,它是一个什么样的最优解,他都知道,所以我们说你,比如说矩阵连乘,你要是求n个矩阵连乘它的最优解,实际上他不但知道n个矩阵连乘的最优解,他还知道n减一个矩阵连乘的最优解,他还知道n减二个矩阵连乘的最优解,对吧。
所以我们说什么呢?为什么我们说原问题的解里面包含有子问题的最优解,这是就是动态规划,动态规划。
而我们讲的贪心,他也是一个多步骤决策,也是个多步骤决策,只不过是什么呢?你看他不是从总体上去考虑最优,他仅仅去考虑局部最优解,局部最优解,嗯,也是一样的,就是比如,我把这个就是问题分成一个多阶段嘛,它分成多阶段,嗯,就是我每一个步骤我都去选择当前最优的,当前最优的,就这么一层一层一层的去讲。
我们当时讲个贪心的时候，我们也给大家讲说贪心，贪心，它并不能保证他一定得到全局最优解，对吧？你说我怎么才能够保证他得到全局最优解呢？你必须有这样的话做保证就是你证明，你要能证明就是这个问题，就是你的这个策略。
嗯，它具有什么贪心选择性质有贪心选择性质这样的话，我就能保证它是全局最优的。
刚才我们区分的是回溯跟分支限界,现在我们再来区分一下动态规划跟贪心。
实际上在前面的时候,我们已经区分过动态规划跟贪心了,就这两个,这两个他们之间的关系,实际上我当时不是给你画个图吗?对吧,我给你画个图,就类似这样一幅图,一个大的最外面这个最外面,这个是什么?动态规划对吧?最里面这个是贪心,也就是说,也就是说就是动态规划,它能求解的问题的范围更大。
嗯，就是在这个范围内有一部分问题是用能用贪心做的。
那么当然你也体会了，贪心，他简单对吧？简单。
如果说他能用贪心做,又能保证得到全局最优解,那我肯定要用贪心。
所以我们讲过那样的话，什么话呢？我们说能用动态规划求解的问题，不一定能用贪心来做，但是反过来，能用贪心做的，他一定能用动态规划做。
这就是你要知道动态规划跟贪心他们间的关系就是你,尤其你要去区分背包问题，跟0-1背包问题对吧?跟0-1背包问题就是我们说普通的背包问题,你用贪心，普通的背包问题跟用动态规划，它有什么样的区别,我们当时的时候就专门给大家花了很多的这种精力去去讲,去讲这是什么,这是我们说的贪心的问题和动态规划的问题,它都是用来解决这种多阶段决策多阶段决策的你像这些都是用来干什么呢?找最优解的找最优解的就是你要找个最优的。
他一般来说,一般来说他要他一旦问你,问你这种类似于说我要找个最优的基本上基本上来说你就他一般来说不太会直接用分治与递归这种方式,分治与递归这种方式。
好,回过头来来,咱再来看咱最早介绍的这种就是第一章分治与递归。
分治与递归。
那么当时讲分治与递归的时候,我们特别强调的两句话,两句话就是你当你求解一个问题它比较难的时候,对吧,你把一个大规模的问题变成一个小规模的问题,就是我们当时讲了两句话,第一句话是这些小规模的子问题必须原问,问题与原问题相同,对吧,根源问题相同,这是这是一个。
另外一个就是我们说这些子问题之间他们要什么呢?他们要独立,对吧?要独立,要相互独立,相互独立,这样的话,就可以采用这种递归的方式去求解。
采用递归的方式去求解,这个地方给你举了很多的这个例子,你看这些例子,关于搜索的,关于排序的,关于排序的等等等等,我要讲的是我们说的五大问题,大概要说的就这么多,当然我们还有什么?还有第一章,就是那个概述,对吧,算法导论那个概述,那个概述那一章,其实嗯,就是就是要给你一个什么概念呢?就是说这个算法,它实际上它是有优劣的,算法是有优劣的。
那么我怎么样去评判一个算法的优劣呢？复杂性对吧？它的复杂性呢？又分为什么呢？时间复杂性和空间复杂性。
我们这个教材更多的关注的是什么呢？时间复杂性时间复杂性。
这个时间复杂性怎么去评价呢？跟很多因素有关系，对吧？你比如说跟他是什么算法，它的输入又是跟它问题的规模它都有关系。
那你要想准确的去评价一个算法的复杂性很难,怎么办呢?我们一般来说都是去分析它的渐进性态,也就是他的解,他的解我们在上课的时候一直给大家强调说你要有这样的技能,什么技能?就比方说,我给你一个这种递推的表达式,对吧?那你要能够去推导出推导出这个算法,它的复杂性大o表示法,它的复杂性的最后的值,对吧,它是n乘logn还是n方,还是一个什么样的结果?嗯,就是我们在讲的过程中专门给你讲,你就要找着那三个要素,对吧?三个要素,它分成了几个子问题。
嗯,然后呢?这每一个子问题是原问题规模的多少你为了分解和合并,你又花费了什么样额外的代价,你要把这三个要素搞清楚,那要做搞清楚,然后这样的话就有助于去什么去,分析分析好了,我们要说的什么呢?关于内容,我就总结这么多分这么多好后面再说什么呢?就是实验当时说的截止到多少号20号,是吧几号我忘了,反正你就按照那个,你就按照那个时间点来就行了,我已经说过了,
就是你在那个时间点之前,在那个时间点之前,你要把相应的个成果都交上去,然后我也说了,我们不需要去交纸质版的实验报告,实验报告,但是在系统上你要按要求去提交了,这个是作为平时成绩的一部分,平时成绩的一部分,那么这是关于实验,关于实验那么关于考试,关于考试,时间已经说过了,就是12月28号,对吧,周五的晚上,周五的晚上,那么这个题我们总共是七道大题,总共是七道大题,嗯,这个这个基本上基本上都很稳定,每年都这样的,就七道大题,你那那那你就可以数了,你就可以数了。
我们总共学了几章是不是总共学了六章对吧学了六章总共七道大题对吧,那应该是每一章都会有每一章都会有,每章都会有,就是有一些问题,我在讲课的过程中,我特别给你强调,对吧,就给你强调,就我们明确一点,就是说我们的课上就是说讲了什么样的范围,它就是什么样的范围,它就是什么样的范围,就是我比如说这教材上内容很多,我我们没有讲的地方,就是不考的就不考的,你也不用去担心,你比方说那个叫什么,什么最小生成树单源最短路径,对吧,我又没讲,没讲我说明不考,不考,那么这个我们已经说了,就是说总共是七个题。
那你说他这个题的形式是什么样子的，形式是什么样子？实际上以前的时候给你做过练习，那些给你截过一些图，那些图就是原，就是以前考试的那些原题。
对吧，他分好几问这一问那一问那一问就累，是那个样子的。
嗯，就是他一般是无外乎这样的话，比方说他他他可能会让你做这种这种跟比如跟复杂性分析有关的，对吧，或者是什么呢？是他给你一个具体的问题,给你具体的问题。
那他会让你去什么呢？就是说你你把这个问题求出来，你大概会采用一个什么样的思路，你会采用一个什么样的思路，就是你要写什么呢？就是你可以去写这个，这个算法就是它的一个，就是你不用任何的这种不是，让你写这个语句不是那个意思，就是你要么可以采用这种伪代码的形式，这也没问题，嗯，伪代码你都不想写，你就可以写大白话就是第一步啥，第二步啥，第三步啥，咱就累是这样了，就是你能把你的问题讲清楚就行了。
嗯，就是你比方说碰到一个碰，碰到碰到一个问题，对吧？那你根据他的要求，你肯定要想这个问题我应该用什么样的方法去去求解？就是你期末考试的时候啊，你你看到那个问题，如果如果哈，如果这个题目明确跟你说了，用什么方法求，那你老老师用什么方法，球对不对，他要没说，这个时候你就要去琢磨，有些时候可能这个本身就是个考点，就是他要去考察你有没有能力去选出合适的，根据我提的要求，你能选出合适的方法，你到底是用贪心来做，还是用动态规划来做，反正根据具体的这种问题，你去求。
当然可能还会有,比方说我们说了让你去你,比如说你回溯也好,你去你你你分支限界也好,对吧?我我我问你它是什么样的这种这种这种空间类型,对吧?我我让你去画。
最后的时候就是他遍历之后,他边遍历边点剪枝的那个结果,你你要你要会画,这都是明摆。
即便是这么说，那每年还是很多人不会画，嗯，就是画到最后画的乱七八糟，这个期末考试的事情，我就说这么多么多。
后面这今天几号,今天17号,对吧,时间其实也很短,也就是十来天的时间,就是大家集中精力。
那么好好复习一下,好复习一下行。
关于课,关于这个课的内容,我就说这么多。我们这个课就上到这个地方,结束就是水平有限,能力有限,这个讲的不好的地方大家多多包涵。
好吧,感谢大家一路以来配合
考点总结
递归与分治
棋盘覆盖、最接近点对、循环赛日程表不考，矩阵乘法优先级低
DP
多边形游戏、最优搜索二叉树不考
贪心
单源最短路径、最小生成树不考
回溯
符号三角形问题、圆排列、电路板排列、连续邮资不考
分支限界
单源最短路径不考，布线问题考的概率低可不看，什么旅行售货员电路板排列批处理作业调度优先级比较低，来不及看就不看