【回溯法】机器零件加工-最优加工顺序

题目

有n个机器零件{J1,J2,…,Jn},每个零件必须先由机器1处理，再由机器2处理。零件Ji需要机器1，机器2的处理时间为t(1i),t(2i)。如何安排零件加工顺序，使第一个零件从机器1上加工开始到最后一个零件在机器2上加工完成，所需的总加工时间最短？

问题分析

要想计算出最短的加工时间，首先要知道一般情况下的加工时间是如何计算的。机器1是连续工作的，就是加工完了这一个，可以继续加工下一个，中间没有等待时间。但是机器2就不一样了，它会既会受到自己上一个加工零件的制约，也会受到机器1的制约。可能它加工完第i个零件，但是机器1还没有加工完第i+1个零件，这时就需要等待。还有一种情况就是机器1加工完第i+1个零件，机器2还没有加工完第i个零件，这时机器1可以继续加工，但是机器2要等到加工完第i个零件才可以加工第i+1个零件。所以我们可以得出机器2开始加工第i+1个零件的时间就是机器1加工完第i+1个零件的时间和机器2加工完第i个零件的时间的最小值，那么结束时间就是机器2开始加工最后一个零件的时间再加上这个零件需要机器2加工的时间。然后我们就可以用回溯法来求解最短时间了。

算法

排列树

这个问题的解空间是排列树，这并不是真正的数据结构，而只是假想的树。就是利用从右边开始按照一定顺序进行数据交换的方式得到全排列的解空间树。

#include<iostream>
#include<cstring>
using namespace std;
const int maxn=105;

int x[maxn];
int n;

void BackTrack(int t)
{
    if(t>n)
    {
        for(int i=1; i<=n; ++i)
            cout<<x[i]<<" ";
        cout<<endl;
    }
    else
    {
        for(int i=t; i<=n; ++i)
        {
            swap(x[t],x[i]);
            BackTrack(t+1);
            swap(x[t],x[i]);
        }
    }
}

int main()
{
    cout<<"请输入要求的全排列：";
    cin>>n;
    memset(x,0,sizeof(x));
    for(int i=1; i<=n; ++i)
        x[i]=i;
    BackTrack(1);
    return 0;
}
           

算法核心

本题中解空间中的每一个解都是可行解，所以没有约束条件。但是还是要考虑限界条件和回溯的问题。

限界条件就是当前结点加入之后的结束时间要早于之前计算的最早结束时间，如果只是截止到这个结点的时间就比最早时间晚的话，那么后面的结点不管怎么安排都会比最早时间晚，所以这个分支可以直接剪掉。

回溯呢，对于机器1的结束时间还是怎么加上的怎么减掉，机器2的结束时间要在计算之前先记录一下，然后扩展完之后再赋原来的值就可以了。

代码实现

#include<iostream>
#include<cstring>
#define INF 1<<29
using namespace std;
const int maxn=105;

struct item
{
    int a;
    int b;
};

int x[maxn];//当前解
int t1,t2;//当前机器1，机器2的结束时间
int bestx[maxn],besttime;//最优解，最优结束时间
struct item I[maxn];//存储每个零件的操作时间
int n;//零件数

void init()
{
    memset(x,0,sizeof(x));
    memset(bestx,0,sizeof(bestx));
    t1=0;
    t2=0;
    besttime=INF;
    for(int i=1; i<=n; ++i)
        x[i]=i;
}

void BackTrack(int t)
{
    if(t>n)//到达叶子结点就记录解并返回
    {
        for(int i=1; i<=n; ++i)
            bestx[i]=x[i];
        besttime=t2;
        return ;
    }
    else
    {
        for(int i=t; i<=n; ++i)//排列树
        {
            t1+=I[x[i]].a;//注意这里是x[i]
            int temp=t2;
            t2=max(t1,t2)+I[x[i]].b;//计算加上这个结点的结束时间
            if(t2<besttime)//满足限界条件
            {
                swap(x[t],x[i]);
                BackTrack(t+1);
                swap(x[t],x[i]);
            }
            t1-=I[x[i]].a;//回溯到之前的结果
            t2=temp;
        }
    }
}

void output()
{
    cout<<"加工零件的最短时间为："<<besttime<<endl;
    cout<<"最优的零件加工顺序为：";
    for(int i=1; i<=n; ++i)
        cout<<bestx[i]<<" ";
    cout<<endl;
}

int main()
{
    cout<<"请输入零件数目：";
    cin>>n;
    cout<<"请输入每个零件在两个机器上的加工时间：";
    for(int i=1; i<=n; ++i)
        cin>>I[i].a>>I[i].b;
    init();
    BackTrack(1);
    output();
    return 0;
}
           

回溯法的主要函数还可以这样写，个人比较习惯这样写，就是以排列树为解空间，然后往里面加限界条件。其实这两种写法本质上是一样的，就是习惯的问题，第一个是先算后换，第二个是先换后算，一定注意零件结构体的下标。

void BackTrack(int t)
{
    if(t>n)
    {
        for(int i=1; i<=n; ++i)
            bestx[i]=x[i];
        besttime=t2;
        return ;
    }
    else
    {
        for(int i=t; i<=n; ++i)
        {
            swap(x[t],x[i]);
            t1+=I[x[t]].a;
            int temp=t2;
            t2=max(t1,t2)+I[x[t]].b;
            if(t2<besttime)//满足限界条件
                BackTrack(t+1);
            t1-=I[x[t]].a;
            t2=temp;
            swap(x[t],x[i]);
        }
    }
}
           

参考文献：《趣学算法》