上次提到了猫妙，回溯(Backtrack)干像，深度和廣度搜索哺徊，一些演化的算法图贸，比如規(guī)定了最大深度的深度搜索蹂季，或者叫做DFS with iterative deepening （DFS-ID），每一個(gè)的action都有一個(gè)固定的cost疏日，假設(shè)最優(yōu)方案的深度為d的話偿洁，空間和時(shí)間的復(fù)雜度：O（d）和O（b^d)。
總結(jié)一下之前講過的這幾種算法, 不難看出時(shí)間復(fù)雜度都是指數(shù)級(jí)別的
那么有沒有一些方式能把時(shí)間復(fù)雜度降低一些呢沟优？我們先來看一下動(dòng)態(tài)規(guī)劃涕滋。
上次提到了，對于一個(gè)搜索的問題挠阁，包含幾個(gè)要素：
當(dāng)前的狀態(tài)S, 到達(dá)下一個(gè)狀態(tài)的動(dòng)作a,這一動(dòng)作的代價(jià)c, 下一個(gè)狀態(tài)（Succ (s,a), successor of S）宾肺，最終的狀態(tài)。
動(dòng)態(tài)規(guī)劃實(shí)際上就是這樣的一個(gè)過程：
在當(dāng)前狀態(tài)S下侵俗，判斷出來達(dá)到下一個(gè)狀態(tài)S‘的動(dòng)作的代價(jià)爱榕，然后通過某種方式計(jì)算一下這個(gè)狀態(tài)到達(dá)最終狀態(tài)的代價(jià)。要做的就是找出來代價(jià)和最小的下一個(gè)狀態(tài)坡慌。
用這樣的一個(gè)例子一起來看一下動(dòng)態(tài)規(guī)劃的一個(gè)過程：
假設(shè)現(xiàn)在有1黔酥，2，5，10塊四種面值的紙幣跪者，現(xiàn)在問一下湊齊68塊錢最少需要多少張紙幣棵帽？
直覺地：先用10塊的6張，湊不夠10塊的渣玲，用5塊的一張逗概，再用2塊的和1塊的各一張，剛好68塊忘衍，毫無疑問這樣的方法是正確的逾苫，這其實(shí)用到了貪心的思想（Greedy Method）。
試想一下枚钓，如果現(xiàn)在的錢幣面值設(shè)置不是這樣的铅搓，而是1，5搀捷，8星掰，10 塊的面值，要湊64塊錢嫩舟，貪心的方法會(huì)選6張10塊氢烘，再選4張一塊，但這不是用的最少的家厌，8張8塊的是最少的播玖。遇到這樣的一類問題，方案就是動(dòng)態(tài)規(guī)劃的方法饭于。
假設(shè)現(xiàn)在要兌換N塊的紙幣黎棠，那么最優(yōu)的方案需要的張數(shù)n是關(guān)于N的一個(gè)這樣的遞歸函數(shù)：
n(N) = min {1+n(N-1)；1+n(N-5); 1+n(N-8); 1+n(N-10)}
很明顯有幾個(gè)隱含的條件：如果N = 1,5,8,10, n(N) = 1, 一張就夠了镰绎。選擇的紙幣的面值肯定不能超過要湊的紙幣總數(shù)脓斩，比如要湊6塊錢，8和10塊肯定用不到了畴栖。代碼實(shí)現(xiàn)也很容易：
# i_STEM,Dynamic programming
# 用1随静，5，8吗讶，10 塊的紙幣湊N塊的問題
# 遞歸
import numpy as np
value = [1,5,8,10]
N = 40
def exchange(value,N, count = [0]):
count[0]+= 1
mn = N
if N in value:
print ("Recursion times:",count[0])
return 1
for i in [int(v) for v in value if int (v) <=N]:
n = 1 + exchange(value,N-i,mem)
if n < mn:
mn = n
return mn
exchange(value,N) #
但上面這段短短的代碼燎猛，卻要花很多時(shí)間去遞歸，舉個(gè)例子照皆，要算一下湊40塊重绷，要調(diào)用20多萬次遞歸，膜毁，普通電腦可能花一分鐘左右才跑完昭卓。愤钾。那么問題出現(xiàn)在哪兒呢？不難想象候醒，很多重復(fù)的數(shù)據(jù)出現(xiàn)能颁，重新進(jìn)行計(jì)算，浪費(fèi)了大量的時(shí)間倒淫。比如伙菊，湊68塊，可能會(huì)用到前67塊各自的需要的最少的數(shù)量的紙幣敌土，才能得出最后的最優(yōu)的結(jié)果镜硕。如果把這些結(jié)果保存下來，就省去了重復(fù)計(jì)算的時(shí)間返干，這其實(shí)也是“學(xué)習(xí)”的一個(gè)過程兴枯，或者說“記憶”。很簡單的犬金，加幾行代碼就可以了。首先六剥，聲明存儲(chǔ)的變量晚顷，函數(shù)調(diào)用的時(shí)候作為參數(shù)。接著疗疟，遞歸出口多了一個(gè)该默，除了面值等于1，5策彤，8栓袖，10的之外，其他存儲(chǔ)過的最少的紙幣的張數(shù)也保存起來店诗，到時(shí)候直接調(diào)用裹刮。這樣顯示，遞歸了80多次庞瘸，調(diào)用了70多次捧弃，不到1秒鐘就跑完程序。
# i_STEM,遞歸動(dòng)態(tài)規(guī)劃
import numpy as np
value = [1,5,8,10]
N = 40
mem = np.zeros([N+1]) # 存儲(chǔ)所有N-1塊的需要的紙幣的最少的張數(shù)
def exchange(value,N, mem,count = [0,0]):
count[0]+= 1
mn = N
if N in value:
print ("Recursion times:",count[0])
return 1
elif mem[N] > 0:
count[1]+= 1
print ("Retrieval times:",count[1])
return mem[N]
for i in [int(v) for v in value if int (v) <=N]:
n = 1 + exchange(value,N-i,mem)
if n < mn:
mn = n
mem[N] = mn
return mn
exchange(value,N, mem) #
print (mem)
那么有一個(gè)問題擦囊，程序跑完之后违霞，所有1-39塊的最少的張數(shù)都會(huì)保存起來嗎？
答案是不一定瞬场，因?yàn)樵谇?0塊的張數(shù)的時(shí)候买鸽，是一個(gè)自頂向下的過程，并且贯被，40塊不一定需要的張數(shù)比20多眼五，30多塊的需要的多妆艘，自頂向下分解的時(shí)候，不一定會(huì)分解到每一個(gè)值弹砚。那么問題來了双仍，能不能找到一種方法，把1-39塊的每一種方案都找出來桌吃？
答案是肯定的朱沃，自底向上的過程可以確保頂層的問題肯定能從下面找到解答。同樣的公式：
n(N) = min {1+n(N-1)茅诱；1+n(N-5); 1+n(N-8); 1+n(N-10)}
在第一種方案中逗物，n（N）代表遞歸的解決方案，這里n（N）表示的是存儲(chǔ)的最優(yōu)方案的值瑟俭，也即不是去遞歸調(diào)用翎卓，而是直接從存儲(chǔ)里面去取值，也就是說我們不需要使用遞歸就可以計(jì)算出來摆寄，無非是在原有的基礎(chǔ)上試探所有四種紙幣的可行性和解決方案是否最優(yōu)失暴。在程序?qū)崿F(xiàn)的時(shí)候，每個(gè)n(N)的初始值都是N,也即微饥，最壞的方案是都用1塊去湊逗扒，然后每求一個(gè)n（N），依據(jù)N的大小欠橘，考慮這四種紙幣拼湊的情況矩肩，在n(N-1), n(N-5), n(N-8), n(N-10)的基礎(chǔ)上加1取值即可。這樣的話時(shí)間復(fù)雜度是O（4*N）肃续，空間復(fù)雜度O（N）黍檩。來看一下代碼的實(shí)現(xiàn)：
# i_STEM,自底向上動(dòng)態(tài)規(guī)劃
import numpy as np
value = [1,5,8,10]
N = 40
# 存儲(chǔ)最優(yōu)的方案，N+1個(gè)0的list,這樣保證下標(biāo)是0-40始锚，41個(gè)數(shù)刽酱，雖然0下標(biāo)的位置用不到,
# cost = [0]*(N + 1)
cost = np.zeros([N+1])
def exchange(value, N, cost):
# N重循環(huán)
for i in range(1,N+1):
# 初始化為最差的方案，全部用1塊
cost[i] = i
# 最多四重循環(huán)
for j in [k for k in value if k <= i]:
# 讀取i-j塊需要的張數(shù)瞧捌，再加一張即可肛跌，j一定是不大于i，需要注意的是cost[0]=0保持不變
cost_temp = cost[i-j] + 1
if cost_temp <= cost[i]:
cost[i] = cost_temp
return cost
exchange(value, N, cost)
如果要想存儲(chǔ)解決的方案察郁，也即哪些紙幣被用來去湊N塊衍慎，聲明另外一個(gè)變量，cost皮钠，求N塊的方案稳捆，存儲(chǔ)最后一個(gè)紙幣的數(shù)額m，也即coin[N]=m麦轰，再找出N-m的最后一張紙幣的數(shù)額乔夯，這樣就可以把整個(gè)方案的找出來砖织。來看一下代碼實(shí)現(xiàn)：
# i_STEM,自底向上動(dòng)態(tài)規(guī)劃，存儲(chǔ)方案
import numpy as np
value = [1,5,8,10]
N = 40
# 存儲(chǔ)最優(yōu)的方案末荐，N+1個(gè)0的list,這樣保證下標(biāo)是0-40侧纯，41個(gè)數(shù)，雖然0下標(biāo)的位置用不到,
# cost = [0]*(N + 1)
cost = np.zeros([N+1])
# 求N塊的方案甲脏，存儲(chǔ)最后一個(gè)紙幣的數(shù)額m眶熬，也即coin[N]=m，再找出N-m的最后一張紙幣的數(shù)額块请，這樣就可以把整個(gè)方案的找出來娜氏，
coin = np.zeros([N+1])
def exchange(value, N, cost):
# N重循環(huán)
for i in range(1,N+1):
# 初始化為最差的方案，全部用1塊
cost[i] = i
# 最多四重循環(huán)
for j in [k for k in value if k <= i]:
# 讀取i-j塊需要的張數(shù)墩新，再加一張即可贸弥，j一定是不大于i，需要注意的是cost[0]=0保持不變
cost_temp = cost[i-j] + 1
if cost_temp <= cost[i]:
cost[i] = cost_temp
coin[i] = j
return cost,coin
exchange(value, N, cost)
簡單的總結(jié)海渊，上面的前三種方案中绵疲，第一種單純使用遞歸，而不使用存儲(chǔ)的話臣疑，花費(fèi)大量的時(shí)間盔憨；第二種方案，使用了一些存儲(chǔ)朝捆，同時(shí)也有遞歸調(diào)用般渡，節(jié)約了大量的時(shí)間懒豹；第三種方案芙盘，最大限度的使用存儲(chǔ)，沒有使用遞歸脸秽，自底向上的解決了問題儒老，也節(jié)省了很多的時(shí)間。適當(dāng)?shù)氖褂么鎯?chǔ)记餐，來節(jié)約大量的時(shí)間成本驮樊，還是很合算的。
類似的拿少量存儲(chǔ)去節(jié)省大量時(shí)間的例子還有很多片酝，在python中囚衔，遞歸調(diào)用的層數(shù)不能超過1000層，再考慮到時(shí)間成本雕沿，所以大量的運(yùn)算的時(shí)候练湿，合適的使用存儲(chǔ)很有必要。除此之外审轮，動(dòng)態(tài)規(guī)劃在很多領(lǐng)域中都可以見到肥哎，比如在生物信息學(xué)中辽俗，做DNA序列的alignment的時(shí)候，動(dòng)態(tài)規(guī)劃是非常常見的例子篡诽，比如Needleman–Wunsch 算法
再回到搜索中來崖飘，搜索中的動(dòng)態(tài)規(guī)劃的幾個(gè)要素上面提到了，當(dāng)前狀態(tài)S杈女，動(dòng)作a朱浴，動(dòng)作的代價(jià)Cost(S,a)和下一個(gè)狀態(tài)Succ(s,a)，以及終止?fàn)顟B(tài)的判斷碧信。與上面所說的不太一樣的地方是赊琳，上面的問題每一個(gè)動(dòng)作的代價(jià)是一樣的，增加一張紙幣砰碴，只是這張紙幣選擇的上一個(gè)狀態(tài)不盡相同躏筏，導(dǎo)致整個(gè)方案的代價(jià)也不同，取其中最優(yōu)的呈枉。
在搜索中趁尼，
FutureCost (S) = 0， 如果是終止?fàn)顟B(tài)猖辫；
FutureCost (S) = min [Cost(S,a) + FutureCost (Succ(s,a))], 不是終止?fàn)顟B(tài)酥泞。
好，動(dòng)態(tài)規(guī)劃是非常重要的一種思想啃憎，我們從時(shí)間和存儲(chǔ)成本的角度簡單的分析了一下這樣的應(yīng)用芝囤，在不同的行業(yè)領(lǐng)域，都會(huì)不同的實(shí)際應(yīng)用的方案辛萍，但抽象化的中心思想是一致的悯姊。后面遇到更經(jīng)典的動(dòng)態(tài)規(guī)劃案例，再補(bǔ)充分享贩毕。下次來看一下搜索中 uniform cost search的實(shí)現(xiàn)悯许。
Reference:
