程序或者是函数抽象和面向对象这两种方法可以用于将代码分割成各个部分,并且使他们之间的相互作用最小化,使我们能够在某段时间内只专注于几个特定概念。

归纳,递归以及归简 也属于这类抽象原则。

  • 归纳:被用于证明某个语句对于某种大型对象类是否成立
  • 递归:用于函数自我调用时候
  • 归简:将某一个问题转换成另外一个问题

简单示例

通过某种途径改变问题条件,使其可以用某种我们已知的方法来解决,这一步差不多是解决问题过程中的核心部分。

下面是一段找出数字列表中彼此接近但是不相等的数的算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from random import randrange
import time
seq = [randrange(10**10) for i in range(100)]
t0 = time.time()
dd = float('inf')
for x in seq:
for y in seq:
if x == y: continue
d = abs(x-y)
if d < dd:
xx, yy, dd = x, y, d
print(xx, yy)
t1 = time.time()
print(t1 - t0)
# 算法2
seq.sort()
dd = float('inf')
for i in range(len(seq)-1):
x, y = seq[i], seq[i+1]
if x == y: continue
d = abs(x-y)
if d < dd:
xx, yy, dd = x, y, d
print(xx, yy)
t2 = time.time()
print(t2 - t1)

算法2先对序列进行排序,已经排序的序列中最接近的两个数必然是相邻的,所以新的运行时间是线性对数级的,由排序操作主导。实际运行结果第一个算法:0.0051s,第二个算法:0.000097s。实际上是将问题分割成了排序和扫描已经排序的序列两部分。

归纳

最主要的一步是要先假设P(n-1)已经成立,意味着我们得从已知或者事先假设的,与n-1相关的信息开始,逐步构建出与n相关的情况。具体的就不多描述了。

对于一个带根节点的二叉树来说,内部每个节点下面都应该有两个子节点,当然,由于它并不需要是完全平衡的,所以叶节点可以有不同的深度,如果现在该数有n个叶节点,那么内部节点应该有多少呢?答案是n-1

  • 解决方法
1
2
3
4
5
假设0,1,2度的节点分别为n0,n1,n2,二叉树的节点总数为T
那么T=n0+n1+n2
如果按照边计算T=n1+2*n2+1 (1就是根节点,没有边引入它,但是是一个节点)
根据两式,并且n1=0,因为每个节点下面都有两个子节点
所以得n2=n0-1
  • 归纳证明

从n=3开始,这时候有2个内部节点和3个叶子节点,这一点Python基础教程75页处有误,它应该把n当成了总节点数了,现在假设叶子节点有n-1时候,内部节点数为n-2,现在要做得事情就是将归纳步骤推导到n上面。

在树上添加叶节点貌似有点困难,所以反着来,从n个叶节点发推到n-1上面,在含有n个叶节点得树上,将其中一个叶节点连同父节点也就是内部节点一并移除,那么剩下得两个节点连接起来就是一个含有n-1个叶节点以及n-2个内部节点得树结构了,原来得树上多了一个叶节点和内部节点,也就是 有n个叶节点和n-1个内部节点。

递归

经过一中午的研究,终于弄明白了书上所阐述的用于讲解递归的棋盘问题

棋盘问题描述:正方形的棋盘,而且边长是2的指数幂,那么有一块角上缺了一个方格,他要问能不能用L形砖来拼出这么一个棋盘。L形砖就是三块小正方形砖组合而成的,想象一下。。

刚开始没有思路,想了想应该要使用递归,因为可以分解成子问题,然后去解决。想要使用归纳法(递归),就必须要将归简法用在不同规模的相同问题实例之间。所以递归的思路如下:比如一个8*8棋盘,可以分成4个4*4的棋盘,一个棋盘是差一个角的,这样下去只要将一个L形砖放在中间,就会使三块子棋盘各自缺失一个角,然后递归下去,只要能够用L形砖拼出这三块子棋盘,拼接完成后,缺失的方格自然就完整了。

下面是这个问题的一个解决程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def cover(board, lab=1, top=0, left=0, side=None):
# 初始化的时候获取棋盘大小
if side is None:
side = len(board)
# 获取子棋盘的大小
s = side // 2
# 子棋盘的内部方块和外部方块的坐标,内部比外部少1的原因是内部要定位到中间,
# 要加上棋盘大小,数组从0开始,所以少一个,外部不需要加,直接就是正确的坐标,
# side-1也是为了定位到正确的坐标上
offsets = (0, -1), (side-1, 0)
# 进行4次判断,将问题切分成4个子棋盘进行求解
for dy_outer, dy_inner in offsets:
for dx_outer, dx_inner in offsets:
# 在这里判断顶点位置上是否还没有摆放L砖
if not board[top+dy_outer][left+dx_outer]:
# 没有摆放的话,将中间部分摆上L形砖,相当于切分问题
# 这里阐述是直接摆L砖,实际操作是一个坐标一个坐标来的
board[top+s+dy_inner][left+s+dx_inner] = lab
lab += 1
# 进行4次递归调用,将上面切分的4个子棋盘问题一一解决
if s > 1:
for dy in [0, s]:
for dx in [0, s]:
# top,left的作用就是将坐标原点按照现在处理子棋盘的位置放在其左上角
# 标签的话,每放置一块L砖,就+1
lab = cover(board, lab, top+dy, left+dx, s)
return lab
  • 递归法只是归纳法的一种镜像

归纳法中,通常会从基本情况着手,并进一步证明相关的归纳步骤,将其推进到目标问题的整体规模n。而递归就是从整个问题出发,将其规模为n-1的子问题委托给某个递归调用,并且等待其返回结果,然后将子解决方案扩展成整体解决方案。

有时候将递归实现成某种迭代操作可能会更好一点,因为迭代操作的开销通常要比递归少一点,而且速度更快。还有一种可能是递归会超过其最大递归深度。

  • 尾递归优化

在一些函数式编程语言中,尾递归优化会修改前面的函数(这种函数最后一句是递归调用),让它们不再受栈深度的限制,一般做法是将这些递归调用重写成内部循环。

插入排序

插入排序的主要思想是假设前n-1个元素已经完成排序了,将第n个元素插入到正确的位置上。递归到最左侧的两个元素,排好序,然后返回,这样就实现了上述的递归原理。代码如下:

1
2
3
4
5
6
7
8
9
def ins_sort_rec(seq, i):
if i == 0: return # 递归到最左侧,然后返回,比较第一个和第二个元素
# 开始递归
truetrue ins_sort_rec(seq, i-1)
truetrue # 返回后,检查目前位置的元素是否在正确位置,否则将一个个比较,挪到正确位置
truetrue j = i
truetrue while j > 0 and seq[j] < seq[j-1]:
truetrue seq[j], seq[j-1] = seq[j-1], seq[j]
truetrue j -= 1

然后迭代版的插入排序就是,从序列开始进行迭代,然后对每个位置进行检查,是否有序,不有序则向前一一比较,直到找到正确的位置

1
2
3
4
5
6
def ins_sort(seq):
for i in range(1, len(seq)):
truetrue j = i
truetrue while j > 0 and seq[j] < seq[j-1]:
truetrue seq[j], seq[j-1] = seq[j-1], seq[j]
truetruetruetruetruetrue j -= 1

选择排序

选择排序的主要思想是先找到最大的元素,然后放在n的位置上,然后递归去排序剩下的元素。也就是说,先找到最大的元素,如果从小到大排序,那么就放到最后面,然后下来找其余元素的最大者,放在倒数第二个,以此类推。以此类推这个词就是一种递归。

1
2
3
4
5
6
7
8
9
10
11
def sel_sort_rec(seq, i):
if i == 0: return
true# 先在i个元素中找到最大元素,放在合适的位置,然后再去搞剩下的元素
truemax_j = i
truefor j in range(i):
true if seq[j] > seq[max_j]:
truetrue max_j = i
true# 找到最大元素后,将最大元素放在合适的位置,也就是目前未排序元素的最后一个
trueseq[i], seq[max_j] = seq[max_j], seq[i]
true# 递归搞剩下的i-1个元素
truesel_sort_rec(seq, i-1)

迭代版本的话,就是从尾部开始,也就是递归中的从i开始,然后找到最大的元素,然后交换,然后去找剩下的元素中最大的。

1
2
3
4
5
6
7
def sel_sort(seq):
for i in range(len(seq)-1, 0, -1):
true max_j = i
truetruefor j in range(i):
truetrue if seq[j] > seq[max_j]:
truetruetrue max_j = j
truetrueseq[i], seq[max_j] = seq[max_j], seq[i]

这两个例子就能看出来,迭代和递归的区别。

基于归纳法(递归法)的算法设计

最大排列

设计算法之前,首先要将问题具体化,这个问题可以看成这些人和座位当中形成的一对一映射关系子集或者排列。对于这个问题,可以思考下归纳法,看是否能够将问题从规模n减少到规模n-1。

在这个问题中,一个人最多只能被安排到一个位置上,所以不应该有空座位,就是没有想要的座位,因为只要有这样的情况,就会出现至少两个人争一个座位,所以就应该排除这种情况。如果排除了空座位,那么目前在这个座位上的人所指向的座位就有可能成为空座位,所以需要递归的处理。淘汰了所有的空座位,这样剩下的人肯定指向的座位都是一一对应的。

所以算法主要就是要查找淘汰元素:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def naive_max_perm(M, A=None):
# A是目前有效的座位
true# 首先初始化
trueif A is None: A = set(range(len(M))
trueif len(A) == 1: return A
true# B是要用到的座位
trueB = set([M[i] for i in A])
true# C是没有用到的座位
trueC = A - B
trueif C:
true # 将没有用的座位从A中删除
truetrueA.remove(C.pop())
truetrue# 递归处理剩余的元素,因为删除一个元素后会导致新的空座位,所以需要再次遍历一下有用座位
truetruereturn naive_max_perm(M, A)
return A

该算法的时间复杂度是平方级的,因为该递归是1重递归,a=1,每次递归只会解决单位为1规模的问题,每次递归额外的算法单元复杂度是n,所以递推公式为T(n) = T(n-1) + n,所以可以得时间复杂度是平方级的。

递归通常都可以直接替换成循环操作。可以为各个元素设置一个计数器,每当有指向座位x的人被淘汰的时候,就递减座位的计数器,直到为0,编号为x的人和座位一起被淘汰。引用计数是许多垃圾回收系统的基本组件,是一种内存管理形式,主要用于自动回收那些不会再用到的对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def max_perm(M):
n = len(M)
# A表示有效位置
A = set(range(n))
count = [0] * n
for i in M:
count[i] += 1
# Q表示没有用的座位
Q = [i for i in A if count[i] == 0]
while Q:
# 要淘汰的位置
i = Q.pop()
A.remove(i)
# 淘汰位置的人所指向的位置
j = M[i]
count[j] -= 1
# 如果淘汰的人指向的位置,也是空座位,继续淘汰
if count[j] == 0:
Q.append(j)
return A

计数排序

如果操作的问题元素是可以被哈希的,那么计数法就是最常用的工具了。下面是一个计数排序代码。

1
2
3
4
5
6
7
8
9
10
from collections import defaultdict
def counting_sort(A, key=lambda x: x):
B, C = [], defaultdict(list)
# 先对要排序的内容进行计数
for x in A:
C[key(x)].append(x)
# 然后从小到大
for k in range(min(C), max(C) + 1):
B.extend(C[k])
return B

get到一点,可以使用min(C)获取到字典的最小key值

明星问题

这个问题就是研究某组依赖关系,该明星不认识任何人,人人都认识这个明星。抽象化就是一个其他所有节点都对该节点有入边,但是自身却没有出边。一个暴力解决方案就是直接迭代,两层循环,如果对于外层循环的u,内层循环所有元素都有入边,但是自己没有出边,则说明是明星,否则不是。

1
2
3
4
5
6
7
8
9
10
def naive_celeb(G):
n = len(G)
truefor u in range(n):
true for v in range(n):
truetrue if u == v: continue
truetruetrueif G[u][v]: break # 有出边就不是明星
truetruetrueif not G[v][u]: break # 只要有一个人不认识就不是明星
truetrueelse:
truetrue return u # 当没有break的时候才是找到明星
truereturn None

平方级算法,下来就是要找到一种归简法,将问题人数由n归简到n-1,一种思路就是对于一个非明星,也就是要么这个人认识某个人,要么就是有人不认识v(Python算法教程中P87表述有误)。所以检查u,v中任何一个节点G[u][v],如果G[u][v]为 True那么就排除u,否则排除v(说明有人不认识v)。接下来确保其中存在一个明星人士就行了,然后通过上面的判断算法来检查。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def celeb(G):
n = len(G)
trueu, v = 0, 1
truefor i in range(2, n+1):
true if G[u][v]: u = i # True说明u可以到v,排除
truetrueelse: v = i # False说明有节点到不了v,排除
trueif u == n: i = v
trueelse: i = u
truefor v in range(n): # 进一步检测
true if i == v: continue
truetrueif G[i][v]: break
truetrueif not G[v][i]: break
trueelse:
true return i
truereturn None

拓扑排序

有一种先后的依赖关系,可以表示成一个有向非环路图(DAG),并将寻找其中依赖顺序的过程,寻找所有沿着特定顺序前进的边和点,称为拓扑排序。一些基于DAG的算法,例如某种寻找DAG中的最短路径,以及大多数基于动态规划的算法,都是以先进行拓扑排序作为初始化步骤的。

拓扑排序的递归实现的基本思想是先移除一个节点,然后解决其余的n-1个节点的拓扑排序问题,直到递归到最后一个节点,然后排序的主要原理是根据该节点的入度多少,如果入度多,则说明在最后,入度少,则可以作为初始节点,即开始节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def topsort(G, S=None):
if S is None: S = set(G)
if len(S) == 1: return list(S)
v = S.pop()
# 一直递归到最后一个
seq = topsort(G, S)
min_i = 0
# 如果v有seq中节点的入边,那么就应该放在后面
for i, u in enumerate(seq):
truetrue# 统计入度
if v in G[u]: min_i = i + 1
truetrue# 入度多,说明在后面
seq.insert(min_i, v)
return seq
a, b, c, d, e, f = range(6)
N = {
e: {f},
b: {c, d, f},
a: {b, f},
d: {e, f},
c: {d},
f: {}
}
print(topsort(N))

同理它也是一个平方级的算法,可以通过在递归调用开始之前找到那个该被移除的节点而不是随机移除。所以一个没有入边的节点,一个没有入边的节点可以安全的被移除,因为它不依赖任何其他节点。同样可以用计数方式来查找没有入边的节点,没有入边的节点count值就是0,移除一个节点,就应该把其相应的指向节点的入度-1,如果变成0,那么就应该将其加入到应该移除的节点列表里。

另外一点就是如果一开始有多个初始点,如果在去掉一个初始点后,该初始点指向的点入度为0的话,就会一直递归的将这条路径做完。然后再从开始的初始点再去移除节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def topsort(G):
count = dict((u, 0) for u in G)
for u in G:
for v in G[u]:
count[v] += 1 # v的入度
# Q是应该移除的节点列表
Q = [u for u in G if count[u] == 0]
S = []
while Q:
u = Q.pop() # 默认最后一个元素
S.append(u)
for v in G[u]:
count[v] -= 1
# 元素入度减为0,则加入应该移除的节点列表中
if count[v] == 0:
Q.append(v)
if len(G) != len(S):
# 有环
return []
return S
  • 拓扑排序和Python的MRO

大多数编程语言都会致力于创建一种线性化的类关系,就是DAG的拓扑排序算法。Python中使用的方法解析顺序MRO是C3

一些概念

更强的假设条件

上面情况设计算法时候设定的归纳前提都是能够解决规模更小的问题,但是有时候这样是不够用的,所以需要在归纳操作中引入一些额外信息。比如在计算树的平衡因子问题上,如果递归解决每个子树上的问题的话,这样并不能解决问题,因为平衡因子不是根据子节点上的平衡因子来决定的,而是根据子树高度来定义的。因此,只要强化假设条件:一定能够找到任意一棵满足节点数k小于n的树的平衡因子和高度。这样,在归纳步骤中使用高度,并且在规模大小为n的归纳步骤里,算出节点两边之间的平衡因子及其高度。

循环不变式

循环不变式是指确保某些事情对于循环中每次迭代操作都成立而设的一些前提条件,它在相关操作中自始至终都是成立的。所以如果能让该不变式始终维持下去,并且证明循环存在终止状态,那么我们已经证明了这个算法的正确性。

松弛法

其实就是一些方法可以通过逐步接近的方式来获得相关问题的最佳解法。比如下面:

1
2
3
4
5
for v in range(n):
C[v] = float('inf')
for i in range(N):
u, v = randrange(n), randrange(n)
trueC[v] = min(C[v], A[u] + B[u][v]) # 这里就是一种松弛

困难度证明

困难度证明所基于的事实是我们只允许用容易的归简法来简化问题。如果我们是通过问题A归简成B来解决A的,那么也只是看起来B简单一点,因为B是已经知道如何解决的。所以A要能够归简成B,B至少要和A是同等难度的问题。

建议

  • 确保自己真正理解问题
  • 找到一种归简方法
  • 查看是否有额外的假设条件可用

总结

归简法的算法设计,主要就是把相关问题归简成已知东西来解决问题,归简成了一个不同的问题,或许可以用某个现存算法解决。如果归简成了一个或者多个子问题,其实是同一个问题的更小型实例,可以用归纳法解决,并根据此设计新算法。上面的内容就是将问题转变成n-1规模的子问题。

在问题规模上的归简和归纳方法或多或少和递归有关系,归纳法通常用来证明递归操作的正确性。而递归是绝大多数归纳性算法思路最直接实现方法。因为效率问题,递归可以用迭代来重写。

这一章内容挺多的,感觉没有理解太透彻,但是卒或有所闻。归简法,递归以后再慢慢体会吧!

参考自:Python 算法教程 – Magnus Lie Hetland