汽车加油行驶问题PPT课件.ppt

汽车行驶加油问题： 3-16：给定一个N*N 的方形网格，设其左上角为起 点S，坐标为（1，1），X 轴向右为正，Y 轴向下为正，每个方格边长为1。一辆汽车从起点S出发驶向右下角终点T，其坐标为（N， N）。在若干个网格交叉点处，设置了油库，可供汽车在行驶途中加油。汽车在行驶过程中应遵守如下规则： （1）汽车只能沿网格边行驶，装满油后能行驶K 条网格边。出发时汽车已装满油，在起点与终点处不设油库。（2）当汽车行驶经过一条网格边时，若其X 坐标或Y 坐标减小，则应付费用B;否则免付费用。 （3）汽车在行驶过程中遇油库则应加满油并付加油费用A。（4）在需要时可在网格点处增设油库，并付增设油库费用C（不含加油费用A）。其中，(1)～(4) 中的各数N、K、A、B、C 均为正整数。 试设计一个算法，求出汽车从起点出发到达终点的一条所付费用最少的行驶路线。 分析与解答： 用f(x,y,0)表示汽车从网格点(1,1)行驶到网格点(x,y)所需的最少费用，f(x,y,1)表示汽车行驶至网格点(x,y)后还能行驶的网格边数。 建立计算f(x,y,o)和f(x,y,1)递归式如下： f(1,1,0)=0,f(1,1,1)=K f(x,y,0)=f(x,y,0)+A，f(x,y,1)=K,(x,y)是油库 f(x,y,0)=f(x,y,0)+C+A，f(x,y,1)=K,(x,y) 非油库且f(x,y,1)=0 f(x,y,0)=min{f(x+s[i][0],y+s[i][1],0)+s[i][2]} 0=i4 f(x,y,1)=f(x+s[j][0],y+s[j][1],1)-1 其中，数组s={{-1,0,0},{0,-1,0},{1,0,B},{0,1,B}}. using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace 汽车动态规划.Net3._5版 { public class Driving { private static int A = 2; private static int B = 3; private static int C = 6; private static int K = 3; private static int N = 9; private static int MAX = 100000000; private static int[,] S = { { -1, 0, 0 }, { 0, -1, 0 }, { 1, 0, B }, { 0, 1, B } }; static int len = K; /* * 私有变量 */ private int[,] f;//记录状态 private int[,] p;//油库点 /* * */ public Driving(int[,] p) { // TODO Auto-generated constructor stub this.p = p; f = new int[N + 1, N + 1]; for (int i = 0; i N + 1; i++) { for (int j = 0; j N + 1; j++) { f[i, j] = MAX; } } f[1, 1] = 0; } /* * 使用备忘录方法自顶向下解决问题 */ public int driving2(int x, int y) { if (x 1 || y 1 || x N || y N) { return MAX; } if