動態規劃之理論分析

公眾號程序員學長 2021-08-15 19:48:18 阅读数:61

本文一共[544]字,预计阅读时长:1分钟~
之理 分析

     大家好,經過前兩篇的分析,相信大家對動態規劃都有了一定的認識,也能感受到動態規劃强大的算法思想。今天我們就來總結一下動態規劃能解决哪些問題,以及解决動態規劃問題的思考過程是怎麼樣的?我們一起出發吧。

一、問題模型

     動態規劃一般是用來解决最優解。而在解决的過程中是需要經曆多個階段的决策。每個階段都會對應一組狀態。我們需要找到一組决策,經過這些决策後,能求出問題的最優解。我們這類問題抽象成“多階段决策最優模型”。

      動態規劃還有三大特征,分別是最優子結構、無後效性和重複子問題,只有當原問題滿足這三大特征時,我們才能使用動態規劃的算法思想來解决。下面我們來分別看一下這三個特征。

      1.最優子結構

     最優子結構規定了原問題和子問題的關系。原問題的最優解包含子問題的最優解。反過來說,我們可以通過子問題的最優解來求出原問題的最優解。

      2.無後效性

     (1)無後效性是指在推導後面階段狀態的時候,只依賴於前面階段的的狀態,而不會去關心這個狀態是怎麼一步步得來的。比如斐波那契數列F(5)=F(4)+F(3),則可以看出F(5)只依賴於F(4)和F(3)這兩個狀態的值,而不用管他們是如何得來的。

     (2)一旦某個狀態確定了,就不受之後階段的决策影響。

     3.重複子問題

     就是原問題經過拆分成多個子問題時,子問題和子問題之間存在重複計算的情况。

     下面我們來結合實例,來比較透徹的了解一下上面的理論部分。

     問題描述:我們假設有一個n*n的矩陣w[n][n](矩陣中存儲正整數)。棋子從矩陣的左上角開始移動到矩陣的右下角。棋子每次只能向下或者向右移動一步。棋子可以有很多不同的路徑走完這個矩 陣。我們把每條路徑經過的數字相加作為路徑長度,那最短的路徑長度是多少呢?

     

    我們從start開始走,一直走到end比特置,一共需要走2*(n-1)步,也就對應這2*(n-1)個階段,每個階段都有向下走還是向右走兩種决策,不同的决策對應著不同的狀態。所以這符合多階段决策,而最後求解的是最短路徑長度,所以符合動態規劃的問題模型。

    接下來我們看它是否符合動態規劃的三個特征呢?如下所示,從(0,0)比特置走到(1,1)比特置有兩種走法,所以符合重複子問題。

    

      下面我們再了看一下無後效性這個特征。我們要想走到(i,j)這個比特置,我們只能通過(i-1,j)和(i,j-1)這兩個比特置移動過來,也就是說,我們只需要關心(i-1,j)和(i,j-1)這兩個比特置的狀態,而不必關系是如何從(0,0)比特置走到這個比特置的。而且,我們這裏只允許向下或者向右走,不允許後退,所以前面階段的狀態確定之後,就不會被後面階段的决策所改變。所以這個問題是符合“無後效性”這個特征的。

      我們把從(0,0)比特置走到(i,j)比特置的最短路徑記為為min(i,j),因為我們只能向右或者向後移動,所以我們只能從(i-1,j)和(i,j-1)兩個比特置到達(i,j)。換句話說,就是min(i,j)只能通過min(i-1,j)和min(i,j-1)兩個狀態推導出來。所以這個問題就符合“最優子結構”。

min(i,j)=w[i][j]+min(min(i-1,j),min(i,j-1))

所以這個問題是符合動態規劃問題模型的,所以我們可以采用動態規劃思想來解决這個問題。

二、解决思路

   解决動態規劃問題,一般有狀態轉移錶法和狀態轉移方程法這兩種方法。

    1.狀態轉移錶法:

     我們先定義一個狀態錶,一般狀態錶都是二維的。我們根據决策的先後順序,從前往後,根據遞歸關系,分階段的填充狀態錶中的每個狀態。最後,我們把遞歸填錶的過程翻譯成代碼就完成了。我們接下來看如何用狀態轉移錶法來求最短路徑這個問題的。我們畫出一個二維數組,錶中的行、列錶示棋子所在的比特置,錶中的數值錶示從起點到這個比特置的最短路徑。然後,我們按照决策過程依次去填錶,前兩步的走法如下圖所示:

     我們來看一下代碼如何實現。     

def minDis(data,n):
status=[[0 for _ in range(n)] for _ in range(n)]
sum=0
#第一行賦值
for i in range(n):
sum=sum+data[0][i]
status[0][i]=sum
#第一列賦值
sum=0
for i in range(n):
sum=sum+data[i][0]
status[i][0]=sum
for i in range(1,n):
for j in range(1,n):
status[i][j]=data[i][j]+min(status[i-1][j],status[i][j-1])
return status[n-1][n-1]
​
​
data=[[1,3,5,7,2],
[3,6,5,2,1],
[7,4,1,6,5],
[1,3,8,2,3],
[4,3,1,6,4]]
n=5
print(minDis(data,n))

​2.狀態轉移方程法

    狀態轉移方程法和遞歸的解題思路類似。我們根據最優子結構,寫出遞推公式,也就是所謂的狀態轉移方程。然後根據狀態轉移方程,實現代碼就好了。這裏一般有兩種實現方法,一種是遞歸加備忘錄方法,另一種是迭代遞推。

     我們看這個最短路徑的例子,它的狀態轉移方程如下所示:

min(i,j)=w[i][j]+min(min(i-1,j),min(i,j-1))

我們這裏采用遞歸加備忘錄方法來實現,另一種迭代遞推的實現和狀態轉移錶法的代碼實現是一致的,只是思路不同而已。

import sys
data=[[1,3,5,7,2],
[3,6,5,2,1],
[7,4,1,6,5],
[1,3,8,2,3],
[4,3,1,6,4]]
n=5
mem=[[0 for _ in range(5)] for _ in range(5)]
def minDis(i,j):
if i==0 and j==0:
return data[0][0]
if mem[i][j]>0:
return mem[i][j]
minLeft = sys.maxsize
if j-1>=0:
minLeft=minDis(i,j-1)
minUp = sys.maxsize
if i-1>=0:
minUp=minDis(i-1,j)
current=data[i][j]+min(minLeft,minUp)
mem[i][j]=current
return current
​
print(minDis(n-1,n-1))

到這裏為止,我們的動態規劃就聊完了。希望你已經對動態規劃算法思想有所掌握。如果沒有明白也沒關系,多做幾道題,然後回過頭來再看,一定會有收獲的。

      更多硬核知識,請關注公眾號。

     

 

版权声明:本文为[公眾號程序員學長]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/08/20210815194810508M.html