39-伪代码详解

5.6.4　伪代码详解

（1）数据结构

我们用一个结构体node来存储机器零件在第一台机器上的加工时间x和第二台机器上的加工时间y。定义一个这样的结构体数组T[]来存储所有的机器零件加工时间。

例如第3个机器零件在一台机器上的加工时间为5，在第二台机器上的加工时间为2，则T[3].x=5，T[3].y=2。

struct node
{
    int x,y;//机器零件在第一台机器上的加工时间x和第二台机器上的加工时间y
}T[MX];

（2）按限界条件搜索求解

t表示当前扩展结点在第t层。f₁表示当前第一台机器上加工的完成时间，f₂表示当前第二台机器上加工的完成时间。

如果t>n，表示已经到达叶子结点，记录最优值和最优解，返回。否则，分别判断每个分支是否满足约束条件，如果满足则进入下一层Backtrack(t+1)；如果不满足则反操作复位，考查下一个分支（兄弟结点）。

void Backtrack(int t)
{
     if(t>n)
     {
          for(int i=1;i<=n;i++)    //记录最优排列
              bestx[i]=x[i] ;
          bestf=f2;                //更新最优值
          return ;
     }
     for(int i=t;i<=n;i++)         //枚举
     {
          f1+=T[x[i]].x;
          int temp=f2;
          f2=max(f1,f2)+T[x[i]].y;
          if(f2<bestf)             //限界条件
          {
               swap(x[t] ,x[i]);   //交换
               Backtrack(t+1);     //继续深搜
               swap(x[t],x[i]);    //复位，反操作
          }
          f1-=T[x[i]].x ;          //复位，反操作
          f2=temp ;                //复位，反操作
     }
}