动态规划
背景知识
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。
动态规划算法的求解思路可以分为两种：策略迭代和价值迭代
策略迭代
代码实现
import numpy as np
# 0是地面，1是陷阱，2是终点
x=3
y=12
map_matrix = [[0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1,1,1,1,2]]
map_move_pi = np.zeros((x,y,4))+0.25
map_value = np.zeros((x,y))
# 在当前位置下做一个动作，可以是上下左右任意一个,并返回对应的奖励
def move(row,col,action):
if map_matrix[row][col] in [1,2]:
return row,col,0
if action==0:
row-=1
if action ==1:
row+=1
if action==2:
col-=1
if action ==3:
col+=1
row = max(0, row)
row = min(x-1, row)
col = max(0, col)
col = min(y-1, col)
if map_matrix[row][col] ==1:
return row,col,-100+0.9*map_value[row][col]
return row,col,-1+0.9*map_value[row][col]
def change_value():
new_value = np.zeros((x,y))
for i in range(len(new_value)):
for j in range(len(new_value[0])):
action_value=np.zeros(4)
for n in range(4):
_,_,action_value[n] = move(i,j,n)
action_value *=map_move_pi[i][j]
new_value[i][j] = sum(action_value)
return new_value
def change_pi():
new_pi = np.zeros((x,y,4))
for i in range(len(new_pi)):
for j in range(len(new_pi[0])):
action_value=[0,0,0,0]
for n in range(4):
_,_,action_value[n] = move(i,j,n)
max_value = max(action_value)
count = sum([1 if i==max_value and i!=0 else 0 for i in action_value])
if count!=0:
new_pi[i][j][0] = 1/count if action_value[0]==max_value else 0
new_pi[i][j][1] = 1/count if action_value[1]==max_value else 0
new_pi[i][j][2] = 1/count if action_value[2]==max_value else 0
new_pi[i][j][3] = 1/count if action_value[3]==max_value else 0
else:
new_pi[i][j]=[0,0,0,0]
return new_pi
for _ in range(100):
for _ in range(100):
map_value = change_value()
map_move_pi = change_pi()
print(map_move_pi)
print(map_value)
价值迭代
价值迭代相比于策略迭代主要不同就在于价值更新时只选择价值最大的动作作为当前位置的价值。
代码实现
def change_value():
new_value = np.zeros((x,y))
for i in range(len(new_value)):
for j in range(len(new_value[0])):
action_value=np.zeros(4)
for n in range(4):
_,_,action_value[n] = move(i,j,n)
new_value[i][j] = max(action_value)
return new_value
