动态规划之棋盘路径问题
动态规划之棋盘路径问题
公众号guangcity
发布于 2019-09-20 17:21:24
发布于 2019-09-20 17:21:24
动态规划之棋盘路径问题
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]
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-03-18，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录