《算法的乐趣》3.算法设计的常用思想------python

本文主要是介绍《算法的乐趣》3.算法设计的常用思想------python，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.贪婪法(greedy algorithm)

基本思想

a.建立对问题精确描述的数学模型，包括定义最优解的模型；
b.将问题分解为一系列子问题，同时定义子问题的最优解结构；
c.应用贪心原则确定每个子问题的局部最优解，并根据最优解的模型，用子问题的局部最优解堆叠出全局最优解。

在任何算法中，只要在某个阶段使用了只考虑局部最优情况的选择策略，都可以理解为使用了贪婪算法。

例子：0-1背包问题

有$N$件物品和一个承重为$C$的背包，每件物品重量$w_i$,价值$p_i$,求将哪几件物品装入背包可使这些物品在重量总和不超过$C$的情况下价值总和最大。
三种贪心策略：价值、重量和价值密度。

w = [35, 30, 60, 50, 40, 10, 25]
p = [10, 40, 30, 50, 35, 40, 30]
C = 150

def select_value(C, w, p):"""根据价值来选择最优。args:C: 背包总重量w: 物品重量P: 物品价值return:status: 物品的选中状态total_values: 装入的总价值load_weigth: 装入的总重量"""number = len(w)status = [0] * numberload_weigth = 0total_values = 0# 价值排序 sorted返回p的从大到小的索引argsort_p = sorted(range(number), key=lambda k: p[k], reverse=True)# 此处可以改进，将价值排序作为第一排序目标，相同的时候将重量作为第二排序目标for i in range(number):# 最大的价值开始循环，就不在重复了if w[argsort_p[i]] > C:continueload_weigth += w[argsort_p[i]]total_values += p[argsort_p[i]]status[argsort_p[i]] = 1# 问题规模减小C -= w[argsort_p[i]]return status, total_values, load_weigthstatus, total_values, load_weigth = select_value(C, w, p)
print('物品的选中状态为：',status)
print('装入的总价值为：',total_values)
print('装入的总重量为：',load_weigth)

物品的选中状态为： [0, 1, 0, 1, 1, 1, 0]
装入的总价值为： 165
装入的总重量为： 130

def select_weigth(C, w, p):"""根据重量来选择最优。args:C: 背包总重量w: 物品重量P: 物品价值return:status: 选中的状态total_values: 总价值load_weigth: 总重量"""number = len(w)status = [0] * numberload_weigth = 0total_values = 0# 重量排序argsort_w = sorted(range(number), key=lambda k: w[k])for i in range(number):# 最小重量开始循环，就不在重复if w[argsort_w[i]] > C:continueload_weigth += w[argsort_w[i]]total_values += p[argsort_w[i]]status[argsort_w[i]] = 1# 问题规模减小C -= w[argsort_w[i]]return status, total_values, load_weigthstatus, total_values, load_weigth = select_weigth(C, w, p)
print('物品的选中状态为：',status)
print('装入的总价值为：',total_values)
print('装入的总重量为：',load_weigth)

物品的选中状态为： [1, 1, 0, 0, 1, 1, 1]
装入的总价值为： 155
装入的总重量为： 140

def select_value_density(C, w, p):"""根据价值密度来选择最优。args:C: 背包总重量w: 物品重量P: 物品价值return:status: 选中的状态total_values: 总价值load_weigth: 总重量"""number = len(w)status = [0] * numberload_weigth = 0total_values = 0# 价值密度排序w_p = [p[i]/w[i] for i in range(number)]argsort_w_p = sorted(range(number), key=lambda k: w_p[k], reverse=True)for i in range(number):# 最优价值密度开始循环，就不在重复if w[argsort_w_p[i]] > C:continueload_weigth += w[argsort_w_p[i]]total_values += p[argsort_w_p[i]]status[argsort_w_p[i]] = 1# 问题规模减小C -= w[argsort_w_p[i]]return status, total_values, load_weigthstatus, total_values, load_weigth = select_value_density(C, w, p)
print('物品的选中状态为：',status)
print('装入的总价值为：',total_values)
print('装入的总重量为：',load_weigth)

物品的选中状态为： [1, 1, 0, 1, 0, 1, 1]
装入的总价值为： 170
装入的总重量为： 150

2.分治法

基本思想

a.分解：将问题分解为若干个规模较小，相互独立且与原问题形式相同的子问题，确保各个子问题的解具有相同的子结构。
b.解决：如果上一步分解得到的子问题可以解决，则解决这些子问题，否则，对每个子问题使用和上一步相同的方法再次分解，然后求解分解后的子问题，这个过程可能是一个递归的过程。
c.合并：将上一步解决的各个子问题的解通过某种规则合并起来，得到原问题的解。

难点

如何将子问题分解，并且将子问题的解合并出原始问题的解，不同的问题有不同的处理方式。
在数学上，只要能用数学归纳法证明的问题，一般都可以用分治法解决。

应用：快速排序算法，快速傅里叶变换，karatsuba乘法

大整数karatsuba乘法算法

普通乘法的算法复杂度$O(n^2)$,karatsuba乘法的复杂度$O(3n^{1.585})$
将$x$和$y$两个大整数分解为：
$$x=x_0\ast 10^{half}+x_1$$
$$y=y_0\ast 10^{half}+y_1$$
$$x\ast y=z_0\ast 10^{half\ast 2}+z_1\ast 10^{half}+z_2$$
$$z_0=x_0\ast y_0$$
$$z_2=x_1\ast y_1$$
$$z_1=x_0\ast y_1+x_1\ast y_0=(x_0+x_1)(y_0+y_1)-z_0-z_2$$

def karatsuba(x, y):"""karatsuba大数相乘args：x: 整数y: 整数return:z: 相乘的结果"""# 终止条件if (len(str(x)) == 1 or len(str(y)) == 1):return x*yn = max(len(str(x)), len(str(y)))half_n = n//2# 分割x0 = x // 10**(half_n)x1 = x % 10**(half_n)y0 = y // 10**(half_n)y1 = y % 10**(half_n)# 根据公式推导可得z0 = karatsuba(x0, y0)z2 = karatsuba(x1, y1)z1 = karatsuba((x0+x1), (y0+y1)) - z0 - z2z = z0*10**(half_n*2) + z1*10**(half_n) + z2return zx = 1651231452316845
y = 1564236842153481231
print(karatsuba(x, y))
print(x*y)

2582917072636608242170997172636195
2582917072636608242170997172636195

3.动态规划

动态规划适合求解多阶段决策问题的最优解，也可用于含有线性或非线性递推关系的最优解问题。但这些问题都必须满足最优化原理和子问题的无后向性。

a.最优化原理：不管之前决策是否是最优策略，都必须保证从现在开始的决策时在之前决策基础上的最优策略。
b.无后向性（无后效性）：每个阶段的决策仅受之前决策的影响，但是不影响之后个阶段的决策。

动态规划也是对问题进行分解，通过求解小规模的子问题再反推原问题的解。不同于分治法，它是沿着决策的阶段划分子问题的，各个子问题之间并不是相互独立的。

例子：装配站问题、背包问题、最长公共子序列问题。

基本思想：

a.定义最优子问题：确定问题的优化目标以及如何决策最优解，并对决策过程划分阶段。阶段就是一个问题从开始到解决需要经过的环节。
b.定义状态：状态既是决策的对象，也是决策的结果，对每个阶段来说，对起始状态施加状态，使得状态发生改变，得到决策的结果状态。状态的定义是建立在子问题定义的基础上的，因此必须满足无后向性。
c.定义决策和装填转换方程：决策就是能使状态发生转变的选择动作，如果选择动作有多个，则决策就是取其中能使得阶段结果最优的那一个。状态转换方程式描述状态转换关系的一系列等式，也就是从n-1阶段到n阶段的演化规律。
d.确定边界条件：递归终结条件。初始条件

字符串的编辑距离

两个字符串的相似度为将一个字符串转换为另外一个字符串时需要付出的代价，也就是利用字符操作（删除、插入、修改），把字符串A转换成字符串B所需要的最少操作数。
不同的转换方法有不同的操作数，其中最少的操作数就是字符串的编辑距离。

状态递推关系的动态规划算法

由状态转换关系入手，假设$str1$有$n$个字符，%str2%有$m$个字符，$str1$到%str2%的最小编辑距离。其子问题定义为$str1$前$i$个字符到$str2$前$j$个字符的最小编辑距离，将其表示为状态$d[i,j]$。
最多有$n\ast m$个状态，引入备忘录来记录每一个状态的值。

递推关系$d[i,j]$有两种情况，即$$d[i,j]=d[i,j]+0,str1[i]=str2[j]$$和
$$d[i,j]=min(d[i,j-1]+1,d[i-1,j]+1,d[i-1,j-1]+1),str1[i]\ne str2[j]$$

边界条件为：$d[i,0]=i,d[0,j]=0$

def edit_distance(str1, str2):len_str1 = len(str1) + 1len_str2 = len(str2) + 1# 初始化，备忘录，来记录所有的状态matrix = [[0] * (len_str2) for i in range(len_str1)]for i in range(len_str1):for j in range(len_str2):# 初始化矩阵if i == 0 and j == 0:matrix[i][j] = 0elif i == 0 and j > 0:matrix[0][j] = jelif i > 0 and j == 0:matrix[i][0] = i# 状态转换elif str1[i - 1] == str2[j - 1]:matrix[i][j] = matrix[i - 1][j - 1]else:matrix[i][j] = min(matrix[i - 1][j - 1] + 1, matrix[i][j - 1] + 1, matrix[i - 1][j] + 1)print(matrix)return matrix[len_str1 - 1][len_str2 - 1]str1 = 'sny'
str2 = 'sjm'
d = edit_distance(str1, str2)
print(d)

[[0, 1, 2, 3], [1, 0, 1, 2], [2, 1, 1, 2], [3, 2, 2, 2]]
2

4.解空间的穷举搜索

步骤：

a.确定问题的解（或状态）的定义，解空间的范围以及正确解的判定条件。
b.根据解空间的特点选择搜索策略，一一检验解空间中的候选解是否正确，必要时可辅助一些剪枝算法，排除一些冥想不可能是正确解的检验过程，提高穷举的效率。

解空间的定义：就是可能的候选解的一个约束范围，确定问题的解就在这个范围内，将搜索策略应用到这个约束范围就可找到问题的解。解空间的结构可能是线性表、集合、树、或者图。

穷举解空间的策略：
a.盲目搜索算法：广度优先搜索和深度优先搜索
b.启发式搜索算法：利用额外信息直接跳过一些状态，避免盲目的机械式的搜索
c.剪枝策略：
d.搜索算法的评估和收敛

Google方程式

这篇关于《算法的乐趣》3.算法设计的常用思想------python的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---