红黑树的扩充
由于红黑树这种结构很好的平衡性(树的高度不会很高), 对于动态变化的集合插入,查找,删除等操作的复杂度都比较低, 通过给它的节点增加一些其他的属性, 能够得到一些在特定情况下很有用的数据结构。
扩充数据结构的四个步骤
- 选择基础的数据结构
- 确定需要给数据结构添加哪些信息, 这些信息可能被添加到每个节点中,也可能被添加作为整体数据结构的性质
- 验证在数据结构的基本操作的过程中,这些信息可以被有效的维护, 这里的有效是指不会因为维护这些信息增加基础操作的复杂度
- 利用这些信息提供一些有用的操作
通过扩充红黑树得到顺序统计
通过给红黑树的每一个节点x附加属性size[x], 表示以x为根的子树的节点个数, 可以通过递归确定一棵红黑树的第i小关键字的元素。 由于包含n个元素的红黑树的高度为,每次递归高度都会下降一层, 所以查找第i小关键字的时间复杂度为。
在第9章中,给出了获取n个元素的数组中第i个元素的的算法, 而一个包含n个元素的数组如果是有序的话,那么获取第i个元素的复杂度是。 但是这种扩充的数据结构的好处在于它的动态性,它的插入和删除的时间复杂度也是, 而一个有序数组的插入和删除的复杂度是。
通过扩充红黑树得到区间树
在区间树中,每一个节点x包含了一段区间int[x],同时包含了一个max[x], 表示以x为根的子树中所有区间的右端点的最大值,同时每一个节点的key[x] = low[int[x]], 也就是说是把每一个节点所包含区间的左端点作为key。
区间树使得查找整个红黑树中与某一个区间i重合的区间变得十分容易, 可以如下递归实现:
- 如果当前节点为空,返回空节点
- 如果区间i与当前节点的区间重合,返回当前节点
- 如果区间i的左端点小于当前节点左儿子的max,递归查找左子树
- 否则递归查找右子树
情况1,2很自然,情况4也比较好理解, 因为如果i的左端点大于左儿子的max,它就大于那么对于左子树中所有节点的右端点, 左子树中一定不存在和区间i重合区间。情况3需要一定的思考, 因为如果i的左端点小于当前节点左儿子的max,并不能保证它一定不会与右子树中的区间重合, 所以如果只是递归查找左子树,如果左子树中有区间和i重合,那么能够返回正确结果 (因为只需要找到一个和i重合的区间就可以),如果左子树中没有区间与i重合, 那右子树中可能会有区间与i重合,导致没有返回正确的结果。情况是这样的吗?
不是这样的,下面可以证明在情况3时如果左子树中没有找到与i重合的区间, 那么在右子树中也一定不存在和i重合的区间。
假设左儿子的max来自于high[j](也就是说,是左子树中区间j的右端点), 那么一定有
否则区间i和j重合,对于右子树中的任意区间k,一定有
所以k与i不重合。
动态规划
动态规划主要用于求解最优化问题, 它的基本思想是通过把子问题的结果保存起来, 这样当遇到一个更大的问题时,如果它需要解决子问题, 那么可以直接使用保存好的子问题的结果,而不用再去重复解决子问题。
动态规划适用的基本条件
使用动态规划必须要满足两个基本的条件:
- 最优子结构。一个问题的最优解包含子问题的最优解。 通常可以通过”剪切-粘贴”的方法证明最优子结构,也就是说, 假设一个问题的最优解没有包含子问题的最优解, 那么把相应的子问题的解替换成最优解将得到一个更好的解, 从而得出矛盾。
- 重叠子问题。如果没有大量的重叠子问题, 那么直接通过递归求解子问题就可以, 动态规划相对于递归的好处也就在于不用重复去计算重叠的子问题, 从而节省了时间。
动态规划解题的基本思路
在确定了一个问题适合采用动态规划进行解决之后, 仍然需要考虑几个问题。最主要的问题就是如何将问题利用更小的子问题来进行解决, 此时的思路是通过把原来的问题通过转化变成更小的子问题, 利用合适的转化可以把一个问题缩小成一个更小的子问题,比如最长递增子序列问题, 求以元素n结尾的最长递增子序列的长度, 可以转化为求以比n小的排在n前面的某个元素结尾的最长递增子序列的长度。 通过转化之后问题就缩小了。
将问题转换成子问题之后,必须要知道如何通过子问题的解得到原问题的解, 也就是所谓的递推公式, 比如上述问题,知道n之前的某个小于n元素的最长子序列的长度之后, n的最长子序列的长度就是这个长度加1。
一个问题可能转化成多个子问题,比如说上面的问题, 比n小的排在n之前的元素可能有多个,这时,就需要从多个子问题之间做出选择。 这个选择通常是比较容易的,直接从所有根据子问题递推得到的解中选出一个最优解即可。 一般情况下,还需要记录此时的选择,用于构造出一个最优解。
把上述的问题都考虑好之后,就可以按照问题的大小, 从小到大依次将各个问题解决,直到达到所需要的问题的大小, 就得到了所需问题的解。
动态规划的经典问题
最长公共子序列(LCS)
- 问题描述: 定义序列的一个子序列为 ,其中 。求两个序列 和的最长公共子序列的长度c[m, n]。
-
求解方法: 定义c[i, j]为序列和的LCS的长度, 有如下递推公式成立
- 说明: 其实c[i, j]有三个子问题, c[i-1, j-1], c[i-1, j], c[i, j-1], 为什么当时只需要考虑第一个子问题,因为有如下不等式成立:
因为c[i, j-1]相对于c[i-1, j-1]就多了一个元素c[i], 最多能够为最长公共子序列多增加长度1,同理对于c[i-1, j]也是如此。
背包问题
- 问题描述: 给定一个重量为w的背包,有n件商品重量分别为, 价值分别为,求这个背包能容纳的最大的商品价值
-
问题求解:
- 如果对于每一件商品,可以拿取任意多次,则定义K(w)表示重量为w的背包最大的价值, 有如下递推关系成立:
- 如果没一件商品只能拿一次,就不能采取上面的方法了,因为如果在K(w)转换至时使用了 商品i, 在求解就不能再使用商品i,上述的递推公式不成立。必须采用另外一种方法。 定义K(w, i)为重量为w的背包在装载商品1..i时的最大价值,有如下递推关系成立:
Floyd算法的正确性
Floyd算法用于求解图中所有节点中的最短路径。 基本思想是通过n(n为节点个数)次循环更新所有节点对之间的最短路径, 伪代码如下:
for k := 1 to n
for i := 1 to n
for j := 1 to n
if path[i][k] + path[k][j] < path[i][j] then
path[i][j] := path[i][k]+path[k][j];
在每次迭代时,对于任意节点对(i, j),如果(i, k)的路径长度加(k, j)的路径长度小于 原来的(i, j)的路径长度, 那么就将(i, j)的路径长度更新为(i, k)的路径长度加(k, j)的路径长度(也就是说, 让(i, j)的最短路径经过k)。 算法的时间复杂度为。
动态规划对于这个算法的理解是,在迭代k结束之后, 此时(i, j)的最短路径为仅使用{1, 2, …, k}作为中间节点的最短路径, 当循环结束时,k=n, 此时(i, j)的最短路径为使用任意节点作为中间节点的最短路径, 也就是(i, j)之间的最短路径。
凭直接感觉,比如说(i, j)之间的最短路径为:
其中, 如果最外层的循环遍历到时,因为此时不能使用作为中间节点, 所以不会把(i, j)之间的最短路径经过, 当允许使用作为中间节点时, 有不会再去遍历让(i, j)之间的最短路径经过, 所以,(i, j)之间的最短路径没有被找到,这个算法好像是错误的。
我开始老是纠结在这样的感觉中, 认为Floyd算法可能并没有找到一条最短的路径, 可是又总是找不到一个反例, 后面经过仔细地思考,总结出两种方法来说明这个算法的正确性, 解除了我的疑虑。
通过循环不变式来证明Floyd算法的正确性
通过证明以下循环不变式证明算法的正确性:
在第k轮迭代开始前,对于任意节点对(i, j), 此时的最短路径长度为使用节点{1, 2, .., k-1}作为中间节点的最短路径长度。
- 初始化:在开始时,k=1, 此时的最短的路径为不使用任何中间节点的最短路径。
- 保持:在第k轮迭代开始时,
此时(i, j)之间的最短路径为使用{1,2,…, k-1}作为中间节点的最短路径,
令p为(i, j)之间使用{1, 2, …, k}的最短路径:
- 如果path[i][k] + path[k][j] < path[i][j], 那么此时p一定为, 其中为(i, k)之间使用{1, 2, …, k-1}作为中间节点的最短路径, 为(k, j)之间使用{1, 2, …, k-1}作为中间节点的最短路径。 所以此时p的长度为path[i][k] + path[k][j],不变式得以保持
- 如果path[i][k] + path[k][j] >= path[i][j], 那么此时p一定也是(i, j)仅经过{1, 2, …, k-1}的最短路径(也就是说, 此时p一定不经过k),p的长度就是path[i][j], 不变式同样可以保持
- 终止:循环结束时,k=n+1, 此时(i, j)的最短路径是使用任意节点作为中间节点的最短路径, 也就是(i, j)的最短路径。
对于这个循环不变式,定义表示(i, j)之间仅使用节点1,…,k作为中间节点的最短路径的长度, 利用这个递推公式:
可能要更好理解一些。
通过归纳证明Floyd算法的正确性
可以通过这样一种思路来证明:假设k是(i, j)最短路径中最大的中间节点, 也就是说对于(i, j)最短路径中任意的中间节点m, 有,这样, k是(i, j)最短路径中最后被迭代的节点,如果在迭代到k时, 能够将(i, j)之间最短路径长度正确的设置,那么这个算法就是正确的。 在迭代k时,如果(i, k)和(k, j)之间的最短路径已经被正确设置时, 那么(i, j)在迭代k结束之后能够被正确设置。
下面通过归纳(i, j)路径中中间节点的个数n来证明在迭代k(k是(i, j)最短路径中最后被迭代的节点)时, (i, k)和(k, j)最短路径已经被正确的设置:
- 当n=1, 在迭代k时,(i, k)和(k, j)都没有中间节点, 最短路径就是节点i和k以及k和j之间的距离, 已经被正确的设置。
- 如果时,命题成立。那么当n=s+1时,在迭代k时, 对于路径(i, k), 它的中间节点的个数, 那么当这条路径的最后一个节点被迭代时,和已经被正确设置, 迭代之后,能够将路径(i, k)正确设置,同理可以证明路径(k , j)也能够被正确设置。
- 由上述两步可以得知对于任意个数的中间节点,(i, j)在迭代最后一个节点k时, (i, k)和(k, j)能够被正确的设置。
忽略我
最后还是吐槽一下动态规划这一章的翻译真的很烂, 感觉和前面的章节不是同一个人翻译的, 很多语句很不通顺,比如说有个反问句就绕了我好久, 试着推测原文才明白什么意思。 人和人之间还是有差距的啊,不管做什么都是, 希望后面的几章能够翻译好一点,bless!