〖編程·C++〗回溯算法：完全N叉树最佳调度问题以及相关思考

问题描述：

假设有N个任务由K台机器完成，任务i完成任务时间为ti。设计算法使K台机器完成这N个任务所花费时间最短。

n、k由输入文件第一行给出，第二行为各个任务的花费时间，output.out输出花费的最短时间。

样例

input.in　　　　　　　　output.out

7 3　　　　　　　　　　59

14 25 1 59 19 10 39　　

输出文件加深：输出一个最佳调度的方法。

程序代码如下：

普通源程序

  1 #include <fstream>
  2 #include <iostream>
  3 
  4 using namespace std;
  5 
  6 ifstream fin("f:\\zuijiadiaodu\\input.in");
  7 ofstream fout("f:\\zuijiadiaodu\\output.out");
  8 
  9 int n,k,min_time,cur_time;
 10 int *time;
 11 int *x;
 12 int *best;
 13 int *machine;
 14 
 15 
 16 int max(int *a,int start,int end)
 17 {
 18     int result = a[start];
 19     for(int i=start+1;i<=end;i++)
 20         if(result<a[i])
 21             result=a[i];
 22     return result;
 23 
 24 
 25 }
 26 
 27 int output()
 28 {
 29     fout<<"输出最终结果："<<endl;
 30     fout<<min_time<<endl;
 31     int p;
 32     for(p=1;p<=k;p++)
 33     {
 34         fout<<"M"<<p<<":";
 35         for(int j =1;j<=n;j++)
 36             if(best[j]==p)
 37                 fout<<j<<' ';
 38         fout<<endl;
 39     }
 40     return 1;
 41 }
 42 
 43 void backtrack (int t)
 44 {
 45     if(t>n)
 46     {    /*
 47         for(int i=1;i<=n;i++)
 48         {
 49             machine[x[i]]+=time[i];
 50         
 51         }
 52 
 53         cur_time=machine[1];
 54         for(int i=2;i<=k;i++)
 55             if(cur_time<machine[i])
 56                 cur_time = machine[i];
 57         */
 58 
 59 
 60         if(cur_time < min_time)
 61         {
 62             min_time = cur_time;
 63             for(int i=1;i<=n;i++)
 64                 best[i] = x[i];
 65         
 66         }
 67     
 68     }
 69     else
 70         for(int i=1;i<=k;i++)
 71         {
 72             x[t]=i;
 73             machine[i] += time[t];
 74             cur_time = max(machine,1,k);
 75             if(cur_time < min_time)
 76                 backtrack(t+1);
 77             machine[i]-= time[t];
 78         }
 79 
 80 }
 81 
 82 int main()
 83 {
 84     fin>>n>>k;
 85     time = new int[n+1];
 86     //输入
 87     for(int i=1;i<=n;i++)
 88         fin>>time[i];
 89 
 90     x = new int [n+1];
 91     best = new int [n+1];
 92     machine = new int [k+1];
 93 
 94     for(int i=1;i<=k;i++)
 95         machine[i]=0;
 96 
 97     cur_time = 0;
 98     min_time = 0;
 99 
100     for(int i=1;i<=n;i++)
101         min_time+=time[i];
102 
103     //输出读入的数值以及赋予的初值
104     fout<<"输出读入的数值以及赋予的初值:"<<endl;
105     fout<<"n="<<n<<endl<<"k="<<k<<endl;
106     for(int i=1;i<=n;i++)
107         fout<<time[i]<<' ';
108     fout<<endl;
109     fout<<"cur_time="<<cur_time<<" "<<"min_time="<<min_time<<endl<<endl;
110 
111 
112     backtrack(1);
113     
114 
115     //输出最终结果
116     output();
117 
118     /*
119     for(int i=1;i<=n;i++)
120         fout<<best[i]<<' ';
121     fout<<endl;
122     */
123 
124     fin.close();
125     fout.close();
126 
127     delete time,x,best,machine;
128     
129     return 1;
130 }

输出如下：

普通源程序的输出截图

关于减枝的思考：

刚开始的时候，min_time=t1+t2+t3+...+tn，那么刚开始运行的时候要运行很多无用的程序才能找出真正的min_time，所以可以使用贪心算法（本问题不适用贪心算法，可以举出反例）求出与真正min_time很接近的一个值作为初值赋予min_time。使用贪心法时候需要进行判断各个机器当前最短时间，所以定义min()函数如下：

int min(int *a,int start,int end)
{//返回最小的值的编号
    int i;
    int result = start;
    for(i=start;i<=end;i++)
        if(a[result]+1>a[i])
            result=i;
    return result;
}

定义函数fackmin_time()用于求出使用贪心算法所求出的“最小值”，代码如下：

//贪心算法求出接近真实min_time的值
int fackmin_time(int *a)
{
    int result;
    int temp;
    int *fack = new int[k+1];//fack存储使用贪心算法各个机器的时间也可以用machine存储不过运行之后要重新将machine赋予0
    for(int i=1;i<=k;i++)
        fack[i]=0;
    int *time2 = new int[n+1];//将传入的time转存  防止改变time原值
    for(int i=1;i<=n;i++)
        time2[i]=time[i];

    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
            if (time2[i]<time2[j])
            {
                temp = time2[j];
                time2[j] = time2[i];
                time2[i] = temp;
            }

    if(n>k)
    {
        for(int i=1;i<=n;i++)
            fack[min(fack,1,k)]+=time2[i];
    }
    else
        for(int i=1;i<=k;i++)
            fack[i]=time2[i];

    result = max(fack,1,k);
    
    delete fack,time2;
    
    return result;
}

主函数中使用min_time = fackmin_time(time);即可给min_time赋予初值，另外，backtrack中所有的if(cur_time < min_time)都应该改为if(cur_time <= min_time)；因为fackmin_time有可能等于真实的min_time（fackmin_time(time)>=min_time）；否则best[]永远为空

改进后的程序如下：

使用贪心法减枝的源程序

  1 #include <fstream>
  2 #include <iostream>
  3 
  4 using namespace std;
  5 
  6 ifstream fin("f:\\zuijiadiaodu\\input.in");
  7 ofstream fout("f:\\zuijiadiaodu\\output.out");
  8 
  9 int n,k,min_time,cur_time;
 10 int *time;
 11 int *x;
 12 int *best;
 13 int *machine;
 14 
 15 
 16 int max(int *a,int start,int end)
 17 {
 18     int result = a[start];
 19     for(int i=start+1;i<=end;i++)
 20         if(result<a[i])
 21             result=a[i];
 22     return result;
 23 
 24 
 25 }
 26 
 27 int min(int *a,int start,int end)
 28 {//返回最小的值的编号
 29     int i;
 30     int result = start;
 31     for(i=start;i<=end;i++)
 32         if(a[result]+1>a[i])
 33             result=i;
 34     return result;
 35 }
 36 
 37 int output()
 38 {
 39     fout<<"输出最终结果："<<endl;
 40     fout<<min_time<<endl;
 41     int p;
 42     for(p=1;p<=k;p++)
 43     {
 44         fout<<"M"<<p<<":";
 45         for(int j =1;j<=n;j++)
 46             if(best[j]==p)
 47                 fout<<j<<' ';
 48         fout<<endl;
 49     }
 50     return 1;
 51 }
 52 
 53 //贪心算法求出接近真实min_time的值
 54 int fackmin_time(int *a)
 55 {
 56     int result;
 57     int temp;
 58     int *fack = new int[k+1];//fack存储使用贪心算法各个机器的时间也可以用machine存储不过运行之后要重新将machine赋予0
 59     for(int i=1;i<=k;i++)
 60         fack[i]=0;
 61     int *time2 = new int[n+1];//将传入的time转存  防止改变time原值
 62     for(int i=1;i<=n;i++)
 63         time2[i]=time[i];
 64 
 65     for(int i=1;i<n;i++)
 66         for(int j=i+1;j<=n;j++)
 67             if (time2[i]<time2[j])
 68             {
 69                 temp = time2[j];
 70                 time2[j] = time2[i];
 71                 time2[i] = temp;
 72             }
 73 
 74     if(n>k)
 75     {
 76         for(int i=1;i<=n;i++)
 77             fack[min(fack,1,k)]+=time2[i];
 78     }
 79     else
 80         for(int i=1;i<=k;i++)
 81             fack[i]=time2[i];
 82 
 83     result = max(fack,1,k);
 84     
 85     delete fack,time2;
 86     
 87     return result;
 88 }
 89 
 90 
 91 void backtrack (int t)
 92 {
 93     if(t>n)
 94     {    
 95         if(cur_time <= min_time)
 96         {
 97             min_time = cur_time;
 98             for(int i=1;i<=n;i++)
 99                 best[i] = x[i];
100         
101         }
102     
103     }
104     else
105         for(int i=1;i<=k;i++)
106         {
107             x[t]=i;
108             machine[i] += time[t];
109             cur_time = max(machine,1,k);
110             if(cur_time <= min_time)
111                 backtrack(t+1);
112             machine[i]-= time[t];
113         }
114 
115 }
116 
117 int main()
118 {
119     fin>>n>>k;
120     time = new int[n+1];
121     //输入
122     for(int i=1;i<=n;i++)
123         fin>>time[i];
124 
125     x = new int [n+1];
126     best = new int [n+1];
127     machine = new int [k+1];
128 
129     for(int i=1;i<=k;i++)
130         machine[i]=0;
131 
132     cur_time = 0;
133     //min_time = 0;
134     //for(int i=1;i<=n;i++)
135         //min_time+=time[i];
136 
137     //计算fakemin_time,给min_time赋予初值
138     min_time = fackmin_time(time);
139 
140     //输出读入的数值以及赋予的初值
141     fout<<"输出读入的数值以及赋予的初值:"<<endl;
142     fout<<"n="<<n<<endl<<"k="<<k<<endl;
143     for(int i=1;i<=n;i++)
144         fout<<time[i]<<' ';
145     fout<<endl;
146     fout<<"cur_time="<<cur_time<<" "<<"min_time="<<min_time<<endl<<endl;
147 
148 
149     backtrack(1);
150     
151 
152     //输出最终结果
153     output();
154 
155     fin.close();
156     fout.close();
157 
158     delete time,x,best,machine;
159     
160     return 1;
161 }

输出结果：

使用贪心法减枝的程序输出结果

如果要求输出全部的最佳调度方法，并输出所有的调度方法的总数？

第一次思考：采用双backtrack()方法：

　　1）输出全部的最佳调度方法：先想到的是使用一次backtrack(1)，用来求出min_time，此时backtrack函数中if(cur_time < min_time)没必要改为if(cur_time <= min_time)，因为只需要求出min_time，而不用赋予best[]值，所以我们使用前者；在使用一次backtrack_2(1)，backtrack_2()中的if(t>n)内的判断语句if(cur_time < min_time)应该改为判断if(cur_time==min_time)，相等则将x[]赋给best[],然后再调用output()进行输出，else内的语句if(cur_time < min_time)应该改为if(cur_time <= min_time)。

　　2）输出调度方法的总数问题：可以设置全局变量sum，在backtrack_2中的if(t>n)下的if(cur_time==min_time)中加入sum++，最后在主函数fout<<"总共共有"<<sum<<"种分配方式。"。

　　3）弊端：回溯法为简化的枚举算法，效率不高，本题时间复杂度原来为O(k^n)，很高，采用双backtrack算法提高一倍的时间复杂度，不合适。（其实运行时backtrack_2比backtrack花费的时间要多因为backtrack_2中t<=n时使用的是if(cur_time <= min_time)判断语句，backtrack用的是if(cur_time < min_time)。（因为backtrack只用来求min_time所以不要求=min_time，而backtrack_2用来输出所有=min_time的调度方法，所以必须要加上等号。）

原程序如下：

使用双backtrack算法的源程序

  1 #include <fstream>
  2 #include <iostream>
  3 
  4 using namespace std;
  5 
  6 ifstream fin("f:\\zuijiadiaodu\\input.in");
  7 ofstream fout("f:\\zuijiadiaodu\\output.out");
  8 
  9 int n,k,min_time,cur_time;
 10 int *time;
 11 int *x;
 12 int *best;
 13 int *machine;
 14 int sum=0;
 15 
 16 int max(int *a,int start,int end)
 17 {
 18     int result = a[start];
 19     for(int i=start+1;i<=end;i++)
 20         if(result<a[i])
 21             result=a[i];
 22     return result;
 23 
 24 
 25 }
 26 
 27 int min(int *a,int start,int end)
 28 {//返回最小的值的编号
 29     int i;
 30     int result = start;
 31     for(i=start;i<=end;i++)
 32         if(a[result]+1>a[i])
 33             result=i;
 34     return result;
 35 }
 36 
 37 int output()
 38 {
 39     
 40     /*int p;
 41     for(p=1;p<=k;p++)
 42     {
 43         fout<<"M"<<p<<":";
 44         for(int j =1;j<=n;j++)
 45             if(best[j]==p)
 46                 fout<<j<<' ';
 47         fout<<endl;
 48     }
 49     return 1;*/
 50     
 51     fout<<"最佳的调度方法"<<sum<<"):"<<endl;
 52     for(int p=1;p<=k;p++)
 53     {
 54         fout<<"    "<<"M"<<p<<"运行以下程序:"<<endl;
 55         for(int j =1;j<=n;j++)
 56             if(best[j]==p)
 57                 fout<<"    "<<"    "<<"t"<<j<<":"<<time[j]<<"min"<<endl;
 58         fout<<endl;
 59     }
 60     fout<<endl;
 61 
 62     return 1;
 63 }
 64 
 65 //贪心算法求出接近真实min_time的值
 66 int fackmin_time(int *a)
 67 {
 68     int result;
 69     int temp;
 70     int *fack = new int[k+1];//fack存储使用贪心算法各个机器的时间也可以用machine存储不过运行之后要重新将machine赋予0
 71     for(int i=1;i<=k;i++)
 72         fack[i]=0;
 73     int *time2 = new int[n+1];//将传入的time转存  防止改变time原值
 74     for(int i=1;i<=n;i++)
 75         time2[i]=time[i];
 76 
 77     for(int i=1;i<n;i++)
 78         for(int j=i+1;j<=n;j++)
 79             if (time2[i]<time2[j])
 80             {
 81                 temp = time2[j];
 82                 time2[j] = time2[i];
 83                 time2[i] = temp;
 84             }
 85 
 86     if(n>k)
 87     {
 88         for(int i=1;i<=n;i++)
 89             fack[min(fack,1,k)]+=time2[i];
 90     }
 91     else
 92         for(int i=1;i<=k;i++)
 93             fack[i]=time2[i];
 94 
 95     result = max(fack,1,k);
 96     
 97     delete fack,time2;
 98     
 99     return result;
100 }
101 
102 void backtrack (int t)
103 {
104     if(t>n)
105     {
106         if(cur_time < min_time)
107         {
108             min_time = cur_time;
109             //for(int i=1;i<=n;i++)
110                 //best[i] = x[i];
111         
112         }
113     
114     }
115     else
116         for(int i=1;i<=k;i++)
117         {
118             x[t]=i;
119             machine[i] += time[t];
120             cur_time = max(machine,1,k);
121             if(cur_time < min_time)
122                 backtrack(t+1);
123             machine[i]-= time[t];
124         }
125 
126 }
127 
128 void backtrack_2 (int t)
129 {
130     if(t>n)
131     {
132         if(cur_time == min_time)
133         {
134             sum++;
135             for(int q=1;q<=n;q++)
136                 best[q]=x[q];
137             output();
138         }
139     
140     }
141     else
142         for(int i=1;i<=k;i++)
143         {
144             x[t]=i;
145             machine[i] += time[t];
146             cur_time = max(machine,1,k);
147             if(cur_time <= min_time)
148                 backtrack_2(t+1);
149             machine[i]-= time[t];
150         }
151 
152 }
153 
154 int main()
155 {
156     fin>>n>>k;
157     time = new int[n+1];
158     //输入
159     for(int i=1;i<=n;i++)
160         fin>>time[i];
161 
162     x = new int [n+1];
163     best = new int [n+1];
164     machine = new int [k+1];
165 
166     for(int i=1;i<=k;i++)
167         machine[i]=0;
168 
169     cur_time = 0;
170     //计算fakemin_time,给min_time赋予初值
171     min_time = fackmin_time(time);
172 
173     //输出读入的数值以及赋予的初值
174     fout<<"输出读入的数值以及赋予的初值:"<<endl;
175     fout<<"n="<<n<<endl<<"k="<<k<<endl;
176     for(int i=1;i<=n;i++)
177         fout<<time[i]<<' ';
178     fout<<endl;
179     fout<<"cur_time="<<cur_time<<" "<<"min_time="<<min_time<<endl<<endl;
180 
181 
182     backtrack(1);
183     cur_time = 0;
184 
185 
186     //输出最终结果
187     fout<<"输出最终结果："<<endl;
188     fout<<min_time<<"min"<<endl;
189     backtrack_2(1);
190     fout<<"总共共有"<<sum<<"种分配方式。";
191 
192 
193 
194     fin.close();
195     fout.close();
196 
197     delete time,x,best,machine;
198     
199     return 1;
200 }

输出结果：

使用双backtrack算法的输出截图

第二次思考：采用存储叶子节点cur_time方法：

　　1）输出全部的最佳调度方法：新定义一个数组int *record;，数组长度为k^n+1（即0~k^n但只使用1~k^n），用来记录到达每个叶子节点时候该叶子节点的cur_time，数组初始化值全为0，即：for(int i=1;i<=pow(k,n);i++) record[i] = min_time，backtrack中if(t>n)下的 if(cur_time <= min_time)后面存储当前达到的叶子节点的cur_time。

　　那么如何存储？根据n+1层完全k叉树叶子节点从1开始编号一直到k^n，知道路径就可以求出叶子节点的编号。

　　知道路径求节点编号代码如下：

int m;
for(int i=1;i<=n;i++)
{
    m+=(x[i]-1)*(pow(k,n-i));//k,n为全局变量
}
m+=1;//最后的m为节点的编号，因为节点从1编号所以最后自加一次

　　因为record[]分配内存以及后续各种操作要用到pow(x,y)函数来求x^y，C++中pow函数默认为double类型，要重载函数，重载pow()代码如下：

int pow(int base,int power)
{
    int value=1;
    if(power == 0)
        value = 1;
    else if(power > 0)
        for(int i=1;i<=power;i++)
            value=value*base;
    return value;        

}

　　存入了record[i]之后如何求出相对应的路径？可以倒着从尾部网头部的方法求路径，所以循环中用for(j=n;j>=1;j--)方便操作，先令code=i，此时有两种情况

　　　　①若code%k=0，则k为这个任务的机器编号best[j]=k，code/k为上一个任务的对应的“节点”编号，令code=code/k；

　　　　②若code%k!=0，则code%k为这个任务的机器编号best[j]=code%k，code/k+1为上一个任务的对应的“节点”编号，令code=code/k+1；

　　上述操作重复n次(j=n;j>=1;j--)。

　　知道节点求路径的代码如下：

int j;
int code = i;
for(j=n;j>=1;j--)
{
            
    if((code%k) == 0)
    {
        best[j] = k;
        code = code/k;
    }
    else
    {
        best[j] = code%k;
        code = code/k+1;
    }
    
}

　 2）输出调度方法的总数问题：可以设置全局变量int sum=0；在output()中输出一次自加一次；也可以在output()中定义局部变量，将对record[i]的读取路径的操作也放入output()中，读一个输出一个然后sum++；最后输出sum。

　　3）弊端：虽然32位操作系统int表示的数值够大，但是方法比较笨拙，而且存入record和读取record很麻烦，相比上一个，增加空间复杂度来降低时间复杂度。

源程序如下：

采用存储叶子节点cur_time方法的源程序

  1 #include <fstream>
  2 #include <math.h>
  3 
  4 using namespace std;
  5 
  6 ifstream fin("f:\\zuijiadiaodu\\input.in");
  7 ofstream fout("f:\\zuijiadiaodu\\output.out");
  8 
  9 int n,k,min_time,cur_time;
 10 int *time;
 11 int *x;
 12 int *best;
 13 int *machine;
 14 int *record;
 15 
 16 
 17 int pow(int base,int power)
 18 {
 19     int value=1;
 20     if(power == 0)
 21         value = 1;
 22     else if(power > 0)
 23         for(int i=1;i<=power;i++)
 24             value=value*base;
 25     return value;        
 26 
 27 }
 28 
 29 int max(int *a,int start,int end)
 30 {
 31     int result = a[start];
 32     for(int i=start+1;i<=end;i++)
 33         if(result<a[i])
 34             result=a[i];
 35     return result;
 36 }
 37 
 38 int min(int *a,int start,int end)
 39 {//返回最小的值的编号
 40     int i;
 41     int result = start;
 42     for(i=start;i<=end;i++)
 43         if(a[result]+1>a[i])
 44             result=i;
 45     return result;
 46 }
 47 
 48 //贪心算法求出接近真实min_time的值
 49 int fackmin_time(int *a)
 50 {
 51     int result;
 52     int temp;
 53     int *fack = new int[k+1];//fack存储使用贪心算法各个机器的时间也可以用machine存储不过运行之后要重新将machine赋予0
 54     for(int i=1;i<=k;i++)
 55         fack[i]=0;
 56     int *time2 = new int[n+1];//将传入的time转存  防止改变time原值
 57     for(int i=1;i<=n;i++)
 58         time2[i]=time[i];
 59 
 60     for(int i=1;i<n;i++)
 61         for(int j=i+1;j<=n;j++)
 62             if (time2[i]<time2[j])
 63             {
 64                 temp = time2[j];
 65                 time2[j] = time2[i];
 66                 time2[i] = temp;
 67             }
 68 
 69     if(n>k)
 70     {
 71         for(int i=1;i<=n;i++)
 72             fack[min(fack,1,k)]+=time2[i];
 73     }
 74     else
 75         for(int i=1;i<=k;i++)
 76             fack[i]=time2[i];
 77 
 78     result = max(fack,1,k);
 79     
 80     delete fack,time2;
 81     
 82     return result;
 83 }
 84 
 85 int output()
 86 {
 87     int sum=0;
 88     int j;
 89     for(int i=1;i<=pow(k,n);i++)
 90     {
 91         if(record[i] == min_time)
 92         {
 93             sum++;
 94             int code = i;
 95             for(j=n;j>=1;j--)
 96             {
 97                 
 98                 if((code%k) == 0)
 99                 {
100                     best[j] = k;
101                     code = code/k;
102                 }
103                 else
104                 {
105                     best[j] = code%k;
106                     code = code/k+1;
107                 }
108                 
109             }
110             
111             fout<<"最佳的调度方法"<<sum<<"):"<<endl;
112             //for(j=1;j<=n;j++)
113                 //fout<<best[j];
114             
115 
116             for(int p=1;p<=k;p++)
117             {
118                 fout<<"    "<<"M"<<p<<"运行以下程序:"<<endl;
119                 for(j =1;j<=n;j++)
120                     if(best[j]==p)
121                         fout<<"    "<<"    "<<"t"<<j<<":"<<time[j]<<"min"<<endl;
122                 fout<<endl;
123             }
124 
125             
126             fout<<endl;
127         }
128     }
129 
130     fout<<"总共共有"<<sum<<"种分配方式。";
131 
132     return 1;
133 
134 }
135 
136 void backtrack (int t)
137 {
138     if(t>n)
139     {
140         if(cur_time <= min_time)
141         {
142             int m=0;
143             min_time = cur_time;
144             //for(int i=1;i<=n;i++)
145                 //best[i] = x[i];
146             for(int i=1;i<=n;i++)
147             {
148                 m+=(x[i]-1)*(pow(k,n-i));
149             }
150             m+=1;
151             record[m]=cur_time;
152         }
153     
154     }
155     else
156         for(int i=1;i<=k;i++)
157         {
158             x[t]=i;
159             machine[i] += time[t];
160             cur_time = max(machine,1,k);
161             if(cur_time <= min_time)
162                 backtrack(t+1);
163             machine[i]-= time[t];
164         }
165 
166 }
167 
168 int main()
169 {
170     fin>>n>>k;
171     time = new int[n+1];
172     //输入
173     for(int i=1;i<=n;i++)
174         fin>>time[i];
175 
176     x = new int [n+1];
177     best = new int [n+1];
178     machine = new int [k+1];
179     record = new int[pow(k,n)+1];
180 
181     for(int i=1;i<=k;i++)
182         machine[i]=0;
183 
184     cur_time = 0;
185     min_time = fackmin_time(time);
186 
187     for(int i=1;i<=pow(k,n);i++)
188         record[i] = 0;
189     
190     //输出读入的数值以及赋予的初值
191     fout<<"输出读入的数值以及赋予的初值:"<<endl;
192     fout<<"n="<<n<<endl<<"k="<<k<<endl;
193     for(int i=1;i<=n;i++)
194         fout<<time[i]<<" ";
195     fout<<endl;
196 
197 
198     backtrack(1);
199     
200     //输出最终结果
201     fout<<"输出最终结果："<<endl;
202     fout<<"最短的调度时间为:"<<min_time<<endl;
203     output();
204 
205 
206     delete time,x,best,machine,record;
207 
208     fin.close();
209     fout.close();
210     
211     return 1;
212 }

输出结果：

采用存储叶子节点cur_time方法的输出截图

第三次思考：采用链表存储路径的方法：

　　1）输出全部的最佳调度方法：

　　　　①全局定义LNode *LN,*front;front用来存储LN的第一个节点的地址，LN（不使用第一个节点）中data分配为长度为n+1的数组，LN->data[0]存储这个节点所存路径所花费的时间，LN->data[1~n]存储当前路径，即第i个任务所选用的机器：

typedef struct LNode
{
    int *data;
    struct LNode *next;
}LNode;

LNode *LN,*front;

　　　　②main()函数中初始化链表LN第一个节点：

LN = new LNode;
front = LN;    
LN->next = NULL;

　　　　③在backtrack()中if(cur_time < min_time)全部改为if(cur_time <= min_time)；另外if(t>n)内容改为：

if(t>n)
{
    if(cur_time <= min_time)
    {
        
        min_time = cur_time;
        //存入链表
         LN->next = new LNode;
        LN = LN->next;
        LN->data = new int[n+1];
        LN->next = NULL;
        LN->data[0] = cur_time;
        for(int i=1;i<=n;i++)
            LN->data[i] = x[i];
    }

}

　　　　④output()函数的改变如下：

int output()
{
    LNode *rear;
    rear = front->next;
    while(rear!=NULL)
    {
        if(rear->data[0]==min_time)
        {
            sum++;

            fout<<"最佳的调度方法"<<sum<<"):"<<endl;
            for(int p=1;p<=k;p++)
            {
                fout<<"    "<<"M"<<p<<"运行以下程序:"<<endl;
                for(int i =1;i<=n;i++)
                    if(rear->data[i]==p)
                        fout<<"    "<<"    "<<"t"<<i<<":"<<time[i]<<"min"<<endl;
                fout<<endl;
            }

            fout<<endl;
            rear=rear->next;
        }
    }
    return 1;
}

　　　　⑤最后清理内存：

//清理LN头结点内存
LNode *rear;
rear = front;
front = front->next;
free(rear);
rear=NULL;
//清理LN其他结点内存
while(front!=NULL)
{
    rear = front;
    front = front->next;
    delete rear->data;
    free(rear);
    rear=NULL;
    
}

　　2）输出调度方法的总数问题：最后主函数输出sum。

　　3）弊端：相比其他方法，这个最好，时间复杂度和空间复杂度都降至最低，老师提示用链表存储就是犀利……

源程序如下：

采用链表存储路径方法的源程序

  1 #include <fstream>
  2 #include <iostream>
  3 
  4 using namespace std;
  5 
  6 ifstream fin("f:\\zuijiadiaodu\\input.in");
  7 ofstream fout("f:\\zuijiadiaodu\\output.out");
  8 
  9 int n,k,min_time,cur_time;
 10 int *time;
 11 int *x;
 12 int *machine;
 13 int sum=0;
 14 int *data;
 15 
 16 typedef struct LNode
 17 {
 18     int *data;
 19     struct LNode *next;
 20 }LNode;
 21 
 22 LNode *LN,*front;
 23 
 24 int max(int *a,int start,int end)
 25 {
 26     int result = a[start];
 27     for(int i=start+1;i<=end;i++)
 28         if(result<a[i])
 29             result=a[i];
 30     return result;
 31 
 32 
 33 }
 34 
 35 int min(int *a,int start,int end)
 36 {//返回最小的值的编号
 37     int i;
 38     int result = start;
 39     for(i=start;i<=end;i++)
 40         if(a[result]+1>a[i])
 41             result=i;
 42     return result;
 43 }
 44 
 45 int output()
 46 {
 47     LNode *rear;
 48     rear = front->next;
 49     while(rear!=NULL)
 50     {
 51         if(rear->data[0]==min_time)
 52         {
 53             sum++;
 54 
 55             fout<<"最佳的调度方法"<<sum<<"):"<<endl;
 56             for(int p=1;p<=k;p++)
 57             {
 58                 fout<<"    "<<"M"<<p<<"运行以下程序:"<<endl;
 59                 for(int i =1;i<=n;i++)
 60                     if(rear->data[i]==p)
 61                         fout<<"    "<<"    "<<"t"<<i<<":"<<time[i]<<"min"<<endl;
 62                 fout<<endl;
 63             }
 64 
 65             fout<<endl;
 66             rear=rear->next;
 67         }
 68     }
 69     return 1;
 70 }
 71 
 72 //贪心算法求出接近真实min_time的值
 73 int fackmin_time(int *a)
 74 {
 75     int result;
 76     int temp;
 77     int *fack = new int[k+1];//fack存储使用贪心算法各个机器的时间也可以用machine存储不过运行之后要重新将machine赋予0
 78     for(int i=1;i<=k;i++)
 79         fack[i]=0;
 80     int *time2 = new int[n+1];//将传入的time转存  防止改变time原值
 81     for(int i=1;i<=n;i++)
 82         time2[i]=time[i];
 83 
 84     for(int i=1;i<n;i++)
 85         for(int j=i+1;j<=n;j++)
 86             if (time2[i]<time2[j])
 87             {
 88                 temp = time2[j];
 89                 time2[j] = time2[i];
 90                 time2[i] = temp;
 91             }
 92 
 93     if(n>k)
 94     {
 95         for(int i=1;i<=n;i++)
 96             fack[min(fack,1,k)]+=time2[i];
 97     }
 98     else
 99         for(int i=1;i<=k;i++)
100             fack[i]=time2[i];
101 
102     result = max(fack,1,k);
103     
104     delete fack,time2;
105     
106     return result;
107 }
108 
109 void backtrack (int t)
110 {
111     if(t>n)
112     {
113         if(cur_time <= min_time)
114         {
115             
116             min_time = cur_time;
117             //存入链表
118             LN->next = new LNode;
119             LN = LN->next;
120             LN->data = new int[n+1];
121             LN->next = NULL;
122             LN->data[0] = cur_time;
123             for(int i=1;i<=n;i++)
124                 LN->data[i] = x[i];
125         }
126     
127     }
128     else
129         for(int i=1;i<=k;i++)
130         {
131             x[t]=i;
132             machine[i] += time[t];
133             cur_time = max(machine,1,k);
134             if(cur_time <= min_time)
135                 backtrack(t+1);
136             machine[i]-= time[t];
137         }
138 
139 }
140 
141 int main()
142 {
143     fin>>n>>k;
144 
145     //①以下
146     LN = new LNode;
147     front = LN;    
148     //LN->data = new int[n+1];
149     LN->next = NULL;
150     //LN->data[1] = 1;
151     //①以上为头结点分配
152 
153 
154     time = new int[n+1];
155     //输入
156     for(int i=1;i<=n;i++)
157         fin>>time[i];
158 
159     x = new int [n+1];
160     machine = new int [k+1];
161 
162     for(int i=1;i<=k;i++)
163         machine[i]=0;
164 
165     cur_time = 0;
166     //计算fakemin_time,给min_time赋予初值
167     min_time = fackmin_time(time);
168 
169     //输出读入的数值以及赋予的初值
170     fout<<"输出读入的数值以及赋予的初值:"<<endl;
171     fout<<"n="<<n<<endl<<"k="<<k<<endl;
172     for(int i=1;i<=n;i++)
173         fout<<time[i]<<' ';
174     fout<<endl;
175     fout<<"cur_time="<<cur_time<<" "<<"min_time="<<min_time<<endl<<endl;
176 
177     backtrack(1);
178     
179     //输出最终结果
180     fout<<"输出最终结果："<<endl;
181     fout<<min_time<<"min"<<endl;
182     
183     output();
184 
185     fout<<"总共共有"<<sum<<"种分配方式。";
186 
187     fin.close();
188     fout.close();
189     //清理内存
190     LNode *rear;
191     while(front!=NULL)
192     {
193         rear = front;
194         front = front->next;
195         free(rear);
196     
197     }
198     delete time,x,machine;
199     
200     return 1;
201 }

输出结果：
采用链表存储路径的输出结果

总结：对于输出数目不能确定的且需要记录中间数据的问题应该使用链表动态存储

〖編程·C++〗回溯算法：完全N叉树 最佳调度问题 以及相关思考

〖編程·C++〗回溯算法：完全N叉树最佳调度问题以及相关思考