回溯法

一、批处理作业调度问题

【问题描述】

     给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理，然后由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。

批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。

【限界函数】

    批处理作业调度问题要从n个作业的所有排列中找出具有最小完成时间和的作业调度，所以如图，批处理作业调度问题的解空间是一颗排列树。按照回溯法搜索排列树的算法框架，设开始时x = [1, .., n]是所给的 n 个 作业，则相应的排列树由所有排列构成。     

【例】：设n=3，考虑以下实例：

tji          机器1     机器2

作业1         2          1

作业2         3          1

作业3         2          3

这3个作业的6种可能的调度方案是1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；

它们所相应的完成时间和分别是19，18，20，21，19，19。

易见，最佳调度方案是1,3,2，其完成时间和为18。

以1,2,3为例:

作业1在机器1上完成的时间为2,在机器2上完成的时间为3

作业2在机器1上完成的时间为5,在机器2上完成的时间为6

作业3在机器1上完成的时间为7,在机器2上完成的时间为10

3+6+10=19，所以是19

1，3，2

作业1在机器1上完成的时间为2, 在机器2上完成的时间为3

作业3在机器1上完成的时间为4,在机器2上完成的时间为7

作业2在机器1上完成的时间为7,在机器2上完成的时间为8

3+7+8=18，所以时间和为18

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int best_t=0x7fffffff,ans[100];
void backtrack(int **time,int *fin,int *x,int n,int t1,int sum,int i){
    if(i>n&&sum<best_t){
        best_t=sum;
        for(int i=1;i<=n;i++) ans[i]=x[i];
        return ;
    }
    for(int j=i;j<=n;j++){
        t1+=time[x[j]][1];
        fin[i]=max(fin[i-1],t1) + time[x[j]][2];
        sum+=fin[i];
        if(sum<best_t){
            swap(x[i],x[j]);
            backtrack(time,fin,x,n,t1,sum,i+1);
            swap(x[i],x[j]);
        }
        t1-=time[x[j]][1];
        sum-=fin[i];
    }
}
int main(){
    int n,
    **time,
    x[100],
    fin[100];
    cin>>n;
    time=new int *[n+1];
    for(int i=1;i<=n;i++)
        time[i]=new int[3];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=2;j++)
            cin>>time[i][j];
        x[i]=i;
        fin[i]=0;
    }
    fin[0]=0;
    backtrack(time,fin,x,n,0,0,1);
    cout<<"最优完成时间: "<<best_t<<endl;
    cout<<"最佳调度方案: "<<endl;
    for(int i =1; i < n; i++){
       cout<<ans[i]<<"->";
    }
    cout<<ans[n]<<endl;
    return 0;
}

二、图的着色问题

    图的着色问题是由地图的着色问题引申而来的：用m种颜色为地图着色，使得地图上的每一个区域着一种颜色，且相邻区域颜色不同。

通常所说的着色问题是指下述两类问题：

    1．给定无环图G=(V,E)，用m种颜色为图中的每条边着色，要求每条边着一种颜色，并使相邻两条边有着不同的颜色，这个问题称为图的边着色问题。

    2．给定无向图G=(V,E)，用m种颜色为图中的每个顶点着色，要求每个顶点着一种颜色，并使相邻两顶点之间有着不同的颜色，这个问题称为图的顶着色问题。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int ans=0;
void Backtrack(int **link,int *color,int i,int n,int m){
    if(i>n) {
        ans++;
        for(int i=1;i<=n;i++) cout<<color[i]<<' ';
        cout<<endl;
        return ;
    }
    for(int j=1;j<=m;j++){
        color[i]=j;
        int flag=0;
        for(int l=1;l<=n;l++){
            if(link[i][l]&&color[i]==color[l]) {
                flag=1;
                break;
            }
        }
        if(!flag)
            Backtrack(link,color,i+1,n,m);
    }
    color[i]=0;//回溯法最重要的一点
}
int main(){
    cout<<"请输入点的个数,可用颜色的个数："<<endl;
    int n,m,**link,*color;
    cin>>n>>m;
    link=new int*[n+1];
    for(int i=1;i<=n;i++) link[i]=new int[n+1];
    color=new int[n+1];
    cout<<"请输入相邻点矩阵："<<endl;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            cin>>link[i][j];
    }
    ans=0;
    Backtrack(link,color,1,n,m);
    cout<<"一共有"<<ans<<"种涂色方法."<<endl;
    for(int i=1;i<=n;i++) delete []link[i];
    delete []color;
    delete []link;
    return 0;