简单说几句

1. 简单说几句，算法的基本逻辑请看其他文章，很多，不介绍。本文旨在提供一份python代码供各位后来学习者多一些资料理解学习动态规划法(Dynamic Programing, DP)，同时对于那些只需简单使用DP解决路径规划的人提供一个并不麻烦的途径。
2. 注意，非路径规划，非栅格图模型的，本文代码99.99%无法运行！
3. 提供DP的一个很重要的原因就是，DP是一定能获得最优解的，因此，可以作为案例最优值的获取手段。

python代码

0.预安装库

pip install lddya==5.0.1     #作者的自用库，里面有一些工具下文会用到

1.调用模版

from lddya.Algorithm.Traditional import Dynamic_Programing as DP   #导入DP算法
from lddya.Draw import ShanGeTu                        #导入栅格图的绘制模块
from lddya.Map import Map                              #导入地图文件读取模块

m = Map()
m.load_map_file('map.txt')                            # 读取地图文件
dp = DP(map_data=m.data,start=[0,0],end=[19,19])      #初始化DP，不调整任何参数的情况下，仅提供地图数据即可，本行中数据由Map.data提供，start跟end都是[y,x]格式，默认[0,0],[19,19]。
dp.run()                                              # 运行
fig = ShanGeTu(m.data,x_label='x',y_label='y')        # 初始化栅格图绘制模块
fig.draw_way(dp.way_data_best)    # 绘制路径信息，路径数据由DP.way_data_best提供。
fig.show()                        # 展示绘图结果

2.地图文件

下面为某地图文件内容，数字位置与栅格图的黑白栅格一一对应。
这篇《个人库的一些小工具》文章中介绍了地图识别的功能，需要的可以看看。

PS: 注意，Map.data本质上是基于numpy的0-1矩阵。

00000000110100000000
00111000100000100000
00100110001100100110
00000011101100000110
00110011100001110000
00110000000111011110
00000010000111011110
00001011110111011110
00001001000000000000
00001101001111000000
00000101101111000000
01110000101111000000
01110011101111000000
01110011100001010000
11000111111001000010
00000011100001110000
00000011100001111000
01100011101100001110
01101000000100000000
00000000000000000000

3.栅格图+迭代图

下图所示的栅格图即为上文的栅格数据文件对应的图，左下角栅格坐标为[0,0]，向上y增大，向右x增大。所以右上角为[19,19]。

3.DP类

如果你只是想使用DP解决问题，下面的内容就不用看了，效果不好就调参吧。考虑存在朋友仅想阅读代码，这里我附一下DP的代码供学习参考。

class Dynamic_Programing():
    def __init__(self,map_data,start = [0,0],end= [19,19]) -> None:
        '''
            Function
            --------
            parameter initilization

            Parameter
            --------
            map_data : 栅格地图数据，   2d矩阵
            start    : 起点坐标，      1*2向量 [y,x]
            end      : 终点坐标，      1*2向量 [y,x]

            Return
            ------
            None
        '''
        self.map_data = map_data
        self.map_size = map_data.shape[0]
        self.start = start
        self.end = end
        self.relation_matrix = np.zeros_like(self.map_data,dtype = np.int16)   #关系矩阵，标记方向
        self.relation_code_zhi = np.array([1,3,5,7])          #回溯方向代码，放入关系矩阵中
        self.relation_code_xie = np.array([2,4,6,8])
        self.dynamic_matrix  = np.zeros_like(self.map_data)   #动态矩阵，标记需要处理的母节点
        self.dynamic_matrix[self.end[0],self.end[0]] = 1   #初始时，母节点仅有终点
        self.static_matrix   = self.dynamic_matrix.copy()   #静态矩阵，冻结的节点(不进行任何操作)

    
    def run(self):
        while True:
            self.relation_matrix_temp = np.zeros_like(self.relation_matrix)
            self.dynamic_matrix_temp  = np.zeros_like(self.dynamic_matrix) 
            # step 1: 由需要处理的母节点进行扩散
            self.task_matrix = np.zeros_like(self.map_data)
            y_1,x_1 = np.where(self.dynamic_matrix==1)
            for k,i in enumerate(y_1):      #直线方向上的更新
                y = y_1[k]
                x = x_1[k]
                neighbours = np.array([
                    [y-1,x],
                    [y,x+1],
                    [y+1,x],
                    [y,x-1],
                ])
                cond_1 = np.logical_and(neighbours[:,0]>=0,neighbours[:,0]<self.map_size)
                cond_2 = np.logical_and(neighbours[:,1]>=0,neighbours[:,1]<self.map_size)
                allowed_index = np.logical_and(cond_1,cond_2)          #约束1：坐标范围
                allowed_rela_code = self.relation_code_zhi[allowed_index]
                allowed_neigh = neighbours[allowed_index]
                allowed_rela_code = allowed_rela_code[self.map_data[allowed_neigh[:,0],allowed_neigh[:,1]]==0] #约束2的code，因为allowed_neigh下一步变了，故要提前处理code，约束3的同理
                allowed_neigh = allowed_neigh[self.map_data[allowed_neigh[:,0],allowed_neigh[:,1]]==0]     #约束2 ： 空白栅格
                allowed_rela_code = allowed_rela_code[self.static_matrix[allowed_neigh[:,0],allowed_neigh[:,1]]==0]
                allowed_neigh = allowed_neigh[self.static_matrix[allowed_neigh[:,0],allowed_neigh[:,1]]==0]  #约束3： 不能是static
                
                a_1 = self.relation_matrix[allowed_neigh[:,0],allowed_neigh[:,1]] == 0  # 没更新的地方,需要判断吗？
                self.relation_matrix_temp[allowed_neigh[a_1][:,0],allowed_neigh[a_1][:,1]] = allowed_rela_code[a_1]
                self.relation_matrix[self.relation_matrix_temp!=0] = self.relation_matrix_temp[self.relation_matrix_temp!=0]
                self.dynamic_matrix_temp[self.relation_matrix_temp!=0] = 1 
            
            self.relation_matrix_temp = np.zeros_like(self.relation_matrix)
            for k,i in enumerate(y_1):      #斜线方向上的更新
                y = y_1[k]
                x = x_1[k]
                neighbours = np.array([
                    [y-1,x+1],
                    [y+1,x+1],
                    [y+1,x-1],
                    [y-1,x-1]
                ])
                cond_1 = np.logical_and(neighbours[:,0]>=0,neighbours[:,0]<self.map_size)
                cond_2 = np.logical_and(neighbours[:,1]>=0,neighbours[:,1]<self.map_size)
                allowed_index = np.logical_and(cond_1,cond_2)
                allowed_rela_code = self.relation_code_xie[allowed_index]
                allowed_neigh = neighbours[allowed_index]
                allowed_rela_code = allowed_rela_code[self.map_data[allowed_neigh[:,0],allowed_neigh[:,1]]==0] #约束2的code，因为allowed_neigh下一步变了，故要提前处理code，约束3的同理
                allowed_neigh = allowed_neigh[self.map_data[allowed_neigh[:,0],allowed_neigh[:,1]]==0]     #约束2 ： 空白栅格
                allowed_rela_code = allowed_rela_code[self.static_matrix[allowed_neigh[:,0],allowed_neigh[:,1]]==0]
                allowed_neigh = allowed_neigh[self.static_matrix[allowed_neigh[:,0],allowed_neigh[:,1]]==0]  #约束3： 不能是static
                a_1 = self.relation_matrix[allowed_neigh[:,0],allowed_neigh[:,1]] == 0  # 没更新的地方,需要判断吗？
                self.relation_matrix_temp[allowed_neigh[a_1][:,0],allowed_neigh[a_1][:,1]] = allowed_rela_code[a_1] 
                self.relation_matrix[self.relation_matrix_temp!=0] = self.relation_matrix_temp[self.relation_matrix_temp!=0]
                self.dynamic_matrix_temp[self.relation_matrix_temp!=0] = 1 
            
            
            self.dynamic_matrix = self.dynamic_matrix_temp.copy()   #更新下一轮的母节点(动态矩阵)
            self.static_matrix[self.dynamic_matrix!=0] = 1   #本轮的母节点全部冻结
            if self.static_matrix[self.start[0],self.start[1]] !=0:
                print('路径规划完成！')
                self._translate()
                break


    def _translate(self):
        self.way_data_best = []
        self.way_len_best = 0
        grid = self.start.copy()
        self.way_data_best.append(grid)
        while True:
            change_matrix = np.array([
                [1,0],
                [1,-1],
                [0,-1],
                [-1,-1],
                [-1,0],
                [-1,1],
                [0,1],
                [1,1]
            ])

            grid = grid+change_matrix[self.relation_matrix[grid[0],grid[1]]-1]
            if 0 in change_matrix[self.relation_matrix[grid[0],grid[1]]-1].tolist():
                self.way_len_best += 1
            else:
                self.way_len_best += 2**0.5
            self.way_data_best.append(grid)
            if (grid == self.end).all():
                self.way_data_best = np.array(self.way_data_best)
                break
        

最后，祝后来诸君学习顺利！