汽车加油行驶问题全网最详细（动态规划+画图）

本文主要是介绍汽车加油行驶问题全网最详细（动态规划+画图），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述

给定一个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，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
from numpy.core.fromnumeric import reshape
import matplotlib.pyplot as pltrandom.seed(10)
INF = 10000#输入参数
def find_path_and_fee(N = 9, K = 3, A = 2, B = 2, C = 1):    seed = lambda : 1 if random.randint(0, 11) % 4 == 0 else 0grid = 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] = seed()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] = INFf[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, Ktempx, tempy = 0, 0path = 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: continueminmoney, minstep, tmpmoney, tmpstep = INF, 0, 0, 0for 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: continuetmpmoney = f[x+s[i][0]][y+s[i][1]][0] + s[i][2]tmpstep = f[x+s[i][0]][y+s[i][1]][1] - 1if grid[x][y] == 1: tmpmoney += Atmpstep = Kif grid[x][y] == 0 and tmpstep == 0 and (x != N or y != N):tmpmoney += A + Ctmpstep = Kif minmoney > tmpmoney:minmoney = tmpmoneyminstep = tmpsteptempx = x + s[i][0]tempy = y + s[i][1]if(f[x][y][0] > minmoney):f[x][y][0] = minmoneyf[x][y][1] = minsteppath[x][y][0] = tempxpath[x][y][1] = tempy#回溯找到最佳路径re_path_x, re_path_y = [], []x, y, tmp = N, N, 0while ((x != 1) or (y != 1)):re_path_x.append(x)re_path_y.append(y)tmp = xx = 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):plt.grid(linestyle=":", color="r")ax = plt.gca()                       #获取到当前坐标轴信息ax.xaxis.set_ticks_position('top')   #将X坐标轴移到上面ax.invert_yaxis()                    #反转Y坐标轴plt.xticks([x for x in range(1, N+1)])plt.xlabel("x axis")plt.yticks([x for x in range(1, N+1)])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)

运行代码

绘制出最佳路径（蓝色虚线为最佳路径，红色点为加油站）