汽车加油⾏驶问题全⽹最详细（动态规划+画图）
问题描述
给定⼀个N*N的⽹络，左上⾓记为起点S，坐标为（1，1），坐标轴⽅向及距离标识见图。⼀辆汽车从起点S出发驶向右下⾓终点
（N，N）。在部分⽹格交叉点，设置了油库，可供汽车在⾏驶途中，为其加油。汽车在⾏驶途中需遵守如下规则：
1.汽车只能沿着⽹格边⾏驶，装满油后只能⾏驶K条⽹格边。出发时已装满油，起点和终点不设油库
2.当汽车⾏驶经过⼀条⽹格边时，若其X坐标或Y坐标减⼩，则需付费B，否则免付费⽤
3.汽车⾏驶过程中若遇到油库，则需加满油并付油费A
4.在需要时可在⽹格点增设油库，并付增设油库费⽤C（不含A）
5.以上N=9,K《3,A,B,C均为正整数，可⾃⾏设置数值（值不能相同）
图1-1
求⾏驶到坐标（9，9）的费⽤最⼩
本题暂且输⼊参数 N = 9，K = 3，A = 2，B = 2，C = 1
动态规划原理：
最优性原理：多阶段决策过程的最优决策序列具有如下性质：⽆论决策过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产⽣的当前状态，构成⼀个最优决策序列。
图1-2
解题步骤：
1. 找递推表达式
2. 填写递推表格
分析：
已知起点（1，1），终点（9，9），设（x，y）为当前汽车所到达的点，f是形为（9+1，9+1，2）的三维表（注释：9+1的原因是数组下标以0为起点，本题起点为（1，1）点，为了⽅便分析，引⼊占位
符，数组下标从1开始计数，本⽂所有数组都以1为起点，后⾯不重复申明），path变量为（9+1，9+1，2）的三维表，⽤于保存⾏驶进⼊当前节点的前向节点表，⽤于路径回溯。
f[x][y][0]表⽰坐标（1，1）到坐标（x，y）汽车所花的最少费⽤
f[x][y][1]表⽰汽车⾏驶到坐标（x，y）后还能⾏驶的⽹格边数
最终总费⽤：即求f[N][N][0]
并最后通过path表回溯路径—》找到最短路径
图 1-3
由图1-3可知汽车运动到蓝⾊的点，有四种运动⽅式，分别是从上到下，从左到右，从右到左，从下到上，需要找出的是，所花费⽤最少的点作为当前蓝⾊点的前向节点。设蓝⾊节点费⽤为g，则可得递推表达式
蓝⾊站点费⽤ g = 加油费⽤ 或 （建⽴油站 加上 加油费⽤）
最⼩费⽤ f[x][y][0] = min(f[x-1][y][0]+g, f[x+1][y][0]+g, f[x][y-1][0]+g, f[x][y+1][0])
使⽤固定随机种⼦初始地图1-4（红⾊点表⽰加油站）
图1-4
⽤递推表达式填表并找规律（熟⼿可跳过此流程）
图1-5
import numpy as np
import random
fromnumeric import reshape
import matplotlib.pyplot as plt
random.ed(10)
INF = 10000
#输⼊参数
def find_path_and_fee(N = 9, K = 3, A = 2, B = 2, C = 1):
ed = lambda : 1 if random.randint(0, 11) % 4 == 0 el 0
grid = np.zeros((N + 1, N + 1), dtype = int)
oil_x, oil_y = [], []
for i in range(N):
for j in range(N):
grid[i+1][j+1] = ed()
if grid[i+1][j+1] == 1:
oil_x.append(i+1)
oil_y.append(j+1)
f = np.zeros((N + 1, N + 1, 2), dtype = int)
for i in range(1, N+1):
for j in range(1, N+1):
f[i][j][0] = INF
f[i][j][1] = K
#4个⽅向
s = [[-1, 0, 0], [0, -1, 0], [1, 0, B], [0, 1, B]]
f[1][1][0], f[1][1][1] = 0, K
tempx, tempy = 0, 0
path = np.zeros((N + 1, N + 1, 2), dtype= int)
for x in range(1, N + 1):
for y in range(1, N + 1):
if x == 1 and y == 1: continue
minmoney, minstep, tmpmoney, tmpstep = INF, 0, 0, 0
for i in range(4):
if x + s[i][0] < 1 or x + s[i][0] > N or y + s[i][1] < 1 or y + s[i][1] > N: continue
tmpmoney = f[x+s[i][0]][y+s[i][1]][0] + s[i][2]
tmpstep = f[x+s[i][0]][y+s[i][1]][1] - 1
if grid[x][y] == 1:
tmpmoney += A
tmpstep = K
if grid[x][y] == 0 and tmpstep == 0 and (x != N or y != N):
tmpmoney += A + C
tmpstep = K
if minmoney > tmpmoney:
minmoney = tmpmoney
minstep = tmpstep
tempx = x + s[i][0]
tempy = y + s[i][1]
if(f[x][y][0] > minmoney):
f[x][y][0] = minmoney
f[x][y][1] = minstep
path[x][y][0] = tempx
path[x][y][1] = tempy
#回溯找到最佳路径
re_path_x, re_path_y = [], []
x, y, tmp = N, N, 0
while ((x != 1) or (y != 1)):
re_path_x.append(x)
re_path_y.append(y)
tmp = x
x = path[x][y][0]
y = path[tmp][y][1]
re_path_x.append(x)
re_path_y.append(y)
return N, oil_x, oil_y, re_path_x, re_path_y
#绘制最佳路径图
def draw_pic(N, oil_x, oil_y, re_path_x, re_path_y):
ax = a() #获取到当前坐标轴信息
ax.xaxis.t_ticks_position('top') #将X坐标轴移到上⾯
ax.invert_yaxis() #反转Y坐标轴
plt.xlabel("x axis")
plt.ylabel("y axis")
plt.scatter(oil_x, oil_y, color="r", label="oil station")
plt.plot(re_path_x, re_path_y, ls="-.", lw=2, c="b", label="plot figure") plt.legend(loc="lower left")
plt.show()
N, oil_x, oil_y, re_path_x, re_path_y = find_path_and_fee()
draw_pic(N, oil_x, oil_y, re_path_x, re_path_y)
运⾏代码
绘制出最佳路径（蓝⾊虚线为最佳路径，红⾊点为加油站）
