算法第二次作业-装配线分配问题

一、运行环境：

Win7、Dev-C++

二、运行过程说明:

数据文件格式：

• 第一行是线路1上的各个装配站装配的时间；
• 第二行是线路2上的各个装配站装配的时间；
• 第三行是线路1上的装配站到线路2的（下一个）装配站的运输时间；
• 第四行是线路2上的装配站到线路1的（下一个）装配站的运输时间 ；
• 第五行是底盘分别到线路1和线路2的第一个装配站所需要的时间；
• 第六行是线路1和线路2的最后一个装配站分别到达终点的市时间。

输入格式：输入测试数据集文件编号。

输出：

三、算法设计

3.1问题描述：

装配一辆汽车，有两条装配线分别有n个装配点，每条装配线在进出所花时间为e[i]，x[i] (i=0,1),每个装配点所需时间a[i][j](i=0,1;j=0,1,...,n-1),从一条装配线i的第j个装配点到另一条装配线的第j+1个装配点所需时间t[i][j]。

3.2解题思路：

DP算法的设计可以分为四个步骤：描述最优解的结构；递归定义最优解的值；按自底而上的方式计算最优解的值；由计算出的结果创造一个最优解。

用上面的四步来解题：

• 描述最优解的结构，即通过工厂最快路线的结构。
• 递归定义最优解的值，计算最快时间。
• 按自底而上的方式计算最优解的值，即计算最快时间。
• 由计算出的结果创造一个最优解，构造通过工厂的最快路线。

3.3数据结构的选择：

• 假设两条装配线都有n个装配站；
• 最短时间int型f_star；
• 最后出口的线路选择l_star（因为求出口时，要有个统一的入口，根据f1[n]+x1和f2[n]+x2的大小决定L*为1还是为2）；
• 每个装配站的最短时间使用整型二维数组f[2][n]；
• 到达i线上的j站点来自于哪个线上的j-1，使用整型二维数组l[2][n]（l[i][j]，其中i=1或2，j表示第j个装配站)；
• 每个装配站的装配时间使用整型二维数组a[2][n]；
• 每个装配站的运输时间使用整型二维数组t[2][n]；
• 底盘分别到达装配线1和装配线2的运输时间使用一维整形数组int e[2]；
• 装配线1和装配线2的最后一个装配站分别到达目的地的运时用一维整形数组int x[2]；

四、算法详细描述：

4.1步骤以及伪代码：

(1)描述最优解的结构，即通过工厂最快路线的结构。

最后的出口(1,n)从第（1，n-1）位置或（2，n-1）来，出口（2，n）类似。这样一次划分后，具有最优子结构：一个问题的最优解包含了子问题的一个最优解。题中找出通过装配站S(i,j)的最优解，包含了找出通过S(1,j-1)或S(2,j-1)的一个最优解，通过S(1,j)的最快路线只能是以下两种选择：

通过配件站S(1,j-1)，然后直接到达S(1,j)；

通过配件站S(2,j-1)，然后从装配线2到装配线1，最后到达S(1,j)。

问题转化为了，为解决该问题（寻找通过任一条装配线上的j的最快路线），解决其子问题（寻找通过两条装配线上的j-1的最快路线）来构造问题最优解。

(2)递归定义最优解的值，计算最快时间。

第一步分析了最优解是如何拆分的，第二步就是用来组成最优解。根据题意，写出f(i)与f(i-1)之间的关系。

先不考虑边界情况，得到如下递归式：

然后处理边界性问题（入口和出口）：

出口时，应该求解f1[n]+x1,f2[n]+x2。然后选出其中的最小值求解。

入口条件如下：

因此得到两个方程组和一个结果方程

(3)按自底而上的方式计算最优解的值，即计算最快时间。

动态规划问题，采用自底向上的方式，需要建立数组来保持，防止递归带来的时间消耗，因此数组保存的是要递归时的返回值。也就是递归表达式中的f1[n-1]以及f2[n-2]。将i从1àn增长，一步一步求解。

计算最快时间的伪代码如下：

FAST_WAY ( a, t, e, x, n)1   f1[1] ße1 + a1,12   f2[1] ße2 + a2,13   for jß2 to n4             do if f1[j-1] + a1,j <= f2[j-1] + t2,j-1 + a1,j5                      then f1[j] ß f1[j-1] + a1,j6                               l1[j] ß 17                      else f1[j] ß f2[j-1] + t2,j-1 + a1,j8                               l1[j] ß 29             do if f2[j-1] + a2,j <= f1[j-1] + t1,j-1 + a2,j10                    then f2[j] ß f2[j-1] + a2,j11                             l2[j] ß 212                    else f1[j] ß f1[j-1] + t1,j-1 + a2,j13                             l2[j] ß 114 if f1[n] + x1 <= f2[n] + x215           then f* ßf1[n] + x116                    l* ß117           else f* ß f2[n] + x2l* ß 2

(4)由计算出的结果创造一个最优解，构造通过工厂的最快路线。

如果只需要最优解的话，不需要这一步。但如果需要给出方案，就需要数组保存路径信息。

构造通过工厂的最快路线的伪代码如下：

PRINT_STATIONS ( l , l* , n ) :iß l*print “line” i “, station” nfor j ß li[j]do I <- li[j]print “line” i “,station” j-1

4.2代码：

#include <stdio.h>int f[2][6]={0};    //对应通过各个装配站的最短时间int l[2][6]={0};    //对应通过各个装配站的来源int l_star;//记录选择的线路int f_star;//记录到达最短时间，/***         Dp求解 最短时间**         二维数组a 存储没个装配站装配时间*         二维数组t 存储装配站间的运输时间*         一维数组a 存储底盘运输到线路1的时间  和  运输到线路2的时间*         一维数组x 存储线路1最后一站运输到目的地的时间是   和   线路2最后一站运输到目的地的时间是2；*         n 每个线路拥有的装配站数量**  ！！！：计算时间的同时要保持线路的纪录**/void Fastest_Way(int a[][6],int t[][5],int e[],int x[],int n){int j=0;f[0][0] = e[0]+ a[0][0];f[1][0] = e[1]+ a[1][0];for (j=1;j<n;j++)                          //自底向上开始计算f[i][j]的值，与l[i][j]的值{//对于在线路1的装配站来说if (f[0][j-1]+a[0][j] <= f[1][j-1]+t[1][j-1]+a[0][j])//选择第一条线 过来的{f[0][j] = f[0][j-1]+a[0][j];           l[0][j] = 0;}else//选择从第二条线过来的{f[0][j] = f[1][j-1]+t[1][j-1]+a[0][j];l[0][j] = 1;}//对于在线路2的装配站来说if (f[1][j-1]+a[1][j] <= f[0][j-1]+t[0][j-1]+a[1][j])//选择从第二条线过来的{f[1][j] = f[1][j-1]+a[1][j];l[1][j] = 1;}else//选择从第一条线过来得{f[1][j] = f[0][j-1]+t[0][j-1]+a[1][j];l[1][j] = 0;}  }if (f[0][5] + x[0] <= f[1][5] + x[1]){f_star = f[0][5]+x[0];              //  f_star为通过装配线的最短时间  l_star为产品最后出自哪个生产线l_star = 0;}else{f_star = f[1][5]+x[1];l_star = 1;}printf("运输最短时间为：%d\n",f_star);}/***         根据记录得出最佳的路径 (根据站点顺序递归输出)*   *        二维数组l 记录了选择的线路l_star 和站点 n**/void Print_Station(int l[][6],int l_star,int n){  if ( n==0 )//边界条件return;l_star = l[l_star][n];/*递归*/Print_Station(l,l_star,n-1);printf("线路  %d ,  站点  %d\n",l[l_star][n]+1,n);}int main(){FILE *fp;/*用户输入文件序号*/int index;printf("请输入文件序号(1-6)！");scanf("%d",&index);if(index>=1&&index<=6){char fname[100];//sprintf(fname,"%s%d%s","input_assgin02_0",index,".dat");puts(fname);/*读取数据文件 FILE * fopen(char *filename, char *mode);*/if ((fp=fopen(fname,"r"))==NULL){printf("文件读取失败！");return -1;}}int a[2][6];           //装配时间int t[2][5];           //运输时间int e[2];                         //底盘运输到线路1、线路2的时间int x[2];                        //线路1、线路2最后一站运输到目的地的时间int i=0,j=0;/*对每个站点的装配时间赋值 */printf("每个站点的装配时间\n");for(i=0;i<2;i++){for(j=0;j<6;j++){fscanf(fp,"%d",&a[i][j]);printf("%d\t", a[i][j]);}putchar('\n');//每行结束换行}/*对站点两两之间的运输时间赋值*/printf("站点两两之间的运输时间\n");for(i=0;i<2;i++){for(j=0;j<5;j++){fscanf(fp,"%d",&t[i][j]);printf("%d\t", t[i][j]);}putchar('\n');//每行结束换行}/*底盘运输到线路1、线路2的时间*/printf("底盘运输到线路1和线路2的运输时间\n");for(i=0;i<2;i++){fscanf(fp,"%d",&e[i]);printf("%d\t", e[i]);}putchar('\n');/*终线路1、线路2最后一站运输到目的地的时间*/printf("线路1和线路2的最后一个装配站到目的地的运输时间\n");for(i=0;i<2;i++){fscanf(fp,"%d",&x[i]);printf("%d\t", x[i]);}putchar('\n');/*求解最短时间*/Fastest_Way(a,t,e,x,6);/*求解最佳线路*/printf("运输最佳线路为：\n");Print_Station(l,l_star,6);return 0;}

五、算法分析

动态规划由于从第二步开始每一步都利用上一步的结果来计算，从而避免了许多重复的计算，大大降低了时间复杂度。根据上面的工作方式，可以计算出时间复杂度为：O(n)。

空间复杂度：因为使用了二维数组、一维数组以及整型变量来保持记录，空间复杂度为：O(n)。