数据结构与算法
目录
树
给元素以及角色，使其相互关联, 树是各种关联方式中的一种.
完全二叉树
每一个父节点都有两个孩子, 只有树的最后一层可能是不满的.
假如按照从根节点开始, 编号从1开始, 每一层从左到右的顺序给结点编号, 父子之间的编号有规律可循.
父节点编号 = i
左孩子编号 = 2*i
右孩子编号 = 2*i + 1
因此, 可以把完全二叉树塞到一个数组中, 或者说数组本身就是一个完全二叉树, 只是以前不知道而已
完全二叉树的实现开销是最小的, 不需要额外使用指针定位.
寻找最优解
动态规划
有一类寻找最优的问题可以用动态规划的方法解决.
按照《算法导论》中的正式说法, 这类问题要具有下面的两个特点, 才可以使用动态规划的算法:
1 最优子结构
2 重复子问题
动态规划本质上是一种自底向上的穷举方法, 先把最底层的子问题的答案准备好, 一层层的向上计算, 直到最后一层.
只适合具有最优子结构的问题, 并且要有重复的子问题, 才能显示出动态规划的优势.
按照我自己的理解, 这类问题可以通过三步进行(以矩阵链乘法问题为例):
矩阵链乘法问题:
表达式: A1*A2*A3*A4*...An A是矩阵
怎样通过加括号的方式改变运算次序, 使整个表达式的计算过程中乘法运算的次数最少?
- 第一步, 如果用穷举的方式, 怎么解决?
考虑用穷举的方式如何解决, 并不是真的要靠穷举的方式获得结果, 真正的目的是弄清楚问题是什么, 将文字性的描述具象化, 在脑海中构建起整个场景.
要给表达式加括号, 括号里面又可以包含括号, 直观感觉括号里嵌套括号的情况不好穷举. 可以首先只穷举括号不包含的情况, 加完第一层括号后, 计算出新的缩短后的表达式, 再对这个表达式穷举括号不包含的情况, 直到最后只剩下了两个矩阵.
例如, 下面是第一层括号的一种添加方法:
A1*A2*(A3*A4)...An [式1] --> A1*A2*A34*...An [式2]
然后用同样的方法对[式2]加括号.
而且在添加括号的时候, 不需要考虑括号内有两个以上矩阵的情况
例如:
A1*A2*(A3*A4*A5)...An 等同于 A1*A2*(A3*A4)*A5 --> A1*A2*(A34*A5)
这里的等同指的是, 乘法运算的次数是相同的.
因此, 每次加括号的时候, 就可以依次考虑加一个括号有几种加法、加两个括号有几种加法, 直到完成穷举.
- 第二步, 问题是否可以划分成子问题, 用递归的方式解决?
递归只是实现手段, 实际是在考虑问题是否可以不断的被分割到最简单的情形. 也就是具有最优子结构.
在脑海中模拟一下表达式的运算过程, 首先最内层的括号内的矩阵相乘, 然后次内层的括号的矩阵, 依次进行, 直到最外层的完成后, 剩下了两个矩阵.
留心, 最后一步的时候就剩下了两个矩阵, 一个乘号. 这说明什么呢? 最后剩下的那个乘号把原先的表达式一分为二了.
那么乘法运算次数最少的加括号方式中, 最后剩下的是哪一个乘号呢? 不清楚, 但是可以试:
如果是第1个乘号, 那么算出用了M1次乘法
如果是第2个乘号, 那么算出用了M2次乘法
...
如果是第n个乘号, 那么算出用了Mn次乘法
M1..Mn中那个值最小, 最后剩下的就是哪个乘号, 这个乘号的两边需要使用括号括起来的表达式.
关键是, 当我们选定一个乘号后发现, 这个乘号两边不是出来了两个相同的问题了吗? 果断判定可以直接上递归.
- 第三步, 在用递归的方式解决的过程中, 是否总是遇到重复的问题?
在递归的过程中发现有些子问题被重复计算了.
例如:
假定1:
(A1 A2 A3 A4) * (A5 A6 A7 A8) --> (A1 (A2 A3 A4)) * (A5 A6 A7 A8)
假定2:
A1 * (A2 A3 A4 A5 A6 A7 A8) --> A1 * ((A2 A3 A4) * (A5 A6 A7 A8))
在两次假定中，都遇到了子问题(A2 A3 A4)和(A5 A6 A7 A8), 也就是说这两个子问题在这两次假定中被计算了两遍. 果断判定可以使用动态规划.
- 动态规划解法
在使用递归的方法的时候, 遇到子问题被重复计算的情形, 影响了算法效率. 那么可不可以事先把所有的子问题都计算出来, 直接把结果用于更上一层的问题?
既然递归实际上也是在穷举, 那么也就是说用事先计算所有子问题的方式遇到的子问题的种类和用递归的方式遇到的子问题的种类是相同, 不存在做了无用计算的情况.
首先考虑最底层的子问题有哪些? 递归的最后一层就是只有两个矩阵的情况, 所以把两个矩阵直接加括号的次数全部计算出.也就是:
A1*A2
A2*A3
A3*A4
A4*A5
...
An-1*An
再上一层的子问题:
A1*A2*A3 --> 用到子问题A1*A2 A2*A3
A2*A3*A4 --> 用到子问题A2*A3 A3*A4
A4*A5*A6 --> 用到子问题A4*A5 A5*A6
…
直到:
A1*A2*A3...An
对于矩阵链乘法, 可以用一个二维数组记录子问题的答案
1 2 3 4 5 6
1 0
2 0
3 0
4 0
5 0
6 0
资料:
《算法导论》第二版, 15章, 动态规划.
