介绍归纳、递归-白红宇

介绍归纳、递归

阅读量：4088 次

发布时间：2019-05-25

本文共 18396 字，大约阅读时间需要 61 分钟。

简单地说，将一个问题A简化为另一个问题B涉及到某种形式的转换，然后解决方案给B（直接或通过一些按摩）给A一个解决方案。一旦你学会了一系列标准算法（在这本书中你会遇到很多），这是你遇到新问题时通常会做的事情。你能以某种方式改变它，以便用你知道的方法之一来解决它？在许多方面，这是核心解决所有问题的过程。让我们举个例子。你有一个数字列表，你想找到两个不相同的数字彼此最接近（即绝对差最小的两个）：

from random import rangdrange

seq = [randrange(10**10) for i in range(100)]

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

xx, yy

(15743, 15774)

两个嵌套循环，都在seq上；很明显这是二次循环，这通常不是一件好事。假设你已经研究过一些算法，你知道如果序列排序。您还知道排序通常是对数线性的，或q（n lg n）。明白了吗？这里的见解是在排序顺序中，两个最近的数字必须相邻：

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

更快的算法，同样的解决方案。新的运行时间是对数线性的，以排序为主。我们的原创问题是“在一个序列中找到两个最接近的数字”，我们将其简化为“在排序序列，”通过排序序列在这种情况下，我们的减少（排序）不会影响我们得到的答案。一般来说，我们可能需要改变答案，使其符合原始问题。

注意，在某种程度上，我们只是将问题分为两部分，对排序的序列进行排序和扫描。你也可以说扫描是一种减少原始问题到排序序列的问题的方法。一切都是关于观点。

把A减到B有点像说“你想解A吗？”哦，这很容易，只要你能解出b。”见图4-1 为了说明减少是如何工作的。

图4-1。使用从A到B的约简，用B的算法求解A。B的算法（中心，内部 circle）可以转换输入b吗？输出B！，而还原包含两个转换（较小的圆圈）从A开始？到B？从B！A！，一起形成主算法，哪个转换输入A？到输出A！

一，二，很多我已经用归纳法解决了第3章中的一些问题，但是让我们回顾一下，并通过以下几个步骤来解决例子。在抽象地描述归纳法时，我们说我们有一个命题或陈述，p（n），并且我们想证明对任何自然数n都是正确的。例如，假设我们正在研究第一个n的和奇数；p（n）可以是以下语句：

这是非常熟悉的，几乎和我们在上一章中讨论过的握手和一样。你通过调整握手公式可以很容易地得到这个新结果，但是让我们看看我们如何通过归纳法证明它。相反。归纳法的思想是让我们的证明“扫过”所有自然数，有点像一排多米诺骨牌。坠落。我们首先建立P（1），这在本例中非常明显，然后我们需要展示每个Domino，如果它掉下来，下一个就会倒掉。换句话说，我们必须证明，如果p（n-1）是真的，那么p（n）就是也是如此。如果我们能证明这一含义，即p（n–1）p（n），结果将扫过n的所有值，从 P（1），用P（1）P（2）建立P（2），然后转到P（3）、P（4）等。换句话说，关键是以确定让我们更进一步的含义。我们称之为归纳步骤。在我们的示例中，这意味着我们假设如下（p（n-1））：

镜子，镜子在他出色的网络视频节目中，泽弗兰克曾经说过：“你知道没有什么可以害怕的，但是恐惧本身。“是的，这叫做递归，这会导致无限的恐惧，所以谢谢你。”4 建议是，“为了理解递归，我们必须首先理解递归。” 的确。尽管无限递归是一种相当病态的行为，但递归很难让人信服。在某种程度上，递归实际上只有作为归纳的镜像才有意义（见图4-3）。在归纳法中，我们（概念上）从一个基本情况开始，展示归纳步骤是如何使我们更进一步，直至完整的问题。大小，n.对于弱诱导，6我们假设（诱导假设）我们的解适用于n-1，由此，我们推断它适用于n。递归通常更像是分解事物。从一个完整的问题开始，大小为n。将大小为n–1的子问题委托给递归调用，等待结果，然后扩展子解决方案找到一个完整的解决方案。我相信你能明白这是怎么回事。在某种程度上，归纳法告诉我们为什么递归有效，递归给了我们一个简单的方法（直接）实现归纳思想。

图4-3。归纳（在左边）和递归（在右边），作为彼此的镜像

例如，以前一节中的跳板问题为例。制定解决方案的最简单方法对此（至少在我看来）是递归的。你放置一个L形件，这样你得到四个等价的子问题，和然后你递归地解决它们。通过归纳，解决方案是正确的。

实现棋盘式覆盖

尽管棋盘覆盖问题在概念上有一个非常简单的递归解决方案，但是实现它可以需要一些思考。实现的细节对示例的要点并不重要，所以感觉如果你愿意，可以跳过这个侧边栏。实现解决方案的一种方法如下所示：

def cover(board,lab=1,top=0,left=0,side=None):

if side is None: side = len(board)

## side length of subboard:

s = side//2

## offsets foe outer/inner squares of subboards:

offstes = (0,-1),(side-1,0)

for dy_outer,dy_inner in offstes:

for dx_outer,dx_inner in offsets:

# if the outer corner is not set..

## ... label the inner corner:

board[top+s+dy_inner][left+s_dx-inner] = lab

# next label:

lab +=1

if s > 1:

for dy in [0,s]:

for dx in [0,s]:

lab = cover(board,lab,top+dy,left+dx,s)

return lab

board = [[0]*8 for i in range(8)] ## Eight by eight checkerboard

board[7][7] = -1

cover(board)

for row in board:

print("%si*8) % tuple(row))

def ins_sort_rec(seq,i):

if i ==0:return

ins_sort_rec(seq,i-1)

j = i

while j > 0 and seq[j-1] >seq[j]:

seq[j-1],seq[j] =seq[j],seq[j-1]

j -=1

这些算法并没有那么有用，但它们通常是被教授的，因为它们是很好的例子。而且，他们是经典，所以任何一个算法师都应该知道它们是如何工作的。

再一次，你可以看到这两者非常相似。递归实现显式表示归纳假设（作为递归调用），而迭代版本显式表示重复执行归纳步骤。两者都是通过找到最大的元素（for循环查找max_j）并将其交换到正在考虑的序列前缀的结尾。注意，您也可以在此节从开始，而不是从结束（在插入排序中，将所有对象排序到右侧，或查找选择排序中的最小元素）

def sel_sort_rec(seq,i):

if i == 0:return

max_j = i

for j in range(i):

if seq[j] > seq[max_j]:max_j = j

seq[i],seq[max_j] = seq[max_j],seq[i]

sel_sort_rec(seq,i-1)

# Selection Sort

def sel_sort(seq):

for i in range(len(seq)-1,0,-1):

max_j = i

for j in range(i):

if seq[j] > seq[max_j]:max_j = j

seq[i],seq[max_j] = seq[max_j],seq[i] # Switch largets intp place

在可能的情况下，尝试使用尽可能特定于您的问题的表示。更一般表示可以导致更多的簿记和复杂的代码；如果使用隐式表示这个问题的一些约束条件，无论是找到还是实现一个解决方案都会容易得多。

如果需要，我们现在可以直接实现递归算法的思想，使用一些强力代码来查找要消除的元素。它不会非常高效，但是效率低下的实现有时是一种有指导意义的开始的地方。有关相对直接的实现，请参见清单4-5。清单4-5。求最大排列的递归算法思想的一种简单实现

像往常一样，系统地检查我们可以使用的工具，并尽可能清晰地界定问题，使其更容易找到解决方案。我们已经到了一个需要划分序列的时刻。分成两半，一个由小值和一个大值组成。我们不必保证两半只等于它们平均相等。一个简单的方法是选择一个值作为所谓的旋转并用它来划分其他部分：所有小于（或等于）旋转的部分最后都在左半部分，而那些 5在统计学中，中位数也被定义为等长序列。它是两个中间元素的平均值。那不是我们在这里担心的一个问题。第6章■分裂、合并和征服一百二十四更大的一端在右边。清单6-3给出了分区和选择的可能实现。注意这个版本分区的主要目的是可读；练习6-11要求您查看是否可以删除一些开销。这里写的方式是select，它返回kth最小的元素；如果您想要所有k最小的元素，您可以可以简单地重写它以返回lo而不是pi。

def partition(seq):

pi,seq = seq[0],seq[1:]

lo = [x for x in seq if x<=pi]

hi = [x for x in seq if x>pi]

return lo,pi,hi

def select(seq,k):

lo,pi,hi = partition(seq)

m = len(lo)

if m == k: return pi

elif m<k:

return select(hi,k-m-1)

else:

return select(lo,k)

快速排序：

def quicksort(seq):

if len(seq) <= 1:return seq

lo,pi,hi =parttion(seq)

return quicksort(lo)+[pi]+quicksort(hi)

您已经在第3章（清单3-2）中看到了用于合并排序的代码，但是我将在这里重复它，并给出一些注释

def mergesort(seq):

mid = len(seq)//2

lft,rgt = seq[:mid],seq[mid:]

if len(lft)>1:lft = mergesort(lft)

if len(rgt)>1:rgt =mergesort(rgt)

res = []

while lft and rgt:

if lft[-1] >=rgt[-1]:

res.append(lft.pop())

else:

res.append(rgt.pop())

res.reverse()

return (lft or rgt)+res

现在应该比第3章更容易理解这是如何工作的。注意合并部分有是为了说明这里发生了什么。如果您要在python中实际使用合并排序（或类似的算法），您可能会使用heapq.merge进行合并。

我们如何避免这两个显式for循环可能并不是很明显，但让我们先尝试避免隐藏在总和中的那个。一种方法是在一次迭代中考虑长度为k的所有间隔，然后移动到 K+1等等。这仍然会给我们一个二次的间隔来检查，但是我们可以使用一个技巧使扫描成本线性：我们正常计算第一个间隔的总和，但每次间隔移动一个位置在右边，我们简单地减去现在落在它外面的元素，然后添加新元素：

best = A[0]

for size in range(1,n+1):

cur = sum(A[:size])

for in range(n-size):

cur +=A[i+size]-A[i]

best = max(best,cur)

沿着这条路走得更远的行动实际上只能做一件会影响我们的事情：他们可以放另一件将节点转换为“我们的”当前模拟节点。在叶级别，每当我们添加节点时都会发生这种情况，因为它们都有 1级。如果当前节点在树中的位置更高，那么我们可以在当前（模拟）节点中获取另一个节点，如果有在分割过程中向上移动。不管是哪种方式，这个突然出现在我们级别上的节点可以是左子节点，也可以是一个合适的孩子如果是一个左孩子，我们就歪斜（做一个右旋转），我们已经解决了这个问题。如果是对的孩子，一开始没问题。但是，如果它是一个右孙子，我们有一个过满的节点，所以我们做了一个拆分（左旋转）并将我们模拟的4节点的中间节点提升到父节点的级别。用文字来描述这一切是相当困难的——我希望代码足够清楚，你会明白发生了什么。在。（不过，这可能需要一些时间和头疼。）

class Node：

lft = None

rgt = None

lvl = 1

def __init__(self,key,val):

self.key = key

self.val = val

def skew(node):

if None in [node,node.lft]:return node

if node.lft.lvl != node.lvl:return node

lft = node.lft

node.lft = lft.rgt

lft.rgt = node

return lft

def split(node):

if None in [node,node.rgt,node.rgt.rgt]:return node

if node.rgt.rgt.lvl != node.lvl:return node

lft = node.lft

lft.rgt=node

return lft

def split(node):

if None in [node,node.rgt,node.rgt.rgt]:return node

if node.rgt.rgt.lvl !=node.lvl：return node:

rgt = node.rgt

node.rgt = rgt.lft

rgt.lft = node

rgt.lvl +=1

return rgt

def insert(node,key,val):

if node is None:return Node(key,val)

if node.key == key:node.val = val

elif key < node.key:

node.lft = insert(node.lft,key,val)

else:

node.rgt = insert(node.rgt,key,val)

node = skew(node)

node = split(node)

return node

黑盒：二进制堆、heapq和heapsort

heapq模块包含一个高效的堆实现，它使用一个公共的 “编码”：如果a是一个堆，那么[i]的子代可以在[2*i+1]和[2*i+2]中找到。这意味着根（最小元素）总是在[0]中找到。您可以使用heappush和 HeapPop函数。您也可以从一个包含大量值的列表开始，并希望将其堆。在这种情况下，可以使用heapify函数。17它基本上修复每个子树根，从右下角，向左上移动。（实际上，通过跳过叶，它只需要在数组的左半部分工作。）产生的运行时间是线性的（见练习6-9）。如果您的列表已排序，则它已经是一个有效的堆，因此您可以别管它了。

与平分一样，heapq模块是在C中实现的，但它以前是一个普通的python模块。例如，下面是函数的代码（来自python 2.3），该函数向下移动一个对象，直到它小于它的两个对象。孩子们（再说一遍，还有我的评论）

def sift_up(heap,startpos,pos):

newitem = heap[pos]

while pos > startpos:

parentpos = (pos-1)>>1

parent = heap[parentpos]

if parent <=newitem:break

heap[pos] = parent

pos = parentpos

heap[pos] = newitem

我们先设计一个贪婪的算法来解决这个问题，然后再证明它是正确的（当然，关键步骤）。最明显的贪婪策略可能是将字符（叶）逐个添加，从频率最高的开始。但是我们要在哪里添加它们呢？另一条路（你会看到在Kruskal的算法中，有一点）是让一个局部解由几个树片段组成，然后重复把它们结合起来。当我们组合两棵树时，我们添加一个新的共享根，并赋予它等于孩子，也就是以前的根。这正是图7-2中节点内部的数字的含义。清单7-1显示了实现哈夫曼算法的一种方法。它作为一个森林保持了部分解决方案，每棵树都表示为嵌套列表。只要森林里至少有两棵独立的树，两棵最轻树木（根部重量最低的树）被挑选出来，组合起来，放回原位，并有一个新的根部重量。

from heapq import heapify,heappush,heappop

from itertools import count

def huffman(seq,frq):

num = count()

trees = list(zip(frq,num,seq))

heapify(trees)

while len(trees) >1:

fa, _, a = heappop(trees)

fb, _, b =heappop(trees)

n = next(num)

heappush(trees,(fa+fb,n,[a,b]))

return trees[0][-1]

一种解决方案是在两者之间添加一个字段，确保所有对象的字段都不同。在这种情况下，我只是使用一个计数器，结果是（freq，num，tree），其中使用任意num中断频率绑定，避免直接比较（可能无法比较）树。6 如您所见，生成的树结构与图7-2所示的树结构等效。当然，要使用这种技术压缩和解压缩文本，您需要一些前处理和后处理。首先，您需要对字符进行计数以获得频率（例如，使用集合中的counter类模块）。然后，一旦你有了哈夫曼树，你就必须找到所有字符的代码。你可以这样做使用简单的递归遍历，如清单7-2所示。

def codes(tree, prefix=""):

if len(tree) == 1:

yield (tree, prefix) # A leaf with its code

return

for bit, child in zip("01", tree): # Left (0) and right (1)

for pair in codes(child, prefix + bit): # Get codes recursively

yield pair

克鲁斯卡尔算法

该算法接近于本章开头概述的一般贪婪方法：对边缘和开始采摘。因为我们在寻找短边，所以我们通过增加长度（或重量）对它们进行排序。唯一的皱纹是如何检测可能导致无效解决方案的边缘。唯一使我们的解决方案失效的方法是一个循环，但我们如何检查它呢？一个简单的解决方案是使用遍历；每次我们考虑一个边（u，v），我们从u穿过我们的树，看是否有到v的路径。如果有，我们就丢弃它。这个好像有点不过，这是浪费；在最坏的情况下，遍历检查将花费部分解大小的线性时间。我们还能做什么？到目前为止，我们可以在树中维护一组节点，然后在未来边缘（u，v），我们会看到是否两者都在解决方案中。这意味着对边缘进行排序是最主要的；可以在恒定时间内检查每个边缘。这个计划只有一个关键缺陷：它行不通。它会如果我们能保证局部解在每一步都是连接的（这就是我们将要做的 Prim的算法），但我们不能，所以即使到目前为止两个节点是我们解决方案的一部分，它们可能在不同的树中，并且连接它们是完全有效的。我们需要知道的是，它们不在同一棵树上。让我们尝试通过让解决方案中的每个节点知道它属于哪个组件（树）来解决这个问题。我们可以让组件中的一个节点充当代表，然后该组件中的所有节点都可以指向该节点。代表。这就留下了组合组件的问题。如果合并组件的所有节点都必须指向对于同一个代表，这种组合（或联合）将是一个线性运算。我们能做得更好吗？我们可以尝试；因为例如，我们可以让每个节点指向另一个节点，然后沿着该链一直走到代表处（指它自己）。那么加入只是一个代表指向另一个（常数时间）目前还不能立即保证引用链的长度，但这至少是第一步。这就是我在清单7-3中所做的，使用map c实现“指向”。如您所见，每个节点最初是它自己的组件的代表，然后我用新的边反复连接组件，按排序顺序。注意，在我实现这一点的方法中，我期望每个边都是一个无向图。仅代表一次（即，使用其中一个方向，任意选择）。11和往常一样，我假设不过，节点是图表中的一个关键点，可能有一个空的权重图（也就是说，如果u没有外缘，g[u]=）。

def naive_find(C,u):

while C[u]!=u:

u = C[u]

return u

def naive_union(C,u,v):

u =naive_find(C,u)

v = naive_find(C,v)

C[u] = v

def naive_kruskal(G):

E = [(G[u][v],u,v) for u in G for v in G[u]]

T = set()

C ={u:u for u in G}

for _, u,v in sorted(E):

if naive_find(C,u)!=naive_find(C,v):

T.add((u,v))

naive_union(C,u,v)

return T

纳维克鲁斯卡尔很管用，但也不是那么好。（什么，名字泄露了？）在最坏的情况下，链条在幼稚的发现中，我们需要遵循的参考可能是线性的。一个相当明显的想法可能是幼稚联盟的两个组成部分中较小的部分指向较大的部分，给了我们一些平衡。或者我们可以认为更重要的是，在一棵平衡的树上，给每个节点一个等级或高度。如果我们总是排名最低代表指出排名最高的一个，我们会得到一个O（M lg n）的总运行时间，用于呼叫naive_find 以及天真的联盟（见练习7-16）。这实际上是很好的，因为开始的排序操作无论如何都是完成的（m lg n）。不过，这种算法中常用的技巧称为路径压缩。它需要“沿着指针移动” 在执行查找时，请确保我们在路上检查的所有节点现在都直接指向该代表。这个更多的节点直接指向代表，越快的事情应该在后面找到，对吗？可悲的是，推理这究竟是如何帮助我的，为什么帮助我，背后太复杂了，我不能进入这里（尽管我会推荐门派）。21.4英寸 Cormen等人的算法简介，如果您感兴趣的话）。最终的结果是，最坏的情况是联合和发现的运行时间是O（ma（n）），其中a（n）几乎是一个常数。实际上，可以假设a（n）≤4，对于n的任何甚至是远程可信的值，对于find和union的改进实现，请参见清单7-4。

def find(C,u):

if C[u]!=u:

C[u] = find(C,C[u])

return C[u]

def union(C,R,u,v):a

u,v =find(C,u),find(C,v)

if R[u]>R[v]:

C[v] = u

else:

C[u]=v

if R[u] == R[v]:

R[v] +=1

def kruskal(G):

E =[(G[u][v],u,v) for u in G for v in G[u]]

T = set()

C,R = {u:u for u in G},{u:0 for u in G}

for _,u,v in sorted(E):

if find(C,u) !=find(C,v):

T.add((u,v))

union(C,R,u,v)

return T

您可以在清单7-5中看到我的prim算法版本。因为HeapQ还不支持排序键，比如 list.sort和friends都有，我在堆中使用（weight，node）对，当节点突然爆炸。除了使用堆之外，代码类似于清单5-10中的宽度优先搜索的实现。这意味着这里的很多理解都是免费的。

def prim(G,s):

P,Q = {},[(0,None,s)]

while Q:

_, p,u = heappop(Q)

if u in P: continue

p[u] = p

for v,w in G[u].item():

heappush(Q,(w,u,v))

return P

动态规划的核心是顺序决策问题。你做出的每一个选择都会导致新的情况下，你需要找到最佳的选择顺序，使你达到你想要的情况。这是相似的。对于贪婪算法的工作原理，他们只是依赖于哪种选择现在看起来最好，而一般来说，你必须减少近视，并考虑到未来的影响。典型的顺序决策问题是在一个定向的节点中找到从一个节点到另一个节点的方法，非循环图我们将决策过程的可能状态表示为单个节点。外缘代表我们可以在每种状态下做出的选择。边缘具有权重，找到一组最佳选择是相当于找到一条最短的路径。图8-3给出了一个DAG示例，其中从节点A到节点F已突出显示。我们应该如何找到这条路？

图8 -3。拓扑排序的DAG。边缘用重量标记，从A到F的最短路径突出显示

应该清楚这是一个连续的决策过程。从节点A开始，您可以选择从边缘到B或从边缘到F。一方面，从边缘到B看起来很有希望，因为它很便宜，而一对F是很有诱惑力的，因为它直奔目标。然而，我们不能用这样简单的策略。例如，该图是这样构造的：从我们访问的每个节点的最短边开始，我们将沿着最长的路径。和前面的章节一样，我们需要进行归纳思考。假设我们已经知道所有我们可以移动到的节点。假设从一个节点v到我们的末端节点的距离是d（v）。让边缘的边缘权重（u，v） W（U，V）。那么，如果我们在节点U中，我们已经（通过归纳假设）知道了每个相邻V的d（v），所以我们只是必须沿着边到相邻的V，使表达式w（u，v）+d（v）最小化。换句话说，我们将第一步和最短路径之和。当然，我们不知道D（V）对所有邻居的价值，但是对于任何归纳设计，这将通过递归的魔力来照顾自己。唯一的问题是重叠的子问题。例如，在图8-3中，找到从b到f的距离需要找到从d到f的最短路径，但也需要找到从d到f的最短路径。找到从C到F的最短路径。我们的情况与斐波那契数、二次幂或帕斯卡三角。如果我们实现递归的话，一些子问题将被解成指数级的次数。直接解决。就像那些问题一样，记忆的魔力消除了所有的冗余，我们结束了使用线性时间算法（即，对于n个节点和m个边，运行时间为（n+m））。直接实现（使用类似于边权函数的dict-of-dicts表示）可以在清单8-3中找到。如果从代码中删除@memo，则最终会得到一个指数算法（它可能仍然适用于边缘较少的相对较小的图）。

def rec_dag_sp(W,s,t):

def d(u):

if u == t:return 0

return min(W[u][v]+d(v) for v in W[u])

return d(s)

在我看来，清单8-3中的实现非常优雅。它直接表达了算法，同时抽象出记忆。然而，这并不是表示该算法的经典方法。什么像其他许多dp算法一样，这里通常要做的是将算法“颠倒”并使其迭代。 DAG最短路径算法的迭代版本通过逐步传播部分解来工作，使用第4.9章中介绍的松弛思想，因为我们表示图的方式（即，我们通常访问节点由外边缘，而不是在边缘），它可以很有用地逆转归纳设计：而不是思考我们想去哪里，想我们想从哪里来。然后我们要确保一旦我们到达节点V，我们已经传播了所有V的前辈的正确答案。也就是说，我们已经放松了在边缘。这就提出了一个问题，我们如何确定我们已经做到了？要知道的方法是对节点进行拓扑排序，如图8-3所示。关于递归版本（在清单8-3中）是不需要单独的拓扑排序。递归隐式地执行一个DFS和是否所有更新都自动按拓扑排序。但是，对于我们的迭代解，我们需要执行分离拓扑排序。如果您想完全摆脱递归，可以使用清单4-10中的topsort；如果您不介意，可以使用清单5-7中的df-topsort（尽管这样您就已经非常接近记忆化递归解）。清单8-4中的函数dag_sp向您展示了这个更常见的迭代解决方案。

def dag_sp(W,s,t): # shortest path from s to t

d = {u:float('inf') for u in W} # Distance esstimates

d[s] = 0 # start node:zero distance

for u in topsort(W): # In top-sorted order

if u == t:break # Have we arrived

for v in W[u]: # For each out-edge

d[v] = min(d[v],d[u]+W[u][v]) # Relax the edge

return d[t] # Distance to t (from s)

迭代算法的思想是，只要我们把每一个边从你的每一个可能的边中解放出来前辈（也就是那些之前按拓扑排序的前辈），我们必须将所有的内边放宽到你。利用这个，我们可以归纳地显示，当我们到达每个节点时，它接收到一个正确的距离估计。外部for循环。这意味着一旦我们到达目标节点，我们就会找到正确的距离。找到与这个距离对应的实际路径也不是那么难（见练习8-5）。你甚至可以从开始节点构建整个最短路径树，就像第5章中的遍历树一样。（你得把但是break语句会一直执行到结尾。）请注意一些节点，包括那些早于start的节点。按拓扑排序的节点，可能根本无法到达，并将保持其无限距离

子序列虽然在DAG中找到最短路径是典型的DP问题，但可能大多数DP 您将遇到的问题与（显式）图没有任何关系。在这种情况下，你必须嗅探自己完成DAG或顺序决策过程。或者用递归的方式来考虑它可能更容易分解并忽略整个DAG结构。在这一部分中，我将遵循两种解决问题的方法在本章开头介绍：寻找最长的非递减子序列。（问题是通常称为“最长增加子序列”，但在这里我将允许在结果中有多个相同的值。）让我们直接讨论归纳法，稍后我们可以用图表来思考更多问题。进行归纳（或递归分解），我们需要定义我们的子问题，许多DP问题的主要挑战之一。在许多与序列相关的问题，用我们已经计算出所有需要知道的前缀来思考是很有用的。关于前缀，归纳的步骤是找出另一个元素。在这种情况下，这可能意味着

我们已经找到了每个前缀增加时间最长的子序列，但这还不够有用。我们需要加强我们的归纳假设，这样我们就可以实际执行归纳步骤。让我们试着找到在每个给定位置结束的最长增加子序列。如果我们已经知道如何在前k个位置找到它，那么如何在k+1位置找到它呢？一次我们已经走到了这一步，答案很简单：我们只需看看以前的职位，然后看看那些其元素小于当前元素。其中，我们选择最长的一个子序列。直接递归实现将给我们提供指数级的运行时间，但再次，记忆化去掉指数冗余，如清单8-5所示。再一次，我专注于找出解决方案；扩展代码以找到实际的子序列并不那么困难（练习8-10）。

def rec_lis(seq):

def L(cur):

res = 1

for pre in range(cur):

if seq[pre] <=seq[cur]:

res =max(res,1+L(pre))

return res

return max(L(i) for i in range(len(seq)))

让我们也做一个迭代版本。在这种情况下，两者之间的差异非常微小，这让人联想到如图4-3所示。由于递归的工作方式，rec-lis将解决中每个位置的问题。顺序（0，1，2…）。在迭代版本中，我们所需要做的就是通过查找关闭递归调用并包装整个事情都在循环中。有关实现，请参见清单8-6。

最长增长子序列问题的一个基本迭代解

def basic_lis(seq):

L = [1]*len(seq)

for cur,val in enumerate(seq):

for pre in range(cur):

if seq[pre] <= val:

L[cur] = max(L[cur],1+L[pre])

return max(L)

我希望您能看到与递归版本的相似之处。在这种情况下，迭代版本可能同样容易理解为递归的。现在，把它想象成一个DAG：每个序列元素都是一个节点，每个元素都有一个隐式的边。对于后面的每个较大的元素，也就是说，对于任何在递增过程中是允许的后继元素随后（见图8-4）。VORE！我们现在正在解决DAG最长路径问题。事实上很清楚在基本函数中。我们没有显式表示边缘，因此它必须查看前面的每个元素看看它是否是一个有效的前一个，但如果是，它只是放松在边缘（这就是最大值的线真的。我们是否可以通过在决策过程（即，此处于边缘或此有效的前置任务）

由于通常的原因，您可能需要反转解决方案并使其迭代。清单8-9给出了一个版本它只保留dp矩阵的当前行和前一行，从而节省内存。（你可以省点钱，但是，请注意cur[i-1]在递归版本中对应于l（i-1，j），而pre[i]和 pre[i-1]分别对应于l（i，j-1）和l（i-1，j-1）

背包反击

如果我们说m（r）是一个（剩余的）容量r所能得到的最大值，r的每个值都给我们一个子问题。递归分解基于使用或不使用最后一个容量单位。如果我们不用它，我们得到m（r）=m（r-1）。如果我们使用它，我们必须选择正确的对象来使用。如果我们选择对象I（提供它将适合剩余的容量），我们会有m（r）=v[i]+m（r-w[i]），因为我们会加上i的值，但是我们会也消耗了一部分剩余的容量，相当于它的重量。我们可以（再一次）把这看作一个决策过程：我们可以选择是否使用最后一个容量单位，如果我们使用它，我们可以选择添加哪个对象。因为我们可以选择任何我们想要的方式，我们只需所有可能性的最大值。记忆化处理了这个递归中的指数冗余。定义，如清单8-10所示。

def rec_unbounded_knapsack(w,v,c):

def m(r):

if r == 0:return 0

val = m(r-1)

for i,wi in enumerate(w)；:

if wi >r:continue

val = max(val,v[i]+m(r-wi))

return val

return m(c)

这里的运行时间取决于容量和对象数量。每个记忆呼叫M（R）是只计算一次，这意味着对于容量C，我们有完成（C）调用。每次调用都会经过所有n个对象，因此，产生的运行时间是。（这可能在等效迭代版本中更容易看到，下一步。另请参见练习8-14，了解提高运行时间常数的方法。）注意，这不是多项式运行时间，因为C可以随着实际问题的大小（位数）成指数增长。如前所述，这种运行时间被称为伪多项式，对于合理大小的容量，该时间被称为解决方案实际上相当有效。清单8-11显示了该算法的迭代版本。正如您所看到的，这两个实现实际上是相同，只是递归被for循环替换，缓存现在是一个列表。

现在我们需要将这些子问题联系起来，并从子解决方案构建一个解决方案。让m（k，r）成为对于前k个对象和剩余容量r，我们可以得到最大值。然后，很明显，如果k=0或r=0，我们将 m（k，r）=0。对于其他情况，我们必须再次考虑我们的决定是什么。对于这个问题，决定是比无边界的更简单；我们只需要考虑是否要包括最后一个对象，i=k-1。如果我们不要，我们会得到m（k，r）=m（k-1，r）。实际上，我们只是从我们没有的情况下“继承”了最优值。还以为我呢。注意，如果w[i]>r，我们别无选择，只能丢弃对象。如果物体足够小，我们可以把它包括进去，这意味着m（k，r）=v[i]+m（k-1，r-w[i]），也就是说除了额外的参数（k.15），与无边界情况非常相似，因为我们可以自由选择是否包括对象，我们尝试两种选择，并使用两个结果值的最大值。再次，记忆消除了指数冗余，最后得到的代码与清单8-12中的代码类似。

def rec_knapsack(w,v,c):

def m(k,r):

if k == 0 or r == 0:return 0

i = k-1

drop = m(k-1,r)

if w[i] > r:return drop

return m(len(w),c)

在像LCS这样的问题中，简单地找到一个解决方案的值是有用的。对于LCS，最长的公共子序列让我们知道两个序列有多相似。不过，在很多情况下，你会发现实际的解决方案会产生最佳的成本。清单8-13中的迭代背包版本构造了一个额外的表，之所以称为P，是因为它的工作方式有点像遍历（第5章）中使用的前一个表和最短路径报错

def knapsack(w,v,c):

n = len(w)

m = [[0]*(c+1) for i in range(n+1)]

p =[[False]*(c+1) for i in range(n+1)]

for k in range(1,n+1):

i = k-1

for r in range(1,c+1):

m[k][r] = drop = m[k-1][r]

if w[i] > r:continue

keep = v[i]+m[k-1][[r-w[i]]

m[k][r] = max(drop,keep)

P[k][r] = keep > drop

return m,P

既然背包函数返回了更多的信息，我们就可以使用它来实际提取对象集了。包含在最佳解决方案中。例如，您可以这样做：

m,P = knapsack(w,v,c)

k,r,items = len(w),c,set()

while k>0 and r>0:

i = k-1

if P[k][r]:

items.add(i)

r -= w[i]

k -=1

换句话说，只需保留一些关于所做选择的信息（在本例中，保留或删除考虑中的元素），我们可以逐渐地从最终状态追溯到初始状态。在本例中，我从最后一个对象开始，检查p[k][r]是否包含它。如果是的话，我减去它的重量如果不是的话，我就让R单独呆着（因为我们仍然有全部的可用容量）。在这两种情况下，我减少k是因为我们已经完成了最后一个元素的查找，现在想查看下一个到最后一个元素（更新了容量）。您可能想让自己相信这个回溯操作有一个线性的运行时间。在本章的所有示例中都可以使用相同的基本思想。除了提出的核心算法（通常只计算最佳值），您可以跟踪在每个步骤中所做的选择，然后一旦找到最佳方案，就要回溯。

当然，在最终的解决方案中，我们将在范围（i，j）中尝试所有r并选择最大值。还有更多的空间但是，为了改进：表达式的和部分将对重叠间隔的二次数求和（每一个可能的i和j对应一个），每个和都有线性运行时间。本着DP的精神，我们寻求重叠：我们引入表示和的memoized函数s（i，j），如清单8-14所示。如你所见，S是假设递归调用已经缓存（这意味着常量计算每一个和（i，j））所花费的时间。代码的其余部分直接来自前面的讨论。

清单8至14。期望最优搜索成本的模化递归函数

总之，该算法的运行时间是立方的。渐近上界是直接的：有一个子问题的二次数（即间隔），我们对每个子问题内部的最佳根进行线性扫描。实际上，下界也是立方的（这有点复杂），所以运行时间是。对于以前的dp算法，迭代版本（清单8-15）在许多方面与memoized类似一。为了以安全（即拓扑排序）顺序解决问题，它解决了一定长度k的所有区间。然后再去大一点的。为了简单起见，我使用了一个dict（或者更具体地说，一个defaultdict，它自动提供零）。您可以很容易地重写实现，以使用列表列表。（不过，请注意，只需要一个三角形的半矩阵，而不需要完整的n乘n。）

传播知识在第四章中，我介绍了放松和逐步改善的概念。在第8章中，你看到了这个想法的应用在DAG中寻找最短路径。事实上，DAGS的迭代最短路径算法（清单8-4）不仅仅是动态规划的典型例子；它也说明了这一算法的基本结构第二章：利用图的边缘松弛来传播关于最短路径的知识。让我们回顾一下这是什么样子。我将使用图表的dict表示形式的dict，并使用dict d来维护距离估计（上限），如第8章。另外，我将添加一个前置dict，p，作为第5章中的遍历算法。这些前置指针将形成所谓的最短路径树，并允许我们重建与D中距离相对应的实际路径。然后可以在RELAX中分解松弛。清单9-1中的函数。注意，我将D中不存在的条目视为无穷大。（我也可以初始化当然，在主要算法中，它们都是无限的。）

inf = float('inf')

def relax(W,u,v,D,P):

d = D.get(u,inf)+W[u][v]

if d < D.get(v,inf):

D[v],p[v] = d,u

return True

我们现在已经得出了第一个正确的算法：BellmanFord（见清单9-2）。它是单一来源允许任意有向或无向图的最短路径算法。如果图表包含负循环，则算法将报告这一事实并放弃。

因为所有的边都是正的，所以只有节点才能有助于节点的解决方案，它将位于假设顺序。我们不可能找到一个能帮助我们找到捷径的节点，因为这个节点离得更远，只有当它有一个负的后缘时才能给我们一个快捷方式。正后缘是对我们来说完全没用，也不是问题结构的一部分。那么，剩下的是一个DAG和拓扑结构我们想要使用的排序正是我们开始使用的假设性排序：按实际距离排序的节点。该结构的示意图见图9-2。（我马上回到问号。）

图9-2。逐渐揭开隐藏的匕首。节点用其最终距离进行标记。因为重量是正的，后缘（虚线）不能影响结果，因此不相关

这个结构与prim的算法非常相似：使用优先级队列遍历。就像普里姆一样，我们知道我们在遍历中没有发现的节点不会被放松，所以我们对他们。在我们发现的那些（和放松的那些）中，我们总是希望优先级最低的那个。在Prim 算法中，优先级是链接回遍历树的边的权重；在Dijkstra中，优先级是距离估计。当然，当我们找到快捷方式（就像新的可能的生成树边缘一样）时，优先级可以改变可以降低prim中的优先级），但正如清单7-5所示，我们可以简单地将同一个节点添加到堆的多个时间（而不是尝试修改堆条目的优先级），而不影响正确性或运行时间。结果可以在清单9-3中找到。它的运行时间是对数线性的，或者更具体地说，是q（（m+n）lg n）。其中m是边数，n是节点数。这里的理由是你需要一个（对数）（1）要从队列中提取的每个节点和（2）要放宽的每个边缘的堆操作。4 W（n）边，对于可以从开始节点到达Q（n）节点的图形，运行时间可以是简化为q（m lg n）。