动态规划(一)
算法动态规划部分(一),包括 python 源代码
更新
1
19.02.06 初始
- 参考资料
https://www.zybuluo.com/codeep/note/163962
https://www.liaoxuefeng.com/wiki/0014316089557264a6b348958f449949df42a6d3a2e542c000
https://mooc.study.163.com/course/1000005000
导语
- 计划重新整理一遍算法与数据结构,开始选择c实现,但是到了算法部分,这个吐血…
- 无奈用python重写,好处是与伪代码几乎对应.恩,人生苦短,我用python.
- 遂决定把算法部分重刷一遍,希望自己能刷完.
动态规划
概述
动态规划简述是 把原问题分解为相对简单的子问题,再依次求解最终解决原问题的方法。
许多子问题非常相似,动态规划中某个给定子问题的解已经得出,则存储,以便下次需要同一个子问题解之时直接查表。所以动态规划在输入的规模呈指数增长时特别有用。
一个问题是否适用于动态规划求解,取决于 重叠子问题 最优子结构 和 无后效性
- 最优子结构性质: 问题的最优解所包含的子问题的解也是最优的,可以通过求解子问题的最优解,来求解原问题.
- 重叠子问题: 在自顶向下对问题进行求解时,每次产生的子问题并不总是新问题,有些子问题会被重复计算多次。动态规划通过保存已求解的子问题答案,避免冗余计算.
- 无后效性: 子问题的解一旦确定,就不再改变,不受在这之后、包含它的更大的问题的求解决策影响。
动态规划基本求解步骤
- 分析优化解结构
- 递归定义最优解代价
- 自底向上计算最优解代价并保存子问题最优解
- 根据最优解信息,构造优化解
randoms类
提供原始数据,随机生成int , str 等.
计算函数运行时间.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class randoms(object):
def list_int(self, n=50, w=100):
return [random.randint(0, w) for i in range(n)]
def list_str(self, lens=20, capital=True):
return secrets.token_urlsafe(lens)
def time(self, method, setus):
if callable(method):
if isinstance(setus, str):
print(timeit.timeit(method, number=10, setup=setus))
else:
print('setus is not str')
else:
print("%s is not a method" % method)测试文件
1
2
3
4
5
6
7
8
9
10
11class test_randoms(unittest.TestCase):
def test_list_int(self):
arr = randoms.list_int()
self.assertTrue(isinstance(arr, list))
for x in arr:
self.assertTrue(isinstance(x, int))
def test_list_str(self):
strs = randoms.list_str()
print(strs)
self.assertTrue(isinstance(strs, str))
编号动态规划
输入为 $x_1$ , $x_2$ , … ,$x_n$ ,子问题是 $x_1$ , $x_2$ , … ,$x_i$ ,子问题的复杂性是 $O(n)$.
子结构的表示方法
- 状态i表示前i个元素构成的最优解,可能不包括第i个元素.
- 状态i表示前i个元素构成的最优解,必须包含第i个元素.
这里的例子是最长 递增/不下降 子序列问题.
最长递增子序列
问题定义
子序列是数字序列的子集合,且与序列中的数字顺序相同.即
$$a_{i_1},a_{i_2}…,a_{i_k}(1 \leq i_1 \leq i_2…\leq i_k \leq n)$$
递增子序列是数字严格递增的子序列.不下降子序列即包括相等的元素.
最长递增子序列LIS (Longest Increasing Subsequence),与最长不下降 子序列区别: 是否包括相同元素.
input: 一个数字序列 $a[1…n]$
output: 最大长度的递增子序列.(为了方便,这里仅输出递增子序列的长度)
分析
优化子结构
- 假设 LIS 包含$a_k$,那么一定存在一组最优解LISA,包含了 $a_1,a_2,…,a_{k-1}$ 这个子序列的LIS.
- 证明: 假设原序列的LIS的最优解 LISA 没有包含 $a_1,a_2,…,a_{k-1}$ 这个子序列 LIS 的最优解 LISB ,那么 LISB + $a_k$ 就是一个 比 LISA 更优的解,与假设矛盾.
重叠子问题
- 以 $a_k$ $a_{k+1}$ 为例
- $a_1,…,a_{k}$ 与 $a_1,…,a_{k+1}$ 的重叠子问题: $a_1,a_2, …,a_{k-1}$ 这个子序列 LIS 的最优解.
所以LIS问题可以通过动态规划求解.
其他
子问题表示: $dp[i]$ 表示以第 i 个元素结尾的前i个元素构成序列的最长递增子序列的长度.
最优解递归方程
$$dp[i] = max \left{ dp[j] \mid 0<j<i ,;, a_j > a_i \right} + 1$$
注意 $dp[i]$ 表示的并不是前i个元素组成序列的LIS最优解.
代码
1
2
3
4
5
6
7
8
9def lis_dp(self, arr):
# dp = [0 for x in range(0, len(arr))]
dp = [0] * len(arr) # 更方便
for i, valuei in enumerate(arr):
for j, valuej in enumerate(arr[0:i]):
if valuej < valuei and dp[j] > dp[i]:
dp[i] = dp[j]
dp[i] += 1
return max(dp) # 返回LIS最优解还需要遍历回溯dp[]时间复杂度为 $n^2$ ,并不是最优的.分析来看时间主要花费在了
if valuej < valuei and dp[j] > dp[i]:
这个比较判断上,需要对此做出改进.时间复杂度为 $nlogn$
- 不再维护一个 $dp[i]$ 数组,转而维护 $tails[i]$ .
- $tails[i]$ 代表了序列中长度为 i 的子序列的最小值.同时维护一个 size 变量,代表 $tails[i]$ 目前的最大有效长度.
- 从前往后遍历整个序列,与 $tails[i]$ 比较,若在 $tails[,]$ 中某个位置,则更新对应位置的 $tails[i]$ .若大于 $tails[,]$ 的最大值,则
size+=1
并在对应位置存入该值. - 这里因为 $tails[i]$ 为递增的,可以使用二分查找.降低时间复杂度.
- 当序列遍历完成后,size即为LIS的最大值.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14def lis_dp_binse(self, arr):
tails = [0] * len(arr)
size = 0
for x in arr:
i, j = 0, size
while i != j:
m = (i + j) // 2
if tails[m] <= x:
i = m + 1
else:
j = m
tails[i] = x
size = max(i + 1, size)
return size测试
1
2
3
4
5
6if __name__ == "__main__":
arr = randoms.list_int(500)
n = functools.partial(lis.lis_dp, arr)
s = functools.partial(lis.lis_dp_binse, arr)
randoms.time(n, 'from lis import lis'),
randoms.time(s, 'from lis import lis')结果如下
1
20.4465395999999999
0.026626600000000167
划分动态规划
输入为 $x_1$ , $x_2$ , … ,$x_n$ ,子问题是 $x_i$ , $x_{i+1}$ , … ,$x_j$ ,子问题的复杂性是 $O(n^2)$.
这里的例子是 凸多边形的最优三角剖分, 矩阵链乘.
两者很相似,矩阵链乘是用c写的,代码量实在太多,故仅提供 凸多边形的最优三角剖分的 python 代码.
凸多边形的最优三角剖分
问题定义
- 多边形: 一个顶点的坐标集合 $P=\left( v_0,v_1,…v_n \right)$ 或者顶点的序列 $v_0,v_1,…v_n$
- 简单多边形: 除顶点外没有任何交叉点的多边形,这个问题涉及到的都是简单多边形.
- 弦: 多边形 P 上的任意两个不相邻的节点 $v_i,,v_{i+1}$ 所对应的线段.$v_iv_{i+1}$ 称为弦.
- 三角剖分: 多边形P的三角剖分是将P划分为不相交的三角剖分弦的集合.
- 输入: 多边形P(序列)和代价函数W(任意)
- 输出: P的三角剖分T,使得 $\sum_{s\in S_T}{W\left(s\right)}$ 最小.
分析
- 优化子结构
- $P=\left( v_0,v_1,…v_n \right)$ 是 n+1 个顶点的多边形.$T_p$ 是 P 的最优三角剖分, $v_k$ 是 $v_0 v_n$中间一点.$v_0,v_k,v_n$构成一个三角形,则有:
$T_p=T\left(\ v_0,…,v_k \right)\bigcup T\left(\ v_k,…,v_n \right)\bigcup {v_0 v_k,v_k v_n,v_n v_0}$ - $T\left(\ v_0,…,v_k \right)$ 与 $T\left(\ v_k,…,v_n \right)$ 分别对应$\left(\ v_0,…,v_k \right)$ 和 $\left(\ v_k,…,v_n \right)$ 的最优三角剖分.
- 证明: 假设 $T\left(\ v_0,…,v_k \right)$ 不是 $\left(\ v_0,…,v_k \right)$ 的最优三角剖分,则 $\left(\ v_0,…,v_k \right)$ 的最优三角剖分带回原式中会得到比 $T_p$ 更优的解.与前提矛盾,故不成立.
- 因为不知道具体 $v_k$ 的取值,需要计算由 $k\in{0,n}$ 所有取值,取到使 $T_p$ 最小的 $v_k$ .
- $P=\left( v_0,v_1,…v_n \right)$ 是 n+1 个顶点的多边形.$T_p$ 是 P 的最优三角剖分, $v_k$ 是 $v_0 v_n$中间一点.$v_0,v_k,v_n$构成一个三角形,则有:
- 重叠子问题
- 以$\left( v_0,…v_{k} \right)$ 和 $\left( v_0,…v_{k+1} \right)$ 为例.
- 在确定 $v_k$ 的循环中,$\left( v_0,…v_{k} \right)$ 和 $\left( v_0,…v_{k+1} \right)$ 用到的子问题结果除 $T\left(\ v_0,…,v_k \right)$外,完全一致,因此适用于动态规划求解.
- 优化子结构
其他
- 子问题表示: $matrix[i,j] = < v_i,…,v_j >$ 的最优三角剖分代价.
- 最优解递归方程:
- $$matrix[i,j] =
\begin{cases}
0& \text{j-i < 2 }\
min_{i\leq k < j} {matrix[i,k]+matrix[k,j]+w(i,k,j)}& \text{other}\
\end{cases}$$
- $$matrix[i,j] =
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class aot(object):
# 仅返回和
def w(self, key1, key2, key3, arr):
return (arr[key1] + arr[key2] + arr[key3])
def aots(self, start, end, arr):
matrix = [[0 for i in range(len(arr) + 1)]
for j in range(len(arr) + 1)]
for i in range(start, end + 1):
m = start
n = i
while m <= start + end - i and n <= end:
if abs(m - n) <= 1:
matrix[m][n] = 0
else:
matrix[m][n] = \
min([matrix[m][k]+matrix[k][n]+self.w(m, k, n, arr) for k in range(m+1, n)])
m += 1
n += 1
return matrix[start][end]
数轴动态规划
输入为 $x_1$ , $x_2$ , … ,$x_n$ 和数字C,子问题是 $x_1$ , $x_2$ , … ,$x_i$ $K(K<C)$,子问题的复杂性是 $O(nC)$.
这里的例子是0-1背包问题.
0-1背包
一个经典的组合优化问题.背包问题通常适用于动态规划和贪心法.贪心法对于0-1背包可能无法产生最优解.
问题定义
- 给定n种物品和一个背包,物品 i 的重量为 $w_i$ 价值为 $v_i$ ,背包容量为C,要求选择转入背包的物品使得背包的总价值最大.
- 0-1背包限定物品只能选择装入/不装入,一个物品仅装入一次.
- input: ${w_1,..,w_n \mid w_i > 0, i\in(1,n)}$ , ${v_1,..,v_n \mid v_i > 0,i\in(1,n)}$ , $C(C>0)$
- output: ${x_1,x_2..,x_n \mid x_i\in(0,1)}$ 且 $\sum_{1\leq i \leq n}{v_i x_i} \leq C$, $Max\sum_{1\leq i \leq n}{w_i x_i}$
- 我们这里假定$w_i$以及C 都是整数.
分析
优化子结构
假设$(y_1,y_2,…,y_n)$是0-1背包的优化解,则$(y_1,…,y_{n-1})$,是子问题的优化解,子问题分两种情况
- $y_n=0$,没选,子问题就是去掉最后一个物品,C的0-1背包问题的优化解.
- $y_n=1$,选了,子问题就是去掉最后一个物品,$C-w_n$的0-1背包问题的优化解.
合并以上情况,子问题定义
$$max
\begin{cases}
\sum_{1\leq i\leq n-1}{v_i x_i} \mid {\sum_{1\leq i\leq n-1}{w_i x_i \leq C}}\
\sum_{1\leq i\leq n-1}{v_i x_i} + v_1 \mid {\sum_{1\leq i\leq n-1}{w_i x_i \leq C-w_n}}
\end{cases}$$证明:
假设 $(y_1,…,y_{n-1})$ 不是子问题的优化解,那么存在更优解$(z_1,…,z_{n-1})$.$x_n=0$没选,$(z_1,…,z_{n-1})$就是的原问题的最优解,与前提矛盾.
$x_n=1$再加上$v_i$,$(z_1,…,z_{n-1},x_n)$就是原问题的最优解,与前提矛盾.
重叠子问题
- 分析见优化子结构.
- 因为不知道$w_i$的具体数值,只能假设C为整数,$w_i$为整数的前提下,将背包的容量$(1\leq i \leq C)$全部算出.需要二维数组存储子问题的计算结果.
其他
- 子问题定义
$matrix[m][n]$背包容量为n,可选物品为前m个时的最优解. - 最优解递归方程:
- $$matrix[m][n]= Max
\begin{cases}
matrix[m-1][n] \
matrix[m][n-w_m]+v_m
\end{cases}$$
- 子问题定义
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22def kp_dp(self, weight, value, wlimted):
lens = len(weight)
# 忽略matrix[0][x] matrix[x][0]
matrix = [[0 for i in range(wlimted + 1)] for j in range(lens + 1)]
# 填充 m=1 第一排
for i in range(1, wlimted + 1):
if i >= weight[1]:
matrix[1][i] = value[1]
else:
matrix[1][i] = 0
# 最优解递归方程
for m in range(2, lens + 1):
for n in range(1, wlimted + 1):
# 可以以装入物品,输入的weight[]value[]值自0开始.
if n >= weight[m-1]:
matrix[m][n] = max(
matrix[m - 1][n],
matrix[m - 1][n - weight[m - 1]] + value[m - 1])
else:
matrix[m][n] = matrix[m - 1][n]
return matrix[lens][wlimted]
前缀动态规划
输入为 $x_1$ , $x_2$ , … ,$x_n$ 和 $y_1$ , $y_2$ , … ,$y_n$,子问题是 $x_1$ , $x_2$ , … ,$x_i$ 和 $y_1$ , $y_2$ , … ,$y_j$,子问题的复杂性是 $O(mn)$.
典型的例子是 最长公共子序列(LCS) 和 字符串编辑距离
字符串编辑距离
编辑距离
- 编辑距离是衡量两个字符串相似程度的指标.具体指将A字符串转换成B字符串的最小代价.
- 包括 B 中字符替换 A 中字符.删除A中字符,插入B中字符.
问题定义
- 编辑操作: 替换,删除,插入
- input: 两个字符串 $A=a_1 a_2…a_m$ 和 $B=b_1b_2…b_m$
- output: A转换为B的编辑的最小代价.
分析
优化子结构
假设$D_{mn}$是A与B的编辑距离.那么子问题可以分为3种情况,分别对应编辑距离定义的3中操作.- $b_n$替换$a_m$,则子问题$D_{m-1,n-1} = D_{mn}-c(a_m,b_n)$
$if,a_m==b_n , c = 0 , else , c = 1$ - 删除$a_m$,则子问题$D_{m-1,n} = D_{mn}-1$
- 插入$b_n$,则子问题$D_{m,n-1} = D_{mn}-1$
- 证明: 反证法,不再赘述.
- $b_n$替换$a_m$,则子问题$D_{m-1,n-1} = D_{mn}-c(a_m,b_n)$
重叠子问题
- 以$D_{m,n}$与$D_{m-1,n}$ $D_{m,n-1}$ 和 $D_{m-1,n-1}$ 为例.
- 通过优化子结构分析得知,计算$D_{i,j}$需要用到$D_{i-1,j}$ $D_{i,j-1} 和$D_{i-1,j-1},对应数据结构是一个二维矩阵,图形化后,正好对应元素上,左,左上.3个位置.
- $D_{m,n}$ 与 $D_{m-1,n}$ $D_{m,n-1}$ 和 $D_{m-1,n-1}$ 的公共区域是以 $D_{0,0} \mid D_{m-1,n-1}$ 为对角线的公共矩形区域.
所以编辑距离可以使用动态规划求解.
其他
- 子问题定义: $matrix[m][n]$表示字符串A的前m个字符与B字符串前n个字符的编辑距离.
- 最优解递归方程:
- $$matrix[m][n]= Min
\begin{cases}
matrix[m-1][n-1] +c(a_m,b_n) \
matrix[m][n-1] + 1 \
matrix[m-1][n] + 1
\end{cases}$$ - python中字符串下标由0开始,需要额外注意一下.
- 矩阵的填充顺序:
- 第一排,按照插入的子问题代价填入
- 第一列,按照插入的子问题代价填入
- 依次从左往右,由上到下填充整个矩阵.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class ed(object):
def editdistance(self, stra, strb):
matrix = [[0 for i in range(len(strb) + 1)]
for j in range(len(stra) + 1)]
# 左上角
matrix[0][0] = 0
# 第一列
for m in range(1, len(stra) + 1):
matrix[m][0] = m
# 第一排
for n in range(1, len(strb) + 1):
matrix[0][n] = n
# 其他
for m in range(1, len(stra) + 1):
for n in range(1, len(strb) + 1):
matrix[m][n] = min(
matrix[m - 1][n] + 1, matrix[m][n - 1] + 1,
matrix[m - 1][n - 1] +
(0 if stra[m - 1] == strb[n - 1] else 1))
return matrix[len(stra)][len(strb)]ps: randoms.list_str 是 引用secrets模块生成的随机字符串,几次生成之间几乎没有重复,手输几个看结果即可.
树型动态规划
- 详情-算法-动态规划(二)