python经常使用算法（7）——动态计划，回溯法

弁言：从斐波那契数列看动态计划

　　斐波那契数列：Fn = F_n-1 + F_n-2    （ n = 1,2     fib(1) = fib(2) = 1）

演习：运用递归和非递归的要领来求解斐波那契数列的第 n 项

　　代码以下：

# _*_coding:utf-8_*_

def fibnacci(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fibnacci(n - 1) + fibnacci(n - 2)

# 写这个是我们会发明盘算f(5) 要算双方f(4) 
# f(5) = f(4)+f(3)
# f(4) = f(3)+f(2)
# f(3) = f(2)+f(1)
# f(3) = f(2)+f(1)
# f(2) = 1
# 那末同理，算f(6)，我们会盘算两次f(5),三次f(4)....
# 固然不是说一切的递归都邑反复盘算，

# 时刻跟着数字越大，时刻越长
print(fibnacci(10))  # 55


def fibnacci_n_recurision(n):
    f = [0, 1, 1]
    if n > 2:
        for i in range(n - 2):
            num = f[-1] + f[-2]
            f.append(num)
    return f[n]


print(fibnacci_n_recurision(10))

　　为了让我们的压服更有理一些，这里写了一个装潢器，我们经由历程运转时刻看。一样关于上面两个函数，一个递归，一个非递归，我们输入 n=15

# cal_time.py 函数代码以下：

import time

def cal_time(func):
    def wrapper(*args, **kwargs):
        t1 = time.time()
        result = func(*arg, **kwargs)
        t2 = time.time()
        print("%s running time: %s secs." % (func.__name__, t2 - t1))
        return result
    return wrapper
    

运转结果：

fibnacci running time: 0.01000070571899414 secs.
fibnacci_n_recurision running time: 0.0 secs.

　　总结来讲，就是递归异常异常的慢，那非递归相对来讲就比较快了。那为什么呢？就是为什么递归的效力低。我们上面代码也说过了，就是对子问题举行反复盘算了。那第二个函数为什么快呢，我们将每次的盘算结果存在了函数里，直接挪用，防止了反复盘算（固然不是说一切的递归都邑反复盘算子问题），第二个函数我们实在能够看作是动态计划的头脑，从上面的代码来看：

　　动态计划的头脑==递推式+反复子问题

　　怎样邃晓呢，下面继承进修。

1，什么是动态计划

　　动态计划(dynamic programming)是运筹学的一个分支，是求处理议计划历程(decision process)最优化的数学要领。把多阶段历程转化为一系列单阶段问题，运用各阶段之间的关联，逐一求解，建立了处理这类历程优化问题的新要领——动态计划。

1.1，运用动态计划特性

• 1. 求一个问题的最优解 
• 2. 大问题能够分解为子问题，子问题另有堆叠的更小的子问题 
• 3. 团体问题最优解取决于子问题的最优解（状况转移方程） 
• 4. 从上往下剖析问题，从下往上处理问题 
• 5. 议论底层的边境问题

1.2，动态计划的基本头脑

　　若要解一个给定问题，我们须要解其差别部份（即子问题），再兼并子问题的解以得出原问题的解。平常很多子问题异常类似，为此动态计划法试图仅仅处理每个子问题一次，从而削减盘算量：一旦某个给定子问题的解已算出，则将其影象化存储，以便下次须要统一个子问题解之时直接查表。这类做法在反复子问题的数量关于输入的范围呈指数增进时迥殊有用。

　　动态计划最主要的有三个观点：1、最优子构造 2、边境 3、状况转移方程

　　所以我们在进修动态计划要邃晓三件事变：

1，目的问题

2，状况的定义：opt[n]

3，状况转移方差：opt[n] = best_of(opt[n-1], opt[n-2])

 

2，钢条切割问题

　　某公司出卖钢条，出卖价钱与钢条长度直接的关联以下表：

 　　问题：如今有一条长度为 n 的钢条和上面的价钱表，求切割钢条计划，使得总收益最大。

　　剖析：长度为4的钢条的一切切割计划以下：（C计划最优）

 　　思索：长度为 n 的钢条的差别切割计划有几种？

　　下面是当长度为n的时刻，最优价钱的表格（ i 示意长度为 n ，r[i] 示意最优价钱）

2.1，递推式处理钢条切割问题

　　设长度为 n 的钢条切割后最优收益值为 Rn，能够获得递推式：

　　第一个参数Pn 示意不切割

　　其他 n-1个参数离别示意别的 n-1种差别切割计划，对计划 i=1,2,...n-1 将钢条切割为长度为 i 和 n-i 两段

　　计划 i  的收益为切割两段的最优收益之和，考核一切的 i，挑选个中收益最大的计划

2.2，最优子构造处理钢条切割问题

　　能够将求解范围为 n 的原问题，划分为范围更小的子问题：完成一次切割后，能够将发生的两段钢条算作两个自力的钢条切割问题。

　　组合两个子问题的最优解，并在一切能够的两段切割计划中拔取组合收益最大的，组成原问题的最优解。

　　钢条切割满足最优子构造：问题的最优解由相关子问题的最优解组合而成，这些子问题能够自力求解。

　　钢条切割问题还存在更简朴的递归求解要领：

• 从钢条的左侧切割下长度为 i 的一段，只对右侧剩下的一段继承举行切割，左侧的不再切割
• 递推式简化为：
• 不做切割的计划就可以够形貌为：左侧一段长度为 n，收益为 pn，剩下一段长度为0，收益为 r0=0.

2.3，钢条切割问题——自顶向下递归代码及其时刻庞杂度

　　代码以下：

def _cut_rod(p, n):
    if n == 0:
        return 0
    q = 0
    for i in range(1, n+1):
        q = max(q, p[i] + _cut_rod(p, n-i))
    return q

　　以下图所示，当钢条的长度增添时刻，切割的计划次数跟着指数增添。当n=1的时刻切割1次，n=2的时刻切割2次，n=3的时刻切割4次，n=4的时刻切割8次。。。。

　　所以：自顶向下递归完成的时刻庞杂度为 O(2ⁿ)

2.4，两种要领的代码完成

　　代码以下：

# _*_coding:utf-8_*_
import time


# 给递归函数一个装潢器，它就递归的装潢！！ 所以为了防备如许我们再套一层即可
def cal_time(func):
    def wrapper(*args, **kwargs):
        t1 = time.time()
        result = func(*args, **kwargs)
        t2 = time.time()
        print('%s running time : %s secs' % (func.__name__, t2 - t1))
        return result

    return wrapper


# p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 21, 23, 24, 26, 27, 28, 30, 33, 36, 39, 40]
p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]


def cut_rod_recurision_1(p, n):
    if n == 0:
        return 0
    else:
        res = p[n]
        for i in range(1, n):
            res = max(res, cut_rod_recurision_1(p, i) + cut_rod_recurision_1(p, n - i))
        return res


# print(cut_rod_recurision_1(p, 9))


def cut_rod_recurision_2(p, n):
    if n == 0:
        return 0
    else:
        res = 0
        for i in range(1, n + 1):
            res = max(res, p[i] + cut_rod_recurision_2(p, n - i))
        return res


# print(cut_rod_recurision_2(p, 9))

@cal_time
def c1(p, n):
    return cut_rod_recurision_1(p, n)

@cal_time
def c2(p, n):
    return cut_rod_recurision_2(p, n)


print(c1(p, 10))
print(c2(p, 10))
'''
c1 running time : 0.02000117301940918 secs
30
c2 running time : 0.0010001659393310547 secs
30
'''

　　我们经由历程盘算时刻，发明第二个递归要领显著比第一个递归要领快很多。那末是不是另有更简朴的要领呢？肯定有，下面进修动态计划。

2.5，动态计划处理钢条切割问题

　　递归算法由于反复求解雷同子问题，效力极低。纵然优化事后的递归也效力不高。那这里运用动态计划。

　　动态计划的头脑：

1. 每个子问题只求解一次，保存求解结果
2. 以后须要此问题时，只须要查找保存的结果

　　动态计划解法代码：

def cut_rod_dp(p, n):
    r = [0 for _ in range(n+1)]
    for j in range(1, n+1):
        q = 0
        for i in range(1, j+1):
            q = max(q, p[i]+r[j-i])
        r[j] = q
    return r[n]

　　或许便于邃晓如许：

def cut_rod_dp(p, n):
    r = [0]
    for i in range(1, n+1):
        res = 0
        for j in range(1, i+1):
            res = max(res, p[j]+r[i-j])
        r.append(res)
    return r[n]

　　时刻庞杂度： O(n²)

2.6，钢条切割问题——重构解

　　怎样修正动态计划算法，使其不仅输出最优解，还输出最优切割计划？

　　关于每个子问题，保存切割一次时左侧切下的长度

　　下图为r[i] 示意最优切割的价钱，s[i]示意切割左侧的长度。

 　　代码以下：

def cut_rod_extend(p, n):
    r = [0]
    s = [0]
    # 这个轮回的意义是从底向上盘算
    for i in range(1, n+1):
        res_r = 0  # 用来纪录价钱的最优值
        res_s = 0  # 用来纪录切割左侧的最优长度
        for j in range(1, i+1):
            if p[j] + r[i-j] > res_r:
                res_r = p[j] + r[i-j]
                res_s = j
        r.append(res_r)
        s.append(res_s)
    return r[n], s

def cut_rod_solution(p, n):
    r, s = cut_rod_extend(p, n)
    ans = []
    while n>0:
        ans.append(s[n])
        n-= s[n]
    return ans


print(cut_rod_extend(p, 10))
# (30, [0, 1, 2, 3, 2, 2, 6, 1, 2, 3, 10])
print(cut_rod_solution(p, 9))
# [3, 6]

2.7，什么问题能够运用动态计划要领？

　　1，最优子构造

• 原问题的最优解中触及多少个子问题
• 在肯定最优解运用那些子问题时，须要斟酌多少种挑选

　　2，堆叠子问题

 

3，最长大众子序列

　　一个序列的子序列是在该序列中删去多少元素后获得的序列。比方：ABCD 和 BDF 都是 ABCDEFG 的子序列。

　　在一个序列中，子串是一连的，子序列能够不一连。

　　最常大众子序列（LCS）问题：给定两个序列 X 和 Y，求 X 和 Y 长度最大的大众子序列。比方 X = ABBCBDE，  Y = DBBCDB ，  LCS(X, Y) = BBCD 。

 　　运用场景：字符串类似度比对。

3.1，最长大众子序列的思绪——暴力穷举法

　　当X的长度为m，Y的长度为n，则时刻庞杂度为： 2^(m+n) 

　　虽然我们最早想到的时暴力穷举法，然则很显然，由其时刻庞杂度可知，这是不可取的。

3.2，最长大众子序列的思绪——LCS是不是具有最优子构造性子

　　比方：请求 a = ABCBDAB  与 b = BDCABA 的LCS：

　　由于末了一名 B！= A 

　　因而LCS（a, b）应当来源于  LCS（a[: -1], b）与 LCS(a, b[: -1]) 中更大的哪个。

 　　最优解的递推式以下：

 　　c[i,j] 示意 Xi 和 Yj 的LCS 长度。

3.3，最长大众子序列的代码

 　　代码以下：

def lcs_length(x, y):
    m = len(x)
    n = len(y)
    c = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if x[i - 1] == y[j - 1]:  # i，j位置上的字符婚配的时刻，来自于左上方
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])

    # 逐行打印
    for _ in c:
        print(_)
    return c[m][n]


# 最优值出来了，然则历程没有出来，也就是只需最长，不知道大众子序列
# print(lcs_length("ABCBDAB", "BDCABA"))
'''
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 1, 1]
[0, 1, 1, 1, 1, 2, 2]
[0, 1, 1, 2, 2, 2, 2]
[0, 1, 1, 2, 2, 3, 3]
[0, 1, 2, 2, 2, 3, 3]
[0, 1, 2, 2, 3, 3, 4]
[0, 1, 2, 2, 3, 4, 4]
4
'''


def lcs(x, y):
    m = len(x)
    n = len(y)
    c = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    # 1左上方 2上方 3 左方
    b = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if x[i - 1] == y[j - 1]:  # i，j位置上的字符婚配的时刻，来自于左上方
                c[i][j] = c[i - 1][j - 1] + 1
                b[i][j] = 1
            elif c[i - 1][j] > c[i][j - 1]:  # 来自于上方
                c[i][j] = c[i - 1][j]
                b[i][j] = 2
            else:
                c[i][j] = c[i][j - 1]
                b[i][j] = 3

    return c[m][n], b


# c, b = lcs("ABCBDAB", "BDCABA")
# for _ in b:
#     print(_)
'''
[0, 0, 0, 0, 0, 0, 0]
[0, 3, 3, 3, 1, 3, 1]
[0, 1, 3, 3, 3, 1, 3]
[0, 2, 3, 1, 3, 3, 3]
[0, 1, 3, 2, 3, 1, 3]
[0, 2, 1, 3, 3, 2, 3]
[0, 2, 2, 3, 1, 3, 1]
[0, 1, 2, 3, 2, 1, 3]
'''


def lcs_trackback(x, y):
    c, b = lcs(x, y)
    i = len(x)
    j = len(y)
    res = []
    while i > 0 and j > 0:
        if b[i][j] == 1:  # 来自左上方 =》婚配
            res.append(x[i - 1])
            i -= 1
            j -= 1
        elif b[i][j] == 2:  # 来自上方=》 不婚配
            i -= 1
        else:  # ==3  来自左方 =》不婚配
            j -= 1
    # 由因而回溯法，所以倒着写的，我们末了须要reverse返来
    return "".join(reversed(res))

print(lcs_trackback("ABCBDAB", "BDCABA"))
# BDAB

　　

4，最大子序和

　　给定一个整数数组 nums ，找到一个具有最大和的一连子数组（子数组起码包含一个元素），返回其最大值。

　　示例：输入：[-2, 1, -3, 4, -1, 2, 1, -5, 4]   输出：输出：6

　　思绪：我们起首剖析问题，为什么最大和的一连子数组不包含其他的元素而是这几个呢？假如我们想在现有的基本上去扩大当前一连子数组，相邻的元素是肯定要被到场的，而相邻元素能够会减损当前的和。

4.1，遍历法

　　算法历程：遍历数组，用 sum 去保护当前元素加起来的和，当 sum 涌现小于0的状况时，我们把它设为0，然后每次都更新全局最大值。

 def maxSubArray(self, nums: List[int]) -> int:
        sum = 0
        MaxSum = nums[0]
        for i in range(len(nums)):
            sum += nums[i]
            MaxSum = max(sum, MaxSum)
            if sum <0:
                sum = 0
        return MaxSum

　　那看起来这么简朴，怎样邃晓呢？一最先思索数组是个空的，我们每次选一个 nums[i] 到场当前数组中新增了一个元素，也就是用动态的眼光去斟酌。代码简朴为什么就可以到达结果呢？

　　我们举行的加和是根据递次来的，当我们i 选出来后，到场当前 sum，这时刻有两种状况：

1，假定我们当前 sum 一致都大于零，那每一次盘算的 sum 都是包含开首元素的一端子序列。

2，涌现小于0的时刻，申明我们当前子序列第一次小于零，所以我们如今构成的一连数组不能包含之前的一连子序了，因而扬弃他们，从新最先新的子序。

4.2，动态计划

　　设sum[i]为以第i个元素末端的最大的一连子数组的和。假定关于元素i，一切以它前面的元素末端的子数组的长度都已求得，那末以第i个元素末端且和最大的一连子数组实际上，要么是以第i-1个元素末端且和最大的一连子数组加上这个元素，要么是只包含第i个元素，即sum[i]= max(sum[i-1] + a[i], a[i])。能够经由历程推断sum[i-1] + a[i]是不是大于a[i]来做挑选，而这实际上等价于推断sum[i-1]是不是大于0。由于每次运算只须要前一次的结果，因而并不须要像平常的动态计划那样保存之前一切的盘算结果，只须要保存上一次的即可，因而算法的时刻和空间庞杂度都很小。

　　代码以下：

def maxSubArray4(self, nums: List[int]) -> int:
    length = len(nums)
    for i in range(1, length):
        # 当前值的大小与前面的值之和比较，若当前值更大，则取当前值，舍弃前面的值之和
        subMaxSum = max(nums[i]+nums[i-1], nums[i])
        # 将当前和最大的赋给 nums[i]， 新的nums 存储的为什么值
        nums[i] = subMaxSum
    return max(nums)

　　只需遍历一遍。nums[i]示意的是以当前这第i号元素末端（看清了肯定要包含当前的这个i）的话，最大的值不过就是看以i-1末端的最大和的子序能不能加上我这个nums[i]，假如nums[i]>0的话，则加上。注重我代码中没有显式地去如许推断，不过我的Max表达的就是这个意义，然后我们把nums[i]肯定下来。

　　动态计划须要和回溯法搭配着运用，动态计划只担任求最优解，而回溯轨则能够找到最优值的途径。

5，回溯法

　　回溯法是一种选优搜刮法，按选优前提向前搜刮，以到达目的。但当探究到某一步时，发明本来挑选并不优或达不到目的，就退回一步从新挑选，这类走不通就退回再走的手艺为回溯法，而满足回溯前提的某个状况的点称为 “回溯点”。很多庞杂的，范围较大的问题都能够运用回溯法，有“通用解题要领”的美称。回溯法有“通用的解题法”之称，也叫试探法，它是一种体系的搜刮问题的解的要领。简朴来讲，回溯法采纳试错的要领处理问题，一旦发明当前步骤失利，回溯要领就返回上一个步骤，挑选另一种计划继承试错。

5.1  回溯法的基本头脑

　　从一条路往前走，能进则进，不能进则退返来，换一条路再试。

5.2  回溯法的平常步骤

1，定义一个解空间（子集树，排序树二选一）

2，运用适用于搜刮的要领构造解空间

3，运用深度优先法搜刮解空间

4，运用剪枝函数防止移动到不能够发生解的子空间

5.3  回溯法针对问题的特性

　　回溯算法针对的大多数问题有以下特性：问题的答案有多个元素（可向下成走迷宫是有多个决议），答案须要一些束缚（比如数独），寻觅答案的体式格局在每个步骤雷同。回溯算法逐渐构建答案，并在肯定候选元素不满足束缚后马上摒弃候选元素（一旦碰墙就返回），直到找到答案的一切元素。　　

5.4回溯法问题——查找单词

　　问题形貌：你玩过报纸上那种查找单词的游戏吗？就是那种在一堆字母中横向或竖向找出单词的游戏。小明在玩一个和谁人很像的游戏，只不过如今不仅能够上下左右衔接字母，还能够拐弯。如图所示，输入world，就会输出“找到了”。

 

 

5.5  回溯法问题——遍历一切的分列体式格局

　　问题形貌：小米近来有四本想读的书：《赤色的北京》，《黄色的巴黎》，《蓝色的夏威夷》，《绿色的哈萨里》，假如小明每次只能从藏书楼借一本书，他一共有多少种借书的递次呢？

 　　回溯法是一种经由历程探究一切能够的候选解来找出所欲的解的算法。假如候选解被确认，不是一个解的话（或许最少不是末了一个解），回溯算法会经由历程在上一步举行一些变换排期该解。即回溯而且再次尝试。

　　这里有一个回溯函数，运用第一个整数的索引作为参数  backtrack(first)。

1，假如第一个整数有索引 n，意味着当前分列已完成。

2，遍历索引 first 到索引 n-1 的一切整数 ，则：

• 在分列中安排第 i 个整数，即 swap(nums[first], nums[i])
• 继承生成从第 i 个整数最先的一切分列：backtrack(first +1)
• 如今回溯，经由历程 swap(nums[first], nums[i]) 复原。

 　　代码以下：

class Solution:
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        def backtrack(first = 0):
            # if all integers are used up
            if first == n:  
                output.append(nums[:])
            for i in range(first, n):
                # place i-th integer first 
                # in the current permutation
                nums[first], nums[i] = nums[i], nums[first]
                # use next integers to complete the permutations
                backtrack(first + 1)
                # backtrack
                nums[first], nums[i] = nums[i], nums[first]
        
        n = len(nums)
        output = []
        backtrack()
        return output

　　便于邃晓的代码以下：

class solution:
    def solvepermutation(self, array):
        self.helper(array, [])

    def helper(self, array, solution):
        if len(array) == 0:
            print(solution)
            return
        for i in range(len(array)):
            newarray = array[:i] + array[i + 1:]  # 删除书籍
            newsolution = solution + [array[i]]  # 到场新书
            self.helper(newarray, newsolution)  # 寻觅盈余对象的分列组合


solution().solvepermutation(["红", "黄", "蓝", "绿"])

　　要领二：走捷径（直接运用Python的库函数，迭代函数itertools）

li = ['A', 'B', 'C', 'D']
def solutoin(li):
    import itertools
    res = list(itertools.permutations(li))
    return len(res)

　　

5.6  回溯法问题——典范问题的组合

　　问题形貌：小明想上两门选修课，他有四种挑选：A微积分，B音乐，C烹调，D设想，小明一共有多少种差别的选课组合？

 　　固然第一个要领就是走捷径！，直接运用python的库函数itertools举行迭代：

li = ['A', 'B', 'C', 'D']
def solutoin(li):
    import itertools
    res = list(itertools.permutations(li, 2))
    return len(res)

　　下面最先回溯法的进修。

class solution():
    def solvecombination(self, array, n):
        self.helper(array, n, [])

    def helper(self, array, n, solution):
        if len(solution) == n:
            print(solution)
            return
        for i in range(len(array)):
            newarray = array[i + 1:]  # 建立新的课程列表，更新列表，即选过的课程不能再选
            newsolution = solution + [array[i]]  # 将科目到场新的列表组合
            self.helper(newarray, n, newsolution)


solution().solvecombination(["A", "B", "C", "D"], 2)

　　

5.7  回溯法问题——八皇后问题

　　问题形貌：保安担任人小安面对一个困难，他须要在一个8x8千米的地区里建筑8个保安站点，并确保每一行、每一列和每一条斜线上都只需一个保安站点。苦恼的小安试着尝试安排了很多遍，但每一次都不符合请求。小安乞助程序员小明，没过多久小明就把好几个安排计划（实际上，这个问题有92种答案）发给了小安，个中包含下面实行结果截图，试问小明是怎样做到的。

 

6，算法综合功课

　　这是一切的算法学完后的综合功课，固然这也是算法进修的一个总结。固然下面的问题我都有触及，这里不做逐一解答。

1. 完成以下算法而且编写解题报告，解题报告中须要给出问题申明、本身对
问题的邃晓、解题思绪、对算法的申明和邃晓、以及算法庞杂度剖析等内容

2. 完成冒泡排序、插进去排序、疾速排序和合并排序

3. 以尽量多的要领处理2-sum问题并剖析其时刻庞杂度：给定一个列表和
一个整数，从列表中找到两个数，使得两数之和即是给定的数，返回两个数
的下标。问题保证有且只需一组解

4. 封装一个双链表类，并完成双链表的建立、查找、插进去和删除

5. 运用最少一种算法处理迷宫寻路问题

6. 运用动态计划算法完成最长大众子序列问题

　　

传送门：代码的GitHub地点：https://github.com/LeBron-Jian/BasicAlgorithmPractice 

 

参考分治与动态计划参考文献：https://blog.csdn.net/weixin_41250910/article/details/94502136

https://blog.csdn.net/weixin_43482259/article/details/97996658