算法分析大作业

动态规划方法解

乘法表问题和汽车加油行驶问题

目录

1.动态规划解乘法表问题 1.1问题描述------ 1.2算法设计思想------ 1.3设计方法------ 1.4源代码------ 1.5最终结果------ 2.动态规划解汽车加油行驶问题 2.1问题描述------ 2.2算法设计思想------ 2.3设计方法------ 2.4源代码------ 2.5最终结果------ 3.总结

1.动态规划解决乘法表问题

1 / 14文档可自由编辑

1.1问题描述

定义于字母表∑{a,b,c)上的乘法表如表所示：

依此乘法表,对任一定义于∑上的字符串,适当加括号表达式后得到一个表达式。

例如,对于字符串x=bbbba,它的一个加括号表达式为(b(bb))(ba)。依乘法表,该表达式的值为a。

试设计一个动态规划算法,对任一定义于∑上的字符串x=x1x2…xn，计算有多少种不同的加括号方式,使由x导出的加括号表达式的值为a。 1.2算法设计思想

设常量a,b,c 分别为 1, 2 ,3 。n 为字符串的长度。 设字符串的第 i 到 第 j 位乘积为 a 的加括号法有result[i][j][a] 种，

字符串的第 i 到 第 j 位乘积为 b 的加括号法有result[i][j][b] 种,

字符串的第 i 到 第 j 位乘积为 c 的加括号法有 result[i][j][c] 种。

则原问题的解是： result[i][n][a] 。

设 k 为 i 到 j 中的某一个字符，则对于 k 从 i 到 j ： result[i][j][a] += result[i][k][a] * result[k + 1][j][c] + result[i][k][b] * result[k + 1][j][c] + result[i][k][c] * result[k + 1][j][a];

result[i][j][b] += result[i][k][a] * result[k + 1][j][a] + result[i][k][a] * result[k + 1][j][b] + result[i][k][b] * result[k + 1][j][b];

result[i][j][c] += result[i][k][b] * result[k + 1][j][a] + result[i][k][c] * result[k + 1][j][b] + result[i][k][c] * result[k + 1][j][c];

2 / 14文档可自由编辑

输入：输入一个以a,b,c组成的任意一个字符串。 输出：计算出的加括号方式数。 1.3设计方法

乘法表问题直观理解就是通过加括号使得最终运算结果为a，该问题与矩阵连乘问题类似，矩阵连乘是每一次加括号选择运算量最小的，写成数学表达式有：

而乘法表问题则是计算所有加括号运算结果为a的情况数，并不要求输出加括号方式。那么可以从乘法的最小单元两个符号相乘的所有可能开始，接着在两个符号相乘的基础上计算三个符号相乘的所有可能。直到计算N长度的符号1-N的所有可能。可以定义一个三维数组a[n][n][3],n为输入字符串的长度，a[i][j][0]为从字符串中第i个元素到第j个元素的子串表达式值为a的加括号方式数，a[i][j][1]为从字符串中第i个元素到第j个元素的子串表达式值为b的加括号方式数，a[i][j][2]为从字符串中第i个元素到第j个元素的子串表达式值为c的加括号方式数。

由乘法表的定义则可知啊a[i][j][0]=（对k求和，k从i到j-1）a[i][k][0]*a[i][k+1][2]+a[i][k][1]*a[i][k+1][2]+a[i][k][2]*a[i][k+1][1];

同理可得到a[i][j][1]和a[i][j][2]。

同时由上面的表达式可知，要计算a[i][j][],需先计算a[i][k][]和a[i][k+1][]，这里k从i到j-1，故a[i][j][]可采取如下的计算次序

3 / 14文档可自由编辑

1.4源代码

#include \"iostream\" #include \"algorithm\" #include \"fstream\" using namespace std;

/*

f[i][j][0] 表示在ch[i]~ch[j]之间以某种方式加括号后，结果为a

f[i][j][1] 表示在ch[i]~ch[j]之间以某种方式加括号后，结果为b

f[i][j][2] 表示在ch[i]~ch[j]之间以某种方式加括号后，结果为c

a = a*c || b*c || c*a b = a*a || a*b || b*b c = b*a || c*b || c*c */ int f[50][50][3];

char chars[3] = {'a', 'b', 'c'};

int mul(int n, char ch[]) {

4 / 14文档可自由编辑

for(int i=0; if[i][i][k] = (ch[i] == chars[k] ? 1: 0); /*

a = a*c || b*c || c*a b = a*a || a*b || b*b c = b*a || c*b || c*c */

for(int r=1; rfor(i=0; iint j = i + r; //区间右端点 for(int k=i; kf[i][j][0] += f[i][k][0]*f[k+1][j][2] f[i][k][1]*f[k+1][j][2] + f[i][k][2]*f[k+1][j][0]; f[i][j][1] += f[i][k][0]*f[k+1][j][0] f[i][k][0]*f[k+1][j][1] + f[i][k][1]*f[k+1][j][1]; f[i][j][2] += f[i][k][1]*f[k+1][j][0] f[i][k][2]*f[k+1][j][1] + f[i][k][2]*f[k+1][j][2]; } }

5 / 14文档可自由编辑

+ + + return f[0][n-1][0]; }

int main() {

ifstream fin(\"mul.txt\"); cout << \"输入字符串：\"; char ch[100];

fin >> ch; cout << ch; int n = strlen(ch);

cout << \"\\n结果为a的加括号方式为：endl;

fin.close(); return 0; }

最终结果

6 / 14文档可自由编辑

\" << mul(n, ch) << 1.5

2.动态规划解决汽车加油行驶问题 2.1问题描述

给定一个N*N的方形网络，设其左上角为起点○，坐标为(1，1)，X轴向右为正，Y轴向下为正，每个方格边长为1。一辆汽车从起点○出发驶向右下角终点， 其坐标为（M，N）。在若干网格交叉点处，设置了油库，可供汽车在行驶途中，可供汽车在行驶途中加油。汽车在行驶过程中应遵守如下规则：

（1）汽车只能沿网格边行驶，装满油后能行驶K条网格边。出发时汽车已装满油，在起点与终点处不设油库。

（2）当汽车行驶经过一条网格边时，若其X坐标或Y坐标减小，则应付费用B，否则免付费用。

（3）汽车在行驶过程中遇油库则应加满油并付加油费用A。 （4）在需要时可在网格点处增设油库，并付增设油库费用C（不含加油费A）。 （5）（1）~（4）中的各数N，K，A，B，C均为正整数。

2.2算法设计思想

这个题目,应该说是刚开始的时候被他给吓到了，只是想着如

7 / 14文档可自由编辑

何去把所有的条件构造起来，然后使用网络流的方式来解决问题！但是，如果真的是很冷静下来好好地思考这道题目，就会发现如果没有那些限制条件，就是一个求解最长路的题目，这样就可以直接使用ＳＰＦＡ来解决这个问题！关键就是在于这个每次最多只能走Ｋ个网格边，这样就是限制了活动的范围，使得有的边无法扩展！因此可以考虑使用这个分层思想的最短路问题！就是通过将每一个点进行拆分，这样，就是相当于一种分类讨论的方式！而分类讨论了之后，就知道哪些边是可以扩展的，哪些边是不能扩展的！关键点就是在于该如何选取变量来分层，这就是因情况而异了！像这道题目之中，就是通过油量的多少来扩展边的！分层思想，说穿了其实就是相当于这个动态规划之中的增加变量的方式来确定状态一样，他们的实质其实都是一样的！ 2.3设计方法

采用的是动态规划的思想来解题,用备忘录的方法进行递归,递归的式子后面写出.

不能直接以汽车行驶的费用为目标来进行动态规划,因为最优子结构性质得不到证明.

所以必须把油量和费用一起考虑,作为动态规划的对象,此时就有了最优子结构性质. 最优子结构性质的证明

证明:假设路径M是从起点◎到终点▲的一条最小费用路径,P(x,y)是M经过的一个点(非加油站),且油量和费用为(g,c),现假设有一条新路径Q从起点◎到点P(x,y),使得其在P(x,y)点的油量和费用为(g,c'),其中c'备忘录递归

刚开始的时候为每个网格点P(x,y)建立一个记录,初始化时,为该记录存入一个特殊值W,表示汽车未行驶过.那么在汽车行驶过程中,对每个待求的汽车最小费用值COST,先查看其相应的记录项C,如果存储的是初始值W,那么表示这个点P(x,y)是第一次遇到,此时计算出该点的最小费用值,并保存在其相应的记录项中,以备以后查看.若记录项C中存储的不是初始值W,那么表示该问

8 / 14文档可自由编辑

题已经求解过了,其相应的记录项中存储的就是该点的最小费用值COST,此时要取出记录项C的值跟最新的计算出的COST进行比较,取其最小的那个数存入到C中.依此建立记录项C的值,当程序递归完成时,我们也得到了汽车行驶到(n,n)的最小费用值COST.

2.4源代码

#include \"iostream\" #include \"algorithm\" #include \"fstream\" using namespace std; #define INF 10000 /*

f[i][j][0]表示汽车从网格点(1,1)行驶至网格点(i,j)所需的最少费用

f[i][j][1]表示汽车行驶至网格点(i,j)还能行驶的网格边数

s[i][0]表示x轴方向 s[i][1]表示y轴方向 s[i][2]表示行驶费用

f[i][j][0] = min{f[ i+s[k][0] ][ [j+s[k][1] ][0] + s[k][2]} f[i][j][1] = f[ i+s[k][0] ][ [j+s[k][1] ][1] - 1;

f[1][1][0] = 0 f[1][1][1] = K

f[i][j][0] = f[i][j][0] + A , f[i][j][1] = K 如果(i, j)是油库

f[i][j][0] = f[i][j][0] + C + A, f[i][j][1] = K (i, j)不是油库，且f[i][j][1] = 0 */

int N; //方形网络规模

int A; //汽车在行驶过程中遇到油库应加满油并付加油费A

9 / 14文档可自由编辑

int C; //在需要时可在网格点处增设油库，并付增设油库费用C（不含加油费A）

int B; //当汽车行驶经过一条网格边时，如果其x坐标或y坐标减少，应付费用B

int K; //装满油后，还能行驶K条边

int f[50][50][2];

int s[4][3] = {{-1,0,0},{0,-1,0},{1,0,B},{0,1,B}};

int a[50][50]; //方形网络

int dyna() {

int i, j, k;

for (i=1;i<=N;i++) {

for (j=1;j<=N;j++) {

f[i][j][0]=INF; f[i][j][1]=K; } }

f[1][1][0] = 0; f[1][1][1] = K;

int count = 1; int tx, ty; while(count) {

count = 0;

for(i=1; i<=N; i++) {

for(int j=1; j<=N; j++)

10 / 14文档可自由编辑

{

if(i==1 && j==1) continue;

int minStep = INF; int minDstep; int step, dstep;

for(k=0; k<4; k++) //可走的四个方向 { tx = i + s[k][0]; ty = j + s[k][1]; if(tx<1 || ty<1 || tx>N || ty>N) //如果出界

continue;

step = f[tx][ty][0] + s[k][2]; dstep = f[tx][ty][1] - 1; if(a[i][j] == 1) // { step += A; dstep = K; } if(a[i][j]==0 (i!=N||j!=N)) // { step += A + C; dstep = K; } if(step < minStep) // { minStep = step; minDstep = dstep; } }

如果是油库

&& dstep == 0 如果不是油库,且油已经用完

可以走

11 / 14文档可自由编辑

&& if(f[i][j][0] > minStep) //如果有更优解 {

count++;

f[i][j][0] = minStep; f[i][j][1] = minDstep; } } } }

return f[N][N][0]; }

int main() {

ifstream fin(\"car.txt\"); cout << \"输入方格规模：\"; fin >> N; cout << N;

cout << \"\\n输入装满油后能行驶的网格边数：\"; fin >> K; cout << K;

cout << \"\\n输入加油费：\"; fin >> A; cout << A;

cout << \"\\n输入坐标减少时应付的费用：\";

fin >> B; cout << B; s[2][2] = s[3][2] = B; cout << \"\\n输入增设油库费用：\"; fin >> C; cout << C;

cout << \"\\n输入方形网络：\\n\"; for(int i=1; i<=N; i++) {

for(int j=1; j<=N; j++) {

fin >> a[i][j];

cout << a[i][j] << \" \"; }

cout << endl;

12 / 14文档可自由编辑

}

cout << \"最优行驶路线所需的费用为：\" << dyna() << endl; fin.close(); return 0; }

2.5最终结果

3.总结

动态规划（Dynamic Programming， DP）思想启发于分治算法的思想，也是将复杂问题化解若干子问题，先求解小问题，再根据小问题的解得到原问题的解。但是DP与分治算法不同的是，DP分解的若干子问题，往往是互相不独立的，这时如果用分治算法求解，那么会对重叠子问题重复进行求解，从而使得浪费大量的时间。那么如果我们保存已经计算过的子问题的解，这样当再次计算该子问题时，可以直接使用，这样可以节约大量的时间。 设计动态规划的四个步骤： 1、刻画一个最优解的结构特征。 2、递归地定义最优解的值。

3、计算最优解的值，通常采用自底向上的方法。

13 / 14文档可自由编辑

4、利用计算出的信息构造一个最优解。

14 / 14文档可自由编辑