动态规划-------最短路径问题

　　-最短路径，即给定一张地图，求从一个地方到另一个地方的最短路径，如下所示，从起点（0，0）到终点（3，3），每一次只能往左或者往右走，求到达终点的最短路径总长是多少？

　　回溯法：决策树，用函数f(x,y,z)表示决策树，其中x表示往下，y表示往右，Z表示最短路径之和

　　动态规划法：我们采用一个全新的表格来记录最佳值，每到一个地方实现方式为min(往左，往右)的最小值。

　　初始化(第0行，第0列)

　　第一行

　　依此类推到最后一行：

　　从而可以推出状态转移方程：

      min_path(x,y)=min(pathValues[x][y]+min_path(x,y-1),pathValues[x][y]+min_path(x-1,y))

　　算法实现：

 1 #最短路径问题
 2 import numpy as np
 3 
 4 
 5 def shorPathSolution(path):
 6     shortPath =[[-1 for col in range(len(path))] for row in range(len(path[0]))]
 7 
 8     shortPathValues =np.array(shortPath)#创建二维数组，用于记录最短路径的值
 9     #short
10 
11     for i in range(len(path)):
12 
13         for j in range(len(path[i])):
14             # 初始化第一行的值
15             if i==0:
16                 if j ==0:
17                     shortPathValues[i][j] = path[i][j]
18                 else:
19                     shortPathValues[i][j] = path[i][j] + shortPathValues[i][j-1]
20             # 初始化第一列的值
21             elif j == 0:
22                 shortPathValues[i][j] = shortPathValues[i-1][j] + path[i][j]
23             else:
24                 #计算每到一个位置的最短路径
25                 shortPathValues[i][j] = min(shortPathValues[i-1][j] + path[i][j],path[i][j] + shortPathValues[i][j-1])
26     for i in range(len(shortPathValues)):
27         for j in range(len(shortPathValues[j])):
28             print(shortPathValues[i][j], end="    ")
29         print()
30     print(shortPathValues[-1][-1])
31 path = [(1,3,5,9),(2,1,3,4),(5,2,6,7),(6,8,4,3)]
32 shorPathSolution(path)

输出结果：

1    4    9    18    
3    4    7    11    
8    6    12    18    
14    14    16    19    
19