注：本節中我給定下面三個重要詞匯的中文翻譯分別是：Induction(推導)、Recursion(遞歸)和Reduction(規約)

本節主要介紹算法設計的三個核心知識：Induction(推導)、Recursion(遞歸)和Reduction(規約)，這是原書的重點和難點部分

正如標題所示，本節主要介紹下面三部分內容：

? Reduction means transforming one problem to another. We normally reduce an unknown problem to one we know how to solve. The reduction may involve transforming both the input (so it works with the new problem) and the output (so it’s valid for the original problem).

Reduction(規約)意味著對問題進行轉換，例如將一個未知的問題轉換成我們能夠解決的問題，轉換的過程可能涉及到對問題的輸入輸出的轉換。[問題規約在證明一個問題是否是NP完全問題時經常用到，如果我們能夠將一個問題規約成一個我們已知的NP完全問題的話，那么這個問題也是NP完全問題]

下面給幅圖你就能夠明白了，實際上很多時候我們遇到一個問題時都是找一個我們已知的類似的能夠解決的問題，然后將這個我們新問題A規約到那個已知的問題B，中間經過一些輸入輸出的轉換，我們就能夠解決新問題A了。

? Induction (or, mathematical induction) is used to show that a statement is true for a large class of objects (often the natural numbers). We do this by first showing it to be true for a base case (such as the number 1) and then showing that it “carries over” from one object to the next (if it’s true for n –1, then it’s true for n).

Induction(推導)是一個數學意義上的推導，類似數學歸納法，主要是用來證明某個命題是正確的。首先我們證明對于基礎情況(例如在k=1時)是正確的，然后證明該命題遞推下去都是正確的(一般假設當k=n-1時是正確的，然后證明當k=n時也是正確的即可)

? Recursion is what happens when a function calls itself. Here we need to make sure the function works correctly for a (nonrecursive) base case and that it combines results from the recursive calls into a valid solution.

Recursion(遞歸)經常發生于一個函數調用自身的情況。遞歸函數說起來簡單，但是實現不太容易，我們要確保對于基礎情況(不遞歸的情況)能夠正常工作，此外，對于遞歸情況能夠將遞歸調用的結果組合起來得到一個有效的結果。

以上三個核心有很多相似點，比如它們都專注于求出目標解的某一步，我們只需要仔細思考這一步，剩下的就能夠自動完成了。如果我們更加仔細地去理解它們，我們會發現，Induction(推導)和Recursion(遞歸)其實彼此相互對應，也就是說一個Induction能夠寫出一個相應的Recursion，而一個Recursion也正好對應著一個Induction式子，也可以換個方式理解，Induction是從n-1到n的推導，而Recursion是從n到n-1的遞歸(下面有附圖可以幫助理解)。此外，Induction和Recursion其實都是某種Reduction，即Induction和Recursion的本質就是對問題進行規約！為了能夠對問題使用Induction或者說Recursion，Reduction一般是將一個問題變成另一個只是規模減小了的相同問題。

你也許會覺得奇怪，不對啊，剛才不是說Reduction是將一個問題規約成另一個問題嗎？現在怎么又說成是將一個問題變成另一個只是規模減小了的相同問題了？其實，Reduction是有兩種的，上面的兩種都是Reduction！還記得前面介紹過的遞歸樹嗎？那其實就是將規模較大的問題轉換成幾個規模較小的問題，而且問題的形式并沒有改變，這就是一種Reduction。你可以理解這種情況下Reduction是降維的含義，也就類似機器學習中的Dimension Reduction，對高維數據進行降維了，問題保持不變。

These are two major variations of reductions: reducing to a different problem and reducing to a shrunken version of the same.

再看下下面這幅圖理解Induction和Recursion之間的關系

[關于它們三個的關系的原文闡述：Induction and recursion are, in a sense, mirror images of one another, and both can be seen as examples of reduction. To use induction (or recursion), the reduction must (generally) be between instances of the same problem of different sizes. ]

[看了原書你會覺得，作者介紹算法的方式很特別，作者有提到他的靈感來自哪里：In fact, much of the material was inspired by Udi Manber’s wonderful paper “Using induction to design algorithms” from 1988 and his book from the following year, Introduction to Algorithms: A Creative Approach.]

也許你還感覺很暈，慢慢地看了后面的例子你就明白了。在介紹例子之前呢，先看下遞歸和迭代的異同，這個很重要，在后面介紹動態規劃算法時我們還會反復提到它們的異同。

[Induction is what you use to show that recursion is correct, and recursion is a very direct way of implementing most inductive algorithm ideas. However, rewriting the algorithm to be iterative can avoid the overhead and limitations of recursive functions in most (nonfunctional) programming languages. ]

有了Induction和Recursion，我們很容易就可以將一個inductive idea采用遞歸(recursion)的方式實現，根據我們的編程經驗(事實也是如此)，任何一個遞歸方式的實現都可以改成非遞歸方式(即迭代方式)實現(反之亦然)，而且非遞歸方式要好些，為什么呢？因為非遞歸版本相對來講運行速度更快，因為沒有用棧去實現，也避免了棧溢出的情況，python中對棧深度是有限制的。

舉個例子，下面是一段遍歷序列的代碼，如果大小設置為100沒有問題，如果設置為1000就會報RuntimeError的錯誤，提示超出了最大的遞歸深度。[當然，大家都不會像下面那樣寫代碼對吧，這只是一個例子]

def trav(seq, i=0):

if i == len(seq): return

#print seq

trav(seq, i + 1)

trav(range(1000)) # RuntimeError: maximum recursion depth exceeded

所以呢，很多時候雖然遞歸的思路更好想，代碼也更好寫，但是迭代的代碼更加高效一些，在動態規劃中還可以看到迭代版本還有其他的優點，當然，它還有些缺點，比如要考慮迭代的順序，如果迫不及待想知道請移步閱讀

下面我們通過排序來梳理下我們前面介紹的三個核心內容

我們如何對排序問題進行reduce呢？很顯然，有很多種方式，假如我們將原問題reduce成兩個規模為原來一半的子問題，我們就得到了合并排序(這個我們以后還會詳細介紹)；假如我們每次只是reduce一個元素，比如假設前n-1個元素都排好序了，那么我們只需要將第n個元素插入到前面的序列即可，這樣我們就得到了插入排序；再比如，假設我們找到其中最大的元素然后將它讓在位置n上，一直這么下去我們就得到了選擇排序；繼續思考下去，假設我們找到某個元素(比如第k大的元素)，然后將它放在位置k上，一直這么下去我們就得到了快速排序(這個我們以后還會詳細介紹)。怎么樣？我們前面學過的排序經過

這么一些reduce基本上都很清晰了對吧？

下面通過代碼來體會下插入排序和選擇排序的兩個不同版本

遞歸版本的插入排序

def ins_sort_rec(seq, i):

if i == 0: return??# Base case -- do nothing

ins_sort_rec(seq, i - 1)??# Sort 0..i-1

j = i??# Start "walking" down

while j > 0 and seq[j - 1] > seq[j]:??# Look for OK spot

seq[j - 1], seq[j] = seq[j], seq[j - 1]??# Keep moving seq[j] down

j -= 1??# Decrement j

from random import randrange

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

ins_sort_rec(seq, len(seq)-1)

改成迭代版本的插入排序如下

def ins_sort(seq):

for i in range(1, len(seq)):??# 0..i-1 sorted so far

j = i??# Start "walking" down

while j > 0 and seq[j - 1] > seq[j]:??# Look for OK spot

seq[j - 1], seq[j] = seq[j], seq[j - 1]??# Keep moving seq[j] down

j -= 1??# Decrement j

seq2 = [randrange(1000) for i in range(100)]

ins_sort(seq2)

你會發現，兩個版本差不多，但是遞歸版本中list的size不能太大，否則就會棧溢出，而迭代版本不會有問題，還有一個區別就是方法參數，一般來說遞歸版本的參數都會多些

遞歸版本和迭代版本的選擇排序

def sel_sort_rec(seq, i):

if i == 0: return??# Base case -- do nothing

max_j = i??# Idx. of largest value so far

for j in range(i):??# Look for a larger value

if seq[j] > seq[max_j]: max_j = j??# Found one? Update max_j

seq, seq[max_j] = seq[max_j], seq??# Switch largest into place

sel_sort_rec(seq, i - 1)??# Sort 0..i-1

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

sel_sort_rec(seq, len(seq)-1)

def sel_sort(seq):

for i in range(len(seq) - 1, 0, -1):??# n..i+1 sorted so far

max_j = i??# Idx. of largest value so far

for j in range(i):??# Look for a larger value

if seq[j] > seq[max_j]: max_j = j??# Found one? Update max_j

seq, seq[max_j] = seq[max_j], seq??# Switch largest into place

seq2 = [randrange(1000) for i in range(100)]

sel_sort(seq2)

下面我們來看個例子，這是一個經典的“名人問題”，我們要從人群中找到那個名人，所有人都認識名人，而名人則任何人都不認識。

[這個問題的一個變種就是從一系列有依賴關系的集合中找到那個依賴關系最開始的元素，比如多線程環境下的線程依賴問題，后面將要介紹的拓撲排序是解決這類問題更實際的解法。A more down-to-earth version of the same problem would be examining a set of dependencies and trying to find a place to start. For example, you might have threads in a multithreaded application waiting for each other, with even some cyclical dependencies (so-called deadlocks), and you’re looking for one thread that isn’t waiting for any of the others but that all of the others are dependent on. ]

在進一步分析之前我們可以發現，很顯然，我們可以暴力求解下，G[v]為True表示 u 認識 v。

def naive_celeb(G):

n = len(G)

for u in range(n):??# For every candidate...

for v in range(n):??# For everyone else...

if u == v: continue??# Same person? Skip.

if G[v]: break??# Candidate knows other

if not G[v]: break??# Other doesn't know candidate

else:

return u??# No breaks? Celebrity!

return None??# Couldn't find anyone

用下面代碼進行測試，得到正確結果57

from random import *

n = 100

G = [[randrange(2) for i in range(n)] for i in range(n)]

c = 57 # For testing

for i in range(n):

G[c] = True

G[c] = False

print naive_celeb(G) #57

上面的暴力求解其實可以看做是一個reduce，每次reduce一個人，確定他是否是名人，顯然這樣做并不高效。那么，對于名人問題我們還可以怎么reduce呢？假設我們還是將規模為n的問題reduce成規模為n-1的問題，那么我們要找到一個非名人(u)，也就是找到一個人(u)，他要么認識其他某個人(v)，要么某個人(v)不認識他，也就是說，對于任何G[v]，如果G[v]為True，那么消去u；如果G[v]為False，那么消去v，這樣就可以明顯加快查找的速度！

基于上面的想法就有了下面的python實現，第二個for循環是用來驗證我們得到的結果是否正確(因為如果我們保證有一個名人的話那么結果肯定正確，但是如果不能保證的話，那么結果就要進行驗證)

def celeb(G):

n = len(G)

u, v = 0, 1??# The first two

for c in range(2, n + 1):??# Others to check

if G[v]:

u = c??# u knows v? Replace u

else:

v = c??# Otherwise, replace v

if u == n:

c = v??# u was replaced last; use v

else:

c = u??# Otherwise, u is a candidate

for v in range(n):??# For everyone else...

if c == v: continue??# Same person? Skip.

if G[c][v]: break??# Candidate knows other

if not G[v][c]: break??# Other doesn't know candidate

else:

return c??# No breaks? Celebrity!

return None??# Couldn't find anyone

看起來還不錯吧，我們將一個O(n2)的暴力解法變成了一個O(n)的快速解法。

[看書看到這里時，我想起了另一個看起來很相似的問題，從n個元素中找出最大值和最小值。如果我們單獨地來查找最大值和最小值，共需要(2n-2)次比較(也許你覺得還可以少幾次，但都還是和2n差不多對吧)，但是，如果我們成對來處理，首先比較第一個元素和第二個元素，較大的那個作為當前最大值，較小的那個作為當前最小值(如果n是奇數的話，為了方便可以直接令第一個元素既是最大值又是最小值)，然后向后移動，每次取兩個元素出來先比較，較小的那個去和當前最小值比較，較大的那個去和當前最大值比較，這樣的策略至多需要 3?n2? 次比較。兩個問題雖然完全沒關系，但是解決方式總有那么點千絲萬縷有木有？]

接下來我們看另一個更加重要的例子，拓撲排序，這是圖中很重要的一個算法，在后面介紹到圖算法的時候我們還會提到拓撲排序的另一個解法，它的應用范圍也非常廣，除了前面的依賴關系例子外，還有一個最突出的例子就是類Linux系統中軟件的安裝，每當我們在終端安裝一個軟件或者庫時，它會自動檢測它所依賴的那些部件(components)是否安裝了，如果沒有那么就先安裝那些依賴項。此外，后面

下圖是一個有向無環圖(DAG)和它對應的拓撲排序結果

拓撲排序這個問題怎么進行reduce呢？和前面一樣，我們最直接的想法可能還是reduce one element，即去掉一個節點，先解決剩下的(n-1)個節點的拓撲排序問題，然后將這個去掉的節點插入到合適的位置，這個想法的實現非常類似前面的插入排序，插入的這個節點(也就是前面去掉的節點)的位置是在前面所有對它有依賴的節點之后。

def naive_topsort(G, S=None):

if S is None: S = set(G)??# Default: All nodes

if len(S) == 1: return list(S)??# Base case, single node

v = S.pop()??# Reduction: Remove a node

seq = naive_topsort(G, S)??# Recursion (assumption), n-1

min_i = 0

for i, u in enumerate(seq):

if v in G: min_i = i + 1??# After all dependencies

seq.insert(min_i, v)

return seq

G = {'a': set('bf'), 'b': set('cdf'),'c': set('d'), 'd': set('ef'), 'e': set('f'), 'f': set()}

print naive_topsort(G) # ['a', 'b', 'c', 'd', 'e', 'f']

上面這個算法是平方時間的，還有沒有其他的reduction策略呢？前面的解法類似插入排序，既然又是reduce一個元素，很顯然我們可以試試類似選擇排序的策略，也就是說，我們找到一個節點，然后把它放在第一個位置上(后面有道練習題思考如果是放在最后一個位置上怎么辦)，假設我們直接就是將這個節點去掉會怎樣呢？如果剩下的圖還是一個DAG的話我們就將原來的問題規約成了一個相似但是規模更小的問題對不對？但是問題是我們選擇哪個節點會使得剩下的圖還是一個DAG呢？很顯然，如果一個節點的入度為0，也就是說沒有任何其他的節點依賴于它，那么它肯定可以直接安全地刪除掉對不對？！

基于上面的思路就有了下面的解法，每次從圖中刪除一個入度為0的節點

def topsort(G):

count = dict((u, 0) for u in G)??# The in-degree for each node

for u in G:

for v in G:

count[v] += 1??# Count every in-edge

Q = [u for u in G if count == 0]??# Valid initial nodes

S = []??# The result

while Q:??# While we have start nodes...

u = Q.pop()??# Pick one

S.append(u)??# Use it as first of the rest

for v in G:

count[v] -= 1??# "Uncount" its out-edges

if count[v] == 0:??# New valid start nodes?

Q.append(v)??# Deal with them next

return S

[擴展知識：有意思的是，拓撲排序還和Python Method Resolution Order 有關，也就是用來確定某個方法是應該調用該實例的還是該實例的父類的還是繼續往上調用祖先類的對應方法。對于單繼承的語言這個很容易，順著繼承鏈一直往上找就行了，但是對于Python這類多重繼承的語言則不簡單，它需要更加復雜的策略，Python中使用了C3 Method Resolution Order，我不懂，

本章后面作者提到了一些其他的內容

1.Strong Assumptions

主要對于Induction，為了更加準確方便地從n-1遞推到n，常常需要對問題做很強的假設。

2.Invariants and Correctness

循環不變式，這在算法導論上有詳細介紹，循環不變式是用來證明某個算法是正確的一種方式，主要有下面三個步驟[這里和算法導論上介紹的不太一樣，道理類似]：

(1). Use induction to show that it is, in fact, true after each iteration.

(2). Show that we’ll get the correct answer if the algorithm terminates.

(3). Show that the algorithm terminates.

3.Relaxation and Gradual Improvement

松弛技術是指某個算法使得當前得到的解有進一步的提升，越來越接近最優解(準確解)，這個技術非常實用，每次松弛可以看作是向最終解前進了“一步”，我們的目標自然是希望松弛的次數越少越好，關鍵就是要確定松弛的順序(好的松弛順序可以讓我們直接朝著最優解前進，縮短算法運行時間)，后面要介紹的

4.Reduction + Contraposition = Hardness Proof

規約是用于證明一個問題是否是一個很難的問題的好方式，假設我們能夠將問題A規約至問題B，如果問題B很簡單，那么問題A肯定也很簡單。逆反一下我們就得到，如果問題A很難，那么問題B就也很難。比如，我們知道了哈密頓回路問題是NP完全問題，要證明哈密頓路徑問題也是NP完全問題，就可以將哈密頓回路問題規約為哈密頓路徑問題。

[這里作者并沒有過多的提到問題A規約至問題B的復雜度，算法導論中有提到，作者可能隱藏了規約的復雜度不大的含義，比如說多項式時間內能夠完成，也就是下面的fast readuction]

“fast + fast = fast.” 的含義是：fast readuction + fast solution to B = fast solution to A

兩條重要的規約經驗：

? If you can (easily) reduce A to B, then B is at least as hard as A.

? If you want to show that X is hard and you know that Y is hard, reduce Y to X.

5.Problem Solving Advice

作者提供的解決一個問題的建議：

(1)Make sure you really understand the problem.

搞明白你要解決的問題

What is the input? The output? What’s the precise relationship between the two? Try to represent the problem instances as familiar structures, such as sequences or graphs. A direct, brute-force solution can sometimes help clarify exactly what the problem is.

(2)Look for a reduction.

尋找一個規約方式

Can you transform the input so it works as input for another problem that you can solve? Can you transform the resulting output so that you can use it? Can you reduce an instance if size n to an instance of size k < n and extend the recursive solution (inductive hypothesis) back to n?

(3)Are there extra assumptions you can exploit?

還有其他的重要的假設條件嗎，有時候我們如果只考慮該問題的特殊情況的話沒準能夠有所收獲

Integers in a fixed value range can be sorted more efficiently than arbitrary values. Finding the shortest path in a DAG is easier than in an arbitrary graph, and using only non-negative edge weights is often easier than arbitrary edge weights.

問題4-18. 隨機生成DAG圖

Write a function for generating random DAGs. Write an automatic test that checks that topsort gives a valid orderings, using your DAG generator.

You could generate DAGs by, for example, randomly ordering the nodes, and add a random number of forward-pointing edges to each of them.

問題4-19. 修改拓撲排序

Redesign topsort so it selects the last node in each iteration, rather than the first.

This is quite similar to the original. You now have to maintain the out-degrees of the remaining nodes, and insert each node before the ones you have already found. (Remember not to insert anything in the beginning of a list, though; rather, append, and then reverse it at the end, to avoid a quadratic running time.)

[注意是使用append然后reverse，而不要使用insert]

總結

以上是生活随笔為你收集整理的python 递归 写平方_Python算法：推导、递归和规约的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。