動態規劃之棋盤路徑問題
- 2019 年 10 月 6 日
- 筆記
動態規劃之棋盤路徑問題
1.對比
DP vs 回溯 vs 貪心
- 回溯(遞歸) – 重複計算
- 貪心 – 永遠局部最優
- DP – 記錄局部最優子結構/多種記錄值
2.棋盤路徑問題
問題描述:
如下圖所示,小人從左上角移動到右下角,總共有多少種走法.
約束條件為:粉紅色為石頭,走不通,小人走路方向只有向下與向右.
該問題可以分解f(0,0)=0,f(1,0)=1,f(0,1)=1 f(m,n)=f(m-1,n)+f(m,n-1)(此時m,n不為0)。
|
0(A) |
1 |
|---|---|
|
1 |
2(B) |
如上表所示為從棋盤中取出的左上角4個格子,填充的數據中第二行第二列(index假設從1開始)為2,表示從A到B有2種路徑,依次往下走,最終得到f(m,n)=f(m-1,n)+f(m,n-1)(此時m,n不為0)。
因此該問題是遞歸問題,同時可以通過動態規劃解決。
3.判斷是石頭還是空地
上述棋盤有個很強的約束條件,就是棋盤的約束問題,粉紅色假設為石頭,沒有粉紅色為空地,那我們就是要找到空地,從空地進行行走,下面來編寫這樣的函數。
棋盤假設為grid的二維數組,共有m行,n列。生成的二維數組中1表示石頭，0表示空位。
棋盤生成代碼：
import numpy as np m,n = 8,8 grid = np.zeros((m,n),dtype=np.int) for i in range(m): for j in range(n): if (i==1 and (j==2 or j==6)) or (i==2 and j==4) or (i==3 and (j==0 or j==2 or j==5)) or (i==4 and j==2) or (i==5 and (j==3 or j==4 or j==6)) or (i==6 and (j==1 or j==5)): grid[i][j]=1 print(grid)
輸出：
[[0 0 0 0 0 0 0 0] [0 0 1 0 0 0 1 0] [0 0 0 0 1 0 0 0] [1 0 1 0 0 1 0 0] [0 0 1 0 0 0 0 0] [0 0 0 1 1 0 1 0] [0 1 0 0 0 1 0 0] [0 0 0 0 0 0 0 0]]
判斷該棋盤中某行某列是否是空地：
# 判斷是否是空地 def validSquare(grid,m,n): if grid[m][n]==1: return False return True
4.遞歸法
- 每次先判斷當前是否是空地
- 左上角處理
- 每次遞歸都可以劃分為(1,0)或(0,1)子問題
- 第一行與第一列遞歸
- 中間行列數據遞歸
def countPath(grid,m,n): # 是否為空地，grid中0為空地，1為非空地 if not validSquare(grid,m,n): return 0 # 左上角特殊處理 if (m==0 and n==0): return 0 # (0,1)與(1,0)為1 if ((m == 0 and n == 1) or (m == 1 and n == 0)): return 1 # 第一行，第一列特殊處理 elif ((m == 0) and (n>1)): return countPath(grid, m, n - 1) elif ((n == 0) and (m>1)): return countPath(grid,m-1,n) # 其他則遞歸 return countPath(grid,m, n - 1) + countPath(grid,m - 1, n) # 申請dp數組 dp = np.zeros((m,n),dtype=np.int) print(countPath(grid,m-1,n-1))
5.動態規劃
從左上角到右下角直接使用遞推式，找到動態規劃的狀態轉移方程，然後返回最後的一個數據即可。
我們知道當第一行或者第一列中有石頭的時候，隨之後面的行或者列就走不通了，那麼直接設為0即可。
所以第一步先堆特殊的第一行與第一列進行處理。
然後堆中間行與列處理。
def countPath2(grid,m,n,dp): # 處理每一行 for i in range(m): if not validSquare(grid,i,0): for j in range(i,m): dp[j][0]=0 break dp[i][0]=1 # 處理每一列 for i in range(n): if not validSquare(grid,0,i): for j in range(i,m): dp[0][j]=0 break dp[0][i]=1 # 左上角處理 dp[0][0]=0 for i in range(1,m): for j in range(1,n): if validSquare(grid,i,j): dp[i][j]=dp[i-1][j]+dp[i][j-1] else: dp[i][j]=0 return dp[m-1][n-1]
由於從左上角到右下角與從右下角到左上角路徑對稱，那麼我們可以再寫一個從右下角到左上角來驗證之前的代碼正確性，如果正常，則兩次結果是一樣的！
下面為從右下角到左上角的動態規劃代碼：
def countPath1(grid,m,n,dp): # 處理每一行 for i in range(m-1,-1,-1): if not validSquare(grid,i,n-1): for j in range(i,m): dp[j][n-1]=0 break dp[i][n-1]=1 # 處理每一列 for i in range(n-1,-1,-1): if not validSquare(grid,m-1,i): for j in range(i,m): dp[m-1][j]=0 break dp[m-1][i]=1 dp[m-1][n-1]=0 for i in range(m-2,-1,-1): for j in range(n-2,-1,-1): if validSquare(grid,i,j): dp[i][j]=dp[i+1][j]+dp[i][j+1] else: dp[i][j]=0 return dp[0][0]
