lyj Blog

# Chap 2 动态规划

# 矩阵连乘

考虑

设 计算 所需的最少数乘次数为

$ m[i,j]=\left{ \begin{array}{rcl} 0 & & {i=j}\ \min\limits_{i \leq k \leq j} {m[i][k] + m[k+1][j] + p_{i-1}p_kp_j} & & {i \lt j}\ \end{array} \right. $

依据递归式自底向上的方式进行计算，计算过程中，使用备忘录算法，保存已解决的子问题答案，避免递归重复。

image-20200324184026685 
def matrixChain(p, n, m, s):
  '''
  从1开始计数
  m为n*n的矩阵，m[i,j]记录A_i* ... * A_j 的最小总数乘次数；
  s为n*n矩阵，s[i,j]记录最佳切分位置
  p为n维向量，p[i]记录A_i和A_j的连接维数
  '''
  
  for i in range(1,n+1):
    m[i][i] = 0
  for r in range(2, n+1):
    for i in range(1, n-r):
      j = i + r - 1
      m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j]
      s[i][j] = i
      for k in range(i+1, j):
        t = m[i][k] + m[k+1][j] + p[i-1]*p[k]* p[j]
        if t < m[i][j]:
          m[i][j] = t
          s[i][j] = k

def traceback(i, j, s):
  '输出最优次序，带括号'
  if i < j:
    print('(')
    traceback(i, s[i][j], s)
    print(')(')
    traceback(s[i,j]+1, j, s)
    print(')')
  elif i == j:
    print('A_{}'.format(i))
  else:
    pass

# 最长公共子序列

  • 给定序列 ， ，称ZZ 是 XX 的子序列，即存在一个严格递增下标序列 使得对于所有 ， 有

  • 当序列 ZZ 既是 XX 的子序列，也是 YY 的子序列，则 ZZ 是 XX 和 YY 的公共子序列

  • 最长公共子序列具有最优子结构性质

设序列 和 的最长公共子序列为 ，则有以下性质：

  • 若 ，则 ，且 是 和 的最长公共子序列
  • 若 ，且 ，则 Z 是 和 YY 的最长公共子序列
  • 若 ，且 ，且 Z 是 XX 和 的最长公共子序列

记 为 和 的最长公共子序列的长度，有递归关系如下：

$ c[i][j]=\left{ \begin{array}{rcl} 0 & & {i=0,j=0}\ c[i-1][j-1]+1 & & {i, j > 0; x_i = y_j}\ \max{c[i][j-1], c[i-1][j]} & & i,j \gt 0; x_i \neq y_j \end{array} \right. $

def LCSLength(m, n, X, Y, c, b):
  '''
  b记录路径，c记录长度
  此算法时间复杂度为 O(mn)
  '''
  for i in range(1, m+1):
    c[i][0] = 0
  for i in range(1, n+1):
    c[0][i] = 0
  for i in range(1, m+1):
    for j in range(1, n+1):
      if x[i] == y[j]:
        c[i][j] = c[i-1][j-1] + 1
        b[i][j] = 'leftup'
      elif c[i-1][j] >= c[i][j-1]:
        c[i][j] = c[i-1][j]
        b[i][j] = 'up'
      else:
        c[i][j] = c[i][j-1]
        b[i][j] = 'left'

def LCS(i, j, X, b):
  '''
  打印最长公共子序列，时间复杂度为 O(m+n)
  '''
  if i == 0 or j == 0:
    return
  if b[i][j] == 'leftup':
    LCS(i-1, j-1, X, b)
    print(X[i])
  elif b[i][j] == 'top':
    LCS(i-1, j, X, b)
  else:
    LCS(i, j-1, X, b)
image-20200324225847774
  • 若仅考虑长度，则可以省去数组 bb ，且用两行的数组空间就可以计算，再进一步分析，可以将空间需求减到

# 最长递增子序列

def LIS(li):
  'O(n^2), 只给长度，不给序列本身'
  if len(li) == 0:
    return 0
  else:
    dp = [0] * len(li)
    dp[0] = 1
    for i in range(1, len(li)):
      tmax = 1
      for j in range(0,i):
        if li[i] > li[j]:
          tmax = max(tmax, dp[j]+1)
      dp[i] = tmax
    print(dp)
    print('最长递增子序列的长度为' + str(max(dp)))
    return max(dp)

def LIS(li):
  'O(nlogn), 只给长度，不给序列本身'
  if li:
    tmpList = [li[0]]
    for item in li:
      if item > tmpList[-1]:
        tmpList.append(item)
      else:
        pos = bisect.bisect_left(tmpList, item)
        tmpList[pos] = item
    return len(tmpList)
  return 0

# 最大子段和

给定 nn 个整数组成的序列 ，求该序列形如 的子段和的最大值，即

计算所有可能性将使时间复杂度达到 ，稍微的优化可以将其达到 ,如下：

def maxSum(n, a, best_i, best_j):
  sum = 0
  for i in range(1, n+1):
    thisSum = 0
    for j in range(i, n+1):
      thisSum += a[j]
      if thisSum > sum:
        sum = thisSum
        best_i = i
        best_j = j
  return sum

考虑时间复杂度为 的分治算法对应的三种情形

  • 的最大子段和与 的最大子段和相同

  • 的最大子段和与 的最大子段和相同

  • 的最大子段和为 ，满足

前两种情况可递归求得，第三种情形中，最大子段和等于两边最大子段和的和，即

考虑时间复杂度为 的动态规划算法

记 ，有最优子结构 ，初始的最大子段和默认为 ，每次有新的 ，都拿去比一比，把较大的存起来，代码如下：

def maxSum(n, a):
    _sum = 0
    b = 0
    for i in range(1, n+1):
        b = b + a[i] if b > 0 else a[i]
        _sum = max(_sum, b)
    return _sum

# 最大子矩阵和问题

给定整数矩阵 ，求一个子矩阵，使其各元素之和最大，即

直接枚举的时间复杂度是，可以借助一维情形的最大子段和问题来优化，时间复杂度为 

import numpy as np
def maxSum2(a):
  _sum = 0
  b = np.zeros(n+1)
  for i in range(1, m+1):
    for k in range(1, n+1):
      b[k] = 0
    for j in range(i, m+1):
      for k in range(1, n+1):
        b[k] += a[j][k]
      # 调用上题写好的函数,本质是将特定范围的列先按行求和聚合成一列，再转化为一维情形
      _max = maxSum(n, b) 
      if _max > _sum:
        _sum = _max
  return _sum

上述算法在按行求和聚合的时候，出现了大量的重复计算，可以用下述方法将时间复杂度优化优化成 ：

  • 先用 时间累加一次结果
  • 只需 时间即可计算

# 电路连线

image-20200325163633881

导线 将上端接线柱 ii 与 下端接线柱 相连

两条导线相交的充要条件是

求导线集的最大不相交子集

记 的最大不相交子集为 ，其大小记为

当 时， $ MNS(i,j)= N(i,j) = \left{ \begin{array}{rcl} \varnothing & & {j \lt \pi(1)}\ {(1,\pi(1))} & & {j \geq \pi(1)}\ \end{array} \right. $

当 时:

  • ，此时 ，故此时 ，

    • 若 ，则对任意 ，有 且 ，否则会相交；所以

    • 若 ，则对任意 ，有 且 ，从而 , ，另一方面， ，，结合二者可得

故有最优子结构如下：

当 时， $ S(i,j)= \left{ \begin{array}{rcl} 0 & & {j \lt \pi(1)}\ 1 & & {j \geq \pi(1)}\ \end{array} \right. $

当 时， $ S(i,j)= \left{ \begin{array}{rcl} S(i-1,j) & & {j \lt \pi(i)}\ \max {S(i-1,j), \quad S(i-1,\pi(i)-1)+1 } & & {j \geq \pi(i)}\ \end{array} \right. $

计算最大不相交子集的基数的时间复杂度为 $O(n^2) ，回溯求具体解再会用O(n)$的时间

思考：最少可以切分为几个子集，使得每个子集的线均不交叉？

# 流水作业调度

作业集 需要依次经历工序集 ，时间成本矩阵 中，其中表示作业 在工序 中的耗时，注意，每道工序同时只能运行一个作业，当某工序处理完作业但下一个作业仍处于上一道工序时，将会出现闲置的情况。求作业集的最优调度顺序，使得总耗时最少。

考虑 n = 2 的简单情况

从直观上讲，一个最优调度应该使没有空闲时间， 空闲时间最少，考虑 S 是 N的作业子集，在一般情况下，机器 开始加工 SS 中的作业时，机器 还在加工其他作业，需要等时间 tt 后才能利用，记该情况下完成 SS 中作业所需的最短时间为 ，流水作业调度问题的最优值为

设 是作业集 的一个最优调度，它所需的加工时间为 ，其中 是工序 的等待时间为 时，安排作业 所需的时间，记 ，则有

流水作业问题具有最优子结构：

推广到一般情形：

其中， 这一项是由于在机器上，作业 ii 必须在 后才能开工，故在机器 完成作业 ii 之后，机器还需 才能完成对作业 ii 的加工

考虑一个最优调度中，前两个任务是 ，由动态递归可知：

\begin{align} t_{ij} &= c_{j,2} + \max\{c_{i,2} + \max \{t-c_{i,1},0\}-c_{j,1}, \ 0\} \\ &= c_{j,2}+ c_{i,2} - c_{j,1} + \max\{\max\{t-c_{i,1}, \ 0\}, \ 0\}, \ c_{j,1}-c_{i,2} \}\\ &= c_{j,2}+ c_{i,2} - c_{j,1} -c_{i,1} + \max\{t, \ c_{i,1}+c_{j,1}-c_{i,2},c_{i,1}\}\\ \end{align}

观察式子，若作业 满足Johnson不等式： ，则有推理过程如下

这意味着当作业 不满足Johnson不等式时，通过交换它们的加工顺序，使其满足Johnson不等式，且不增加加工时间，故对于流水作业调度问题，必存在一个最优调度为满足 Johnson法则的调度，进一步可以证明，调度满足Johnson法则等价于 ，故任意两个满足Johnson法则的调度具有相同的加工时间。

下面时间复杂度为的算法用于构造一个满足Johnson法则的调度

  • 令 ，

  • 将 中作业依照 增序排列，将 中作业依照 减序排列

  • 中作业接上 中作业即为满足Johnson法则的最优调度

下面给出一个两阶段的python求解程序

def schedule(a, b, n):
  'Johnson算法生成最优排列'
  N1 = []
  N2 = []
  for i in range(n):
    if a[i] < b[i]:
      N1.append((i,a[i],b[i]))
    else:
      N2.append((i,a[i],b[i]))
  N1.sort(key=lambda x: x[1])
  N2.sort(key=lambda x: x[2], reverse=True)
  N = N1 + N2
  bestorder = [i[0] for i in N]
  besttime = schedule_time(N, 0)
  return bestorder, besttime

def schedule_time(N, remaining):
    '根据特定排序计算总时间'
    if len(N) == 0:
        return remaining
    else:
        return N[0][1] + schedule_time(N[1:], N[0][2]+ max(remaining-N[0][1], 0))

def schedule_test():
  n = 3 # 作业数
  a = [1,3,2] # 第一阶段耗时
  b = [2,3,1] # 第二阶段耗时
  bestorder, besttime = schedule(a, b, n)
  print('最佳调度顺序：' , bestorder)
  print('最佳调度时间：' , besttime)

schedule_test()

# 0-1背包问题

给定 nn 种物品和一个容量为 cc 的背包，其中，物品ii 的重量是 ，其价值为 ，应选择装入哪些物品使价值最大

记 是背包容量为 jj ，可选择物品为 时0-1背包问题的最优值，由其最优子结构性质计算递归，实质是求 的最大值，下面给出了Python实现的 时间复杂度的算法（有一个改进算法可以时间复杂度到 , 此处不讲，建议了解）

$ m(i,j)=\left{ \begin{array}{rcl} \max{m(i-1,j), m(i-1, j-w_i)+v_i} & & {j \geq w_i}\ m(i-1,j) & & {j \lt w_i}\ 0 & & i=0 \ or \ j=0 \end{array} \right. $

import numpy as np
n = 5
c = 10
w = [2, 2, 6, 5, 4]
v = [3, 6, 5, 4, 6]

def bag_0_1(w, v, n, c):
  'Time Complexity O(nc)'
  w.insert(0, 0)
  v.insert(0, 0)
  m = np.zeros((n+1,c+1), dtype=np.int32)
  for i in range(1, n+1):
    for j in range(1, c+1):
      if w[i] <= j:
        m[i][j] = max(m[i-1][j], m[i-1][j-w[i]]+v[i])
      else:
        m[i][j] = m[i-1][j]
  x = show(m, n, w, c)
  print('Selection is ' + str(x))
  print('maxValue is ' + str(m[n][c]))

def show(m, n, w, c):
  x = [False for i in range(n)]
  j = c
  for i in range(n, 0, -1):
    if m[i][j] > m[i-1][j]:
      x[i-1] = True
      j -= w[i-1]
  return x  

bag_0_1(w,v,n,c)
最后更新: 5/31/2022, 6:43:40 AM

← Chap3 贪心 →