当先锋百科网

首页 1 2 3 4 5 6 7

一、运行环境:

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,1

2   f2[1] ße2 + a2,1

3   for jß2 to n

4             do if f1[j-1] + a1,j <= f2[j-1] + t2,j-1 + a1,j

5                      then f1[j] ß f1[j-1] + a1,j

6                               l1[j] ß 1

7                      else f1[j] ß f2[j-1] + t2,j-1 + a1,j

8                               l1[j] ß 2

9             do if f2[j-1] + a2,j <= f1[j-1] + t1,j-1 + a2,j

10                    then f2[j] ß f2[j-1] + a2,j

11                             l2[j] ß 2

12                    else f1[j] ß f1[j-1] + t1,j-1 + a2,j

13                             l2[j] ß 1

14 if f1[n] + x1 <= f2[n] + x2

15           then f* ßf1[n] + x1

16                    l* ß1

17           else f* ß f2[n] + x2

                l* ß 2

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

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

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

PRINT_STATIONS ( l , l* , n ) :

iß l*

print “line” i “, station” n

for 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)。