算法分析大作业.docx
《算法分析大作业.docx》由会员分享，可在线阅读，更多相关《算法分析大作业.docx（19页珍藏版）》请在冰点文库上搜索。
算法分析大作业
算法分析大作业
动态规划方法解
乘法表问题和汽车加油行驶问题
1.动态规划解乘法表问题
1.1问题描述------
1.2算法设计思想------
1.3设计方法------
1.4源代码------
1.5最终结果------
2.动态规划解汽车加油行驶问题
问题描述------
算法设计思想------
设计方法------
源代码------
最终结果------
3.总结
1.动态规划解决乘法表问题
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]
种。
原的解是：
ki到j
result[i][n][a]。
中的某一个字符，于
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];
输入：
输入一个以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][]可采取如下的计算次序
1.4源代码
#include"iostream"
#include"algorithm"
#include"fstream"
usingnamespacestd;
/*
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*/
intf[50][50][3];
charchars[3]={'a','b','c'};
intmul（intn,charch[]）
{
for（inti=0;i
for（intk=0;k<3;k++）
f[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（intr=1;r
for（i=0;i
{
intj=i+r;//区间右端点
for（intk=i;k
{
f[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];
}
}
returnf[0][n-1][0];
}
intmain（）
{
ifstreamfin（"mul.txt"）;
cout<<"输入字符串：
";
charch[100];
fin>>ch;cout<
intn=strlen（ch）;
cout<<"\n结果为a的加括号方式为：
"<
fin.close（）;
return0;
}
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算法设计思想
这个题目,应该说是刚开始的时候被他给吓到了，只是想着如何去把所有
的条件构造起来，然后使用网络流的方式来解决问题！
但是，如果真的是很
冷静下来好好地思考这道题目，就会发现如果没有那些限制条件，就是一个
求解最长路的题目，这样就可以直接使用ＳＰＦＡ来解决这个问题！
关键就
是在于这个每次最多只能走Ｋ个网格边，这样就是限制了活动的范围，使得
有的边无法扩展！
因此可以考虑使用这个分层思想的最短路问题！
就是通过
将每一个点进行拆分，这样，就是相当于一种分类讨论的方式！
而分类讨论
了之后，就知道哪些边是可以扩展的，哪些边是不能扩展的！
关键点就是在
于该如何选取变量来分层，这就是因情况而异了！
像这道题目之中，就是通
过油量的多少来扩展边的！
分层思想，说穿了其实就是相当于这个动态规划
之中的增加变量的方式来确定状态一样，他们的实质其实都是一样的！
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,
那么表示该问题已经求解过了,其相应的记录项中存储的就是该点的最小费
用值COST,此时要取出记录项C的值跟最新的计算出的COST进行比拟,取其
最小的那个数存入到C中.依此建立记录项C的值,当程序递归完成时,我们
也得到了汽车行驶到（n,n）的最小费用值COST.
2.4源代码
#include"iostream"
#include"algorithm"
#include"fstream"
usingnamespacestd;
#defineINF10000
/*
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
*/
intN;//
方形网络规模
intA;//
汽车在行驶过程中遇到油库应加满油并付加油费A
intC;//
在需要时可在网格点处增设油库，并付增设油库费用
C〔不含加
油费A〕
intB;//
当汽车行驶经过一条网格边时，如果其
x坐标或y坐标减少，应
付费用B
intK;//
装满油后，还能行驶K条边
intf[50][50][2];
ints[4][3]={{-1,0,0},{0,-1,0},{1,0,B},{0,1,B}};
inta[50][50];//方形网络
intdyna（）
{
inti,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;
intcount=1;
inttx,ty;
while（count）
{
count=0;
for（i=1;i<=N;i++）
{
for（intj=1;j<=N;j++）
{
if（i==1&&j==1）
continue;
intminStep=INF;
intminDstep;
intstep,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
&&dstep
==0&&（i!
=N||j!
=N））//
如果不是油库
且油已经用完
{
step+=A+C;
dstep=K;
}
if（step{
可以走
minStep=step;
minDstep=dstep;
}
}
if（f[i][j][0]>minStep）//
{
如果有更优解
count++;
f[i][j][0]=minStep;
f[i][j][1]=minDstep;
}
}
}
}
returnf[N][N][0];
}
intmain（）
{
ifstreamfin（"car.txt"）;
cout<<"输入方格规模：
";
fin>>N;cout<cout<<"\n输入装满油后能行驶的网格边数：
";fin>>K;cout<cout<<"\n输入加油费：
";
fin>>A;cout<cout<<"\n输入坐标减少时应付的费用：
";
fin>>B;cout<cout<<"\n输入增设油库费用：
";
fin>>C;cout<cout<<"\n输入方形网络：
\n";
for（inti=1;i<=N;i++）
{
for（intj=1;j<=N;j++）
{
fin>>a[i][j];
cout<}
cout<}
cout<<"最优行驶路线所需的费用为：
"<fin.close（）;
return0;
}
2.5最终结果
3.总结
动态规划〔DynamicProgramming，DP〕思想启发于分治算法的思想，也是将复杂问题化解假设干子问题，先求解小问题，再根据小问题的解得到原问题的解。
但是DP与分治算法不同的是，DP分解的假设干子问题，往往是互相不独立的，这时如果用分治算法求解，那么会对重叠子问题重复进行求解，从而使得浪费大量的时间。
那么如果我们保存已经计算过的子问题的解，这样当再次计算该子问题时，可以直接使用，这样可以节约大量的时间。
设计动态规划的四个步骤：
1、刻画一个最优解的结构特征。
2、递归地定义最优解的值。
3、计算最优解的
值，通常采用自底向上的方法。
4、利用计算出的信息构造一个最优解。
升级会员 