下载文档原格式
算法设计与分析——批处理作业调度（回溯法）之前讲过⼀个相似的问题流⽔作业调度问题，那⼀道题最开始⽤动态规划，推到最后得到了⼀个Johnson法则，变成了⼀个排序问题，有兴趣的可以看⼀下本篇博客主要参考⾃⼀、问题描述给定n个作业的集合{J1,J2,…,Jn}。
每个作业必须先由机器1处理，然后由机器2处理。
作业Ji需要机器j的处理时间为t ji。
对于⼀个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。
所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。
批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度⽅案，使其完成时间和达到最⼩。
例：设n=3，考虑以下实例：看到这⾥可能会对这些完成时间和是怎么计算出来的会有疑问，这⾥我拿123和312的⽅案来说明⼀下。
对于调度⽅案（1,2,3）作业1在机器1上完成的时间是2，在机器2上完成的时间是3作业2在机器1上完成的时间是5，在机器2上完成的时间是6作业3在机器1上完成的时间是7，在机器2上完成的时间是10所以，作业调度的完成时间和= 3 + 6 + 10这⾥我们可以思考⼀下作业i在机器2上完成的时间应该怎么去求？作业i在机器1上完成的时间是连续的，所以是直接累加就可以。
但对于机器2就会产⽣两种情况，这两种情况其实就是上图的两种情况，对于（1,2,3）的调度⽅案，在求作业2在机器2上完成的时间时，由于作业2在机器1上还没有完成，这就需要先等待机器1处理完；⽽对于（3,1,2）的调度⽅案，在求作业2在机器2上完成的时间时，作业2在机器1早已完成，⽆需等待，直接在作业1被机器1处理之后就能接着被处理。
综上，我们可以得到如下表达式if(F2[i-1] > F1[i])F2[i] = F2[i-1] + t[2][i]elseF2[i] = F1[i] + t[2][i]⼆、算法设计类Flowshop的数据成员记录解空间的结点信息，M输⼊作业时间，bestf记录当前最⼩完成时间和，数组bestx记录相应的当前最佳作业调度。
1、问题描述：n个作业{1，2，…，n}要在由2台机器M1和M2组成的流水线上完成加工。
每个作业加工的顺序都是先在M1上加工，然后在M2上加工。
M1和M2加工作业i所需的时间分别为ai和bi。
流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。
2、问题分析直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。
在一般情况下，机器M2上会有机器空闲和作业积压2种情况。
设全部作业的集合为N={1，2，…，n}。
S是N的作业子集。
在一般情况下，机器M1开始加工S中作业时，机器M2还在加工其他作业，要等时间t后才可利用。
将这种情况下完成S中作业所需的最短时间记为T(S,t)。
流水作业调度问题的最优值为T(N,0)。
设π是所给n个流水作业的一个最优调度，它所需的加工时间为aπ(1)+T’。
其中T’是在机器M2的等待时间为bπ(1)时，安排作业π(2)，…，π(n)所需的时间。
记S=N-{π(1)}，则有T’=T(S,bπ(1))。
证明：事实上，由T的定义知T’>=T(S,bπ(1))。
若T’>T(S,bπ(1))，设π’是作业集S在机器M2的等待时间为bπ(1)情况下的一个最优调度。
则π(1)，π'(2)，…，π'(n)是N的一个调度，且该调度所需的时间为aπ(1)+T(S,bπ(1))<aπ(1)+T’。
这与π是N的最优调度矛盾。
故T’<=T(S,bπ(1))。
从而T’=T(S,bπ(1))。
这就证明了流水作业调度问题具有最优子结构的性质。
由流水作业调度问题的最优子结构性质可知:从公式（1）可以看出，该问题类似一个排列问题，求N个作业的最优调度问题，利用其子结构性质，对集合中的每一个作业进行试调度，在所有的试调度中，取其中加工时间最短的作业做为选择方案。
将问题规模缩小。
批处理作业调度问题描述：N个作业要在两台机器上处理，每个作业必须先由机器1处理，然后再由机器2处理，机器1处理作业i所需时间为ai，机器2处理作业i所需时间为bi，批处理作业调度问题要求确定这n个作业的最优处理顺序，使得到处理结束所需的时间和最少。
输入：输出：最节省时间为25 应对方案为 1 3 2算法描述：回溯法按深度优先策略搜索问题的解空间树。
首先从根节点出发搜索解空间树，当算法搜索至解空间树的某一节点时，先利用剪枝函数判断该节点是否可行（即能得到问题的解）。
如果不可行，则跳过对该节点为根的子树的搜索，逐层向其祖先节点回溯；否则，进入该子树，继续按深度优先策略搜索。
回溯法的基本行为是搜索，搜索过程使用剪枝函数来为了避免无效的搜索。
剪枝函数包括两类：1. 使用约束函数，剪去不满足约束条件的路径；2.使用限界函数，剪去不能得到最优解的路径。
问题的关键在于如何定义问题的解空间，转化成树（即解空间树）。
解空间树分为两种：子集树和排列树。
两种在算法结构和思路上大体相同。
算法设计：设数组a[n]存储n个作业在机器1上的处理时间，数组b[n]存储n个作业在机器2上的处理时间。
数组x[n]存储具体的作业调度，初始迭代时x[0]表示未安排作业，x[k]表示第k个作业的编号。
数组sum1[n]存储机器1的完成时间，sum2[n]存储机器2的完成时间，初始迭代时sum1[0]和sum2[0]均为0，表示完成时间均为0，sum1[k]表示在安排第k个作业后机器1的当前完成时间，sum2[k]表示在安排第k个作业后机器2的当前完成时间举例：有三个作业1, 2, 3，这三个作业在机器1上所需的处理时间为(2, 5, 4)，在机器2上所需的处理时间为(3, 2, 1)，确定这n个作业的最优处理顺序，使得到处理结束所需的时间和最少。
确定这3个作业的最优处理顺序，使得到处理结束所需的时间和最少。
由此可知，最优处理顺序为（1，2，3）和（2，1，3）最短完成时间为12#include <iostream>using namespace std;#define MAX 200int* x1;//作业Ji在机器1上的工作时间；int* x2;//作业Ji在机器2上的工作时间；int number=0;//作业的数目；int* xOrder;//作业顺序；int* bestOrder;//最优的作业顺序；int bestValue=MAX;//最优的时间；int xValue=0;//当前完成用的时间；int f1=0;//机器1完成的处理时间；int* f2;//第i阶段机器2完成的时间；void BackTrace(int k){if (k>number){for (int i=1;i<=number;i++){bestOrder[i]=xOrder[i];}bestValue=xValue;}{for (int i=k;i<=number;i++){f1+=x1[xOrder[i]];f2[k]=(f2[k-1]>f1?f2[k-1]:f1)+x2[xOrder[i]];xValue+=f2[k];swap(xOrder[i],xOrder[k]);if (xValue<bestValue){BackTrace(k+1);}swap(xOrder[i],xOrder[k]);xValue-=f2[k];f1-=x1[xOrder[i]];}}}int main(){int i;cout<<"请输入作业数目：";cin>>number;x1=new int[number+1];x2=new int[number+1];xOrder=new int[number+1];bestOrder=new int[number+1];f2=new int[number+1];x1[0]=0;x2[0]=0;xOrder[0]=0;bestOrder[0]=0;f2[0]=0;cout<<"请输入每个作业在机器1上所用的时间："<<endl; for (int i=1;i<=number;i++){cout<<"第"<<i<<"个作业=";cin>>x1[i];}cout<<"请输入每个作业在机器2上所用的时间："<<endl; for (i=1;i<=number;i++){cout<<"第"<<i<<"个作业=";cin>>x2[i];}for (i=1;i<=number;i++){xOrder[i]=i;}BackTrace(1);cout<<"最节省的时间为："<<bestValue;cout<<endl;cout<<"对应的方案为：";for (i=1;i<=number;i++){cout<<bestOrder[i]<<" ";}System (“pause”);return 0;}。
1、回溯法(1)描述:回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。
但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。
(2)原理:回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。
算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。
如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。
回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。
这种方法适用于解一些组合数相当大的问题。
有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。
(3)问题的解空间问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,…,xn)的形式。
显约束：对分量xi的取值限定。
隐约束：为满足问题的解而对不同分量之间施加的约束。
解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。
注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）。
例1：n=3的0——1 背包问题的回溯法搜索过程。
W=[16,15,15] p=[45,25,25] C=30例2：旅行售货员问题。
某售货员要到若干城市去推销商品，已知各城市之间的路程（旅费），他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（总旅费）最小。
(4)生成问题状态的基本方法扩展结点:一个正在产生儿子的结点称为扩展结点。
活结点:一个自身已生成但其儿子还没有全部生成的节点称做活结点。
死结点:一个所有儿子已经产生的结点称做死结点。
深度优先的问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。
在完成对子树C（以C 为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R 的下一个儿子（如果存在）。
调度问题中的算法作者：***来源：《中国信息技术教育》2020年第11期说到“调度”，人们往往会想到交通运输部门的运行安排，也会想到企业中复杂的生产任务安排。
其实，日常生活中也经常面临着多个事项需要合理安排;只不过任务数不大，也不涉及明显的经济指标限制，人们凭经验就足以应付，很少会联想到“算法”。
当需要解决的任务数增加，且包含相互依赖关系时，算法可以帮助我们顺利有效地完成任务。
● 单纯依赖关系约束下的任务调度我们从仅考虑任务间的依赖约束开始。
如果任务X只能在另外某个任务Y完成后才能开始，我们就说X依赖Y。
下面来看一个简单的例子。
同学们打算在教室里组织一场联欢活动，还准备自己动手包饺子。
他们拟定了一张准备工作任务表，包含所有任务事项、每项任务耗时、任务间依赖关系（注意：只需列出直接依赖关系，而间接依赖关系自然地隐含在其中）。
管理上通常将这些任务的集合称为一个“项目”。
任务列表见表1。
有些任务之间没有依赖关系，执行顺序无关紧要，如果有多个执行者，这样的任务就可以并行。
这里说的“调度”，就是要给每项任务分配一个不同的序号，表示它们执行的顺序，满足：如果任务X依赖任务Y，则X的序号就要大于Y的序号;如果两个任务之间没有依赖关系，则对它们的序号关系没有要求。
从数学上看，原来所有任务间的依赖关系确定了一个“偏序”，即并非任意两个任务都必须“有先后”（称为“可比”）。
调度就是要在此基础上生成一个“全序”，即任何两个任务皆“可比”，对任意两个原来就“可比”的任务，新关系与原关系保持一致。
换句话说，如果按照这个序号串行执行，一定满足原来要求的依赖关系。
这个问题被称为“拓扑排序”问题。
读者应该注意到，如果只要解决拓扑排序问题，我们并不需要考虑上述例子中每项子任务的耗时。
我们可以建立一个有向图模型。
图中每个节点表示一个任务，节点X和Y之间存在从X 到Y的有向边（X→Y）当且仅当对应的任务X直接依赖于任务Y。
上述例子的图模型如下页图1所示。
回溯算法解决八数码问题的实现和优化回溯算法是一种经典的求解问题的方法，通过尝试所有可能的解来找到问题的最优解。
八数码问题是一种经典的拼图游戏，其目标是将一个3×3的方格中的数字按照特定的规则进行移动，最终使得数字按照给定的顺序排列。
本文将介绍回溯算法在解决八数码问题时的实现方法，并探讨如何通过一些优化技巧提高算法的效率。
一、八数码问题八数码问题是一个经典的数学问题，其具体要求是给定一个初始状态和一个目标状态，通过移动数字的方式，将初始状态转变为目标状态。
在八数码问题中，初始状态和目标状态都由一个3×3的方格组成，其中包含数字1到8和一个空格，初始状态和目标状态可以用一个矩阵表示。
例如，下面是一个八数码问题的初始状态和目标状态：初始状态：1 2 34 6 87 5目标状态：1 2 34 5 67 8在每一步移动中，可以选择将空格上、下、左、右四个方向的数字与空格进行交换。
通过一系列的移动操作，最终希望将初始状态转变为目标状态。
而解决八数码问题的关键就是找到从初始状态到目标状态的最短路径。
二、回溯算法解决八数码问题的实现回溯算法是一种穷举搜索方法，通过尝试所有可能的解来找到问题的最优解。
在解决八数码问题时，回溯算法可以通过深度优先搜索的方式遍历所有可能的移动序列，直到找到目标状态或者搜索完所有可能。
具体来说，回溯算法可以通过以下步骤来解决八数码问题：1. 将初始状态加入到一个空的路径列表中。
2. 从初始状态开始，尝试将空格与上、下、左、右四个方向的数字进行交换，得到所有可能的移动后的状态。
3. 对于每一个移动后的状态，判断是否已经达到了目标状态。
如果是，则找到了最短路径；如果不是，则将移动后的状态加入到路径列表中，并继续进行下一步的移动。
4. 重复步骤2和3，直到搜索完所有可能的移动序列或者找到了最短路径。
5. 如果找到了最短路径，返回路径列表；否则，返回无解。
三、回溯算法解决八数码问题的优化尽管回溯算法能够解决八数码问题，但是在面对较大规模的问题时，其效率较低。
假设有4个作业j1、j2、j3和j4,到达时间分别为0、1、1和3,运行时间分别为3、3、2和
本文主要介绍四个作业j1、j2、j3和j4的短程调度，根据其到达时
间和运行时间来分析贪婪算法，提出调度问题的解决方案。
一、四个作业j1、j2、j3和j4的短程调度
1. 四个作业的详细参数
以上四个作业的基本参数情况如下表所示：
| 作业 | 到达时间（t） | 运行时间（cpu） |
| :-----: | :-----------: | :------------: |
| j1 | 0 | 3 |
| j2 | 1 | 3 |
| j3 | 1 | 2 |
| j4 | 3 | 2 |
2. 贪婪算法的实施
在贪婪算法的实施，将作业按照到达时间以及运行时间一次进行排序，按照“到达时间先小后大，同到达时间即运行时间先小后大”的原则，
选择到达时间最短且花费cpu时间最短的作业，依次进行调度或运行，即j1，j3，j2，j4.
三、贪婪算法的总结
通过以上分析，可以得出用贪婪算法解决作业调度问题的总结：
1. 对于多个作业问题，可以根据作业的到达时间和运行时间，按照时间的先后顺序进行排序，依次选出最少用时的作业进行调度；
2. 对于每个作业问题，可以采用贪婪算法进行，以期达到最小的花费总时数，即时间的最优利用。
综上所述，用贪婪算法解决作业调度问题非常有效，可以让我们找到最优解，而且算法本身比较容易实现，使用起来效果比较好，可以满足不断变化的条件下多作业的解决方案，特别是多作业间有关联的短程作业调度问题的求解。
1、批作度(1)问题描述定 n 个作的集合 {J1,J2, ⋯,Jn}。
每个作必先由机器 1 理，然后由机器 2 理。
作 Ji 需要机器 j 的理 tji。
于一个确定的作度， Fji 是作 i 在机器 j 上完成理的。
所有作在机器 2 上完成理的和称作度的完成和。
批处理作业调度问题要求对于给定的 n 个作业，制定最佳作业调度方案，使其完成时间和达到最小。
例： n=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。
(2)算法设计批理作度要从 n 个作的所有排列中找出具有最小完成和的作度，所以如，批理作度的解空是一排列树。
按照回溯法搜索排列的算法框架，开始 x=[1,2, ⋯⋯n]是所的 n 个作，相的排列由 x[1:n] 的所有排列构成。
算法具体代如下：[cpp]view plain copy1.#include "stdafx.h"2.#include <iostream>ing namespace std;4.5.class Flowshop6.{7.friend int Flow( int **M, int n, int bestx[]);8.private :9. void Backtrack( int i);10.11. int **M, // 各作业所需的处理时间12. *x, // 当前作业调度13. *bestx, // 当前最优作业调度14.15. *f2, // 机器 2 完成处理时间16. f1, // 机器 1 完成处理时间17. f, // 完成时间和18.19. bestf, // 当前最优值20. n; // 作业数21.};22.23. int Flow( int **M, int n, int bestx[]);24.25. template < class Type>26. inline void S &a, Type &b);27.28.int main()29.{30.int n=3,bf;31.int M1[4][3]={{0,0,0},{0,2,1},{0,3,1},{0,2,3}};32.33.int **M= new int *[n+1];34.35.for ( int i=0;i<=n;i++)36.{37.M[i]=new int[3];38.}39.cout<<"M(i,j) 值如下： " <<endl;40.41.for ( int i=0;i<=n;i++)42.{43.for ( int j=0;j<3;j++)44.{45.M[i][j]=M1[i][j];46.}47.}48.49.int bestx[4];50.for ( int i=1;i<=n;i++)51.{52.53.54.55. cout<< "(" ;for ( int j=1;j<3;j++)cout<<M[i][j]<< " " ; cout<< ")" ;56.}57.58.bf=Flow(M,n,bestx);59.60.for ( int i=0;i<=n;i++)61.{62.delete[]M[i];63.}64.delete []M;65.66.M=0;67.68.cout<<endl<<" 最优值是： " <<bf<<endl;69.cout<<" 最优调度是： " ;70.71.for ( int i=1;i<=n;i++)72.{73.cout<<bestx[i]<<" " ;74.}75.cout<<endl;76.return 0;77.}78.79. void Flowshop::Backtrack(int i)80.{81.if (i>n)82.{83.for ( int j=1; j<=n; j++)84.{85.bestx[j] = x[j];86.}87.bestf = f;88.}89.else90.{91.for ( int j = i; j <= n; j++)92.{93.f1+=M[x[j]][1];94.// 机器 2 执行的是机器 1 已完成的作业，所以是i-195.f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+M[x[j]][2];96.97.f+=f2[i];98.if (f < bestf)// 剪枝99.{100. Swap(x[i], x[j]);101. Backtrack(i+1);102. Swap(x[i], x[j]);103.}104.f1-=M[x[j]][1];105.f-=f2[i];106.}107.}108.}109.110. int Flow( int **M, int n, int bestx[])111.{112.int ub=30000;113.114.Flowshop X;115.X.n=n;116. X.x= new int [n+1];117. X.f2= new int [n+1];118.119.X.M=M;120.X.bestx=bestx;121.X.bestf=ub;122.123.X.f1=0;124.X.f=0;125.126.for ( int i=0;i<=n;i++)127.{128.X.f2[i]=0,X.x[i]=i;129.}130.X.Backtrack(1);131.delete []X.x;132.delete []X.f2;133.return X.bestf;134.}135.136.template < class Type>137. inline void S &a, Type &b)138.{139.Type temp=a;140.a=b;141.b=temp;142.}由于算法 Backtrack 在每一个节点处耗费O(1) 计算时间，故在最坏情况下，整个算法计算时间复杂性为O(n!) 。
【分支限界法】批处理作业调度问题问题描述给定n个作业的集合J1,J2,…,J。
每个作业必须先由机器1处理，然后由机器2处理。
作业Ji需要机器j的处理时间为tji。
对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。
所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。
批处理作业调度问题要求对于给定的个作业，制定最佳作业调度方案，使其完成时间和达到最小例：设n=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。
限界函数批处理作业调度问题要从n个作业的所有排列中找出具有最小完成时间和的作业调度，所以如图，批处理作业调度问题的解空间是一颗排在作业调度问相应的排列空间树中，每一个节点E都对应于一个已安排的作业集,……〈。
以该节点为根的子树中所含叶节点的完成时间和可表示为：设|M|=r,且L是以节点E为根的子树中的叶节点，相应的作业调度为｛pk,k=1,2,……1其中pk是第k个安排的作业。
如果从节点E到叶节点L的路上，每一个作业pk在机器1上完成处理后都能立即在机器2上开始处理，即从p r+1开始，机器1没有空闲时间，则对于该叶节点L有：Z七=2 ［耳心+(〃-左+1居网+%热］=d£叩+1i更M注：(n-k+1)tipk因为是完成时间和，所以，后续的n-k+1)个作业完成时间和都得算上ipk。
如果不能做到上面这一点，则si只会增加，从而有：下；, 一」。
类似地，如果从节点E开始到节点L的路上，从作业p r+1开始，机器2没有空闲时间，则：日25；E ［max(勺，/+呻4) + ("4 + 1H热］k=r+l冈同理可知，s2是三；•的下界。
由此得到在节点E处相应子树中叶节点完成时间和的下界是：/吓 J+maxf3}ieM注意到如果选择Pk，使tipk在k>=r+1时依非减序排列，S1则取得极小值。
分支限界法求解批作业处理调度问题的实验总结(一)前言本文将介绍分支限界法在求解批作业处理调度问题中的实验结果，并总结这种方法在实践中的应用效果。
批作业处理调度问题是一个经典的优化问题，通过引入分支限界法求解，可以有效提高求解效率。
正文问题描述批作业处理调度问题是将一批作业分配给多台处理机，使得总完成时间最短。
每个作业有一个处理时间，各个处理机的处理速度可能不同，且每个处理机同时只能处理一项作业。
问题的目标就是找到一个合适的作业分配方案，使得总完成时间最小。
分支限界法原理分支限界法是一种优化算法，通过不断剪枝和界限约束，逐步地搜索最优解。
在批作业处理调度问题中，分支限界法的基本思想是将问题划分为子问题，并通过计算每个子问题的上界，动态地选择优先搜索的分支。
本次实验选取了一批作业和多台处理机，随机生成了作业的处理时间和处理机的处理速度。
利用分支限界法和贪心算法分别求解了批作业处理调度问题，并比较了两者的求解效果。
实验结果实验结果显示，分支限界法在求解批作业处理调度问题时表现出了较高的效率和准确性。
与贪心算法相比，分支限界法能够找到更优的作业分配方案，并且所需的计算时间相对较短。
实际应用分支限界法在实际生产中广泛应用于调度问题的求解。
无论是生产线的作业调度、机器设备的任务分配，还是人员的排班安排，都可以通过分支限界法来优化求解。
其高效的搜索方式和较好的求解结果使其成为一种实用的求解方案。
结尾通过本次实验，我们验证了分支限界法在求解批作业处理调度问题中的有效性。
分支限界法不仅能够在较短的时间内找到较优的解决方案，而且还可以应用于各种实际的调度问题。
希望通过本文的介绍，能够增加对分支限界法的了解和认识，并促进其在实际应用中的推广和应用。
为了求解批作业处理调度问题，我们使用了分支限界法和贪心算法两种方法进行对比。
首先，我们随机生成了一批作业和多台处理机。
每个作业的处理时间和每台处理机的处理速度也随机生成。
这样可以模拟实际情况中作业的不同耗时和处理机的不同处理能力。
符号三角形问题回溯法
符号三角形问题可以使用回溯法来解决。
回溯法在求解问题时，首先采取深度优先遍历，当发现当前搜索
的解不符合条件时，就返回上一步，回溯到上一个状态继续搜索。
这
种方法是一种暴力搜索的方法，但是当搜索错解时，可以避免无效的
搜索。
针对符号三角形问题，我们可以将问题转化为填充三角形，使得
每行的相邻两个数字之间的运算符的结果等于该行的最后一个数字。
我们可以从三角形的顶部开始填充，用一个列表来存储路径，每
次添加一个新的数字时，都会对路径进行检查，以确认当前状态是否
满足条件。
如果符合条件，则继续向下搜索，否则回溯到上一个状态。
如果找到了一个合法的解，就将它输出，并回溯到上一个状态，
搜索下一个可能的解。
需要注意的是，在回溯过程中，我们需要将已经访问过的节点进
行标记，避免重复访问。
通过回溯法求解符号三角形问题，可以快速地找到所有合法的解，但是需要遍历所有的可能解，因此时间复杂度较高。
符号三角形问题计算机科学与技术一班徐启桂学号20044155591、思想：写出主函数，写出打印函数，根据书上给出的类，可以实现该问题对于符号三角行问题，用n元数组x[1：n]存放第一行的n个符号，用递归方法backtrack（i）实现对整个解空间的回溯搜索。
backtrack（）搜索解空间第i层子树。
当i>n时，臬法搜索至叶结点，得到一个新的”+”个数与”-“的个数相同的符号三角形，当前已找到符号三角形数sum增加1.当i<n时，当前扩展结点Z是解空间中的内部结点。
该结点有x[i]=1和x[i]=0共两个儿子结点。
对当前扩展结点Z的每一个儿子结点，计算其相应的符号三角形中”+”个数count与”-“个数，并以深度优先的主式递归地对可行子树搜索，或剪去不可行子树。
//主函数：public static void main(String []args){System.out.println("要求解的符号三角形打印如下：\n");long sum = compute(3);//输入的个数为3；System.out.println("\n符合要求的符号三角形的个数共为:"+sum);}//打印函数：public static void printTriangles(){int m = n;// System.out.println(m--);for(int i = 1;i <= n;i++){for(int k = 1;k < i;k++)System.out.print(" ");for(int j = 1;j <= m;j++){if(p[i][j] == 1)System.out.print("+ ");else if(p[i][j] == 0)System.out.print("- ");}m--;System.out.println();}}/backtrack函数：private static void backtrack(int t){if((count>half)||(t*(t-1)/2-count>half)) return;//判断当前层+号和-号的个数是否满足约束条件if(t>n){sum++;printTriangles();}elsefor(int i=0;i<2;i++){ //三角形的第一层有两种可能性，分别考虑p[1][t]=i; //第一层放符号i，i=0，-号，i=1，+号count+=i; //统计+号的个数for(int j=2;j<=t;j++){p[j][t-j+1]=1-(p[j-1][t-j+1]^p[j-1][t-j+2]);count+=p[j][t-j+1];}backtrack(t+1);for(int j=2;j<=t;j++)count-=p[j][t-j+1];count-=i;}}算法分析：计算可行性约束需要o(n)时间，最坏情况下有2的n次方个结点需要计算，因此该回溯算法所需要的时间是o(n 2xN): 二的n次方。
Python回溯算法及八皇后问题一、回溯算法1. 回溯算法的概念回溯算法是一种通过探索所有可能的候选解来找出所有解的算法。
如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化来舍弃该解。
回溯算法通常用于解决组合优化问题，如八皇后问题、图的着色问题等。
2. 回溯算法的基本思路回溯算法的基本思路是从一组可能的解中选择一个解，然后递归地对剩下的未解决的问题进行同样的操作。
当一个问题的所有可能解都被找到时，算法结束。
如果在搜索过程中发现当前解不满足约束条件，可以回溯到上一步，尝试其他可能的解。
3. 回溯算法的实现步骤（1）确定问题的解空间，定义一个函数来描述问题的约束条件和目标函数。
（2）使用递归或栈来实现回溯过程。
在每一层递归中，选择一个可能的解，然后递归地处理剩下的未解决的问题。
如果当前解满足约束条件，将其添加到结果集中；否则，回溯到上一步，尝试其他可能的解。
（3）当所有可能的解都被找到时，算法结束。
输出结果集。
二、八皇后问题及其回溯解法1. 八皇后问题的描述八皇后问题是一个简单的组合优化问题，要求在一个8×8的棋盘上放置8个皇后，使得它们互不攻击（即任意两个皇后不在同一行、同一列和同一对角线上）。
这个问题可以用回溯算法求解。
2. 八皇后问题的暴力解法暴力解法是直接枚举所有可能的解，然后检查是否满足约束条件。
这种方法的时间复杂度为O(N!)，其中N为皇后的数量（在本问题中为8）。
暴力解法的代码实现如下：```pythondef is_valid(board, row, col):for i in range(row):if board[i] == col or abs(board[i] - col) == abs(i - row):return Falsereturn Truedef solve_n_queens(board, row):if row == len(board):return 1count = 0for col in range(len(board)):if is_valid(board, row, col):board[row] = colcount += solve_n_queens(board, row + 1)return countdef n_queens(n):board = [-1] * nreturn solve_n_queens(board, 0)```3. 八皇后问题的回溯解法及Python实现（1）确定问题的解空间在八皇后问题中，我们可以将棋盘看作是一个一维数组，每个元素表示对应行上放置的皇后所在的列。
1、批作业调度问题(1)问题描述给定n个作业的集合{J1,J2,…,Jn}。
每个作业必须先由机器1处理，然后由机器2处理。
作业Ji需要机器j的处理时间为tji。
对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。
所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。
批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。
例：设n=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。
(2)算法设计批处理作业调度问题要从n个作业的所有排列中找出具有最小完成时间和的作业调度，所以如图，批处理作业调度问题的解空间是一颗排列树。
按照回溯法搜索排列树的算法框架，设开始时x=[1,2,……n]是所给的n个作业，则相应的排列树由x[1:n]的所有排列构成。
算法具体代码如下：[cpp]view plain copy1.#include "stdafx.h"2.#include <iostream>ing namespace std;4.5.class Flowshop6.{7.friend int Flow(int **M,int n,int bestx[]);8.private:9.void Backtrack(int i);10.11.int **M, // 各作业所需的处理时间12. *x, // 当前作业调度13. *bestx, // 当前最优作业调度14.15. *f2, // 机器2完成处理时间16. f1, // 机器1完成处理时间17. f, // 完成时间和18.19. bestf, // 当前最优值20. n; // 作业数21. };22.23.int Flow(int **M,int n,int bestx[]);24.25.template <class Type>26.inline void Swap(Type &a, Type &b);27.28.int main()29.{30.int n=3,bf;31.int M1[4][3]={{0,0,0},{0,2,1},{0,3,1},{0,2,3}};32.33.int **M=new int*[n+1];34.35.for(int i=0;i<=n;i++)36. {37. M[i]=new int[3];38. }39. cout<<"M(i,j)值如下："<<endl;40.41.for(int i=0;i<=n;i++)42. {43.for(int j=0;j<3;j++)44. {45. M[i][j]=M1[i][j];46. }47. }48.49.int bestx[4];50.for(int i=1;i<=n;i++)51. {52. cout<<"(";53.for(int j=1;j<3;j++)54. cout<<M[i][j]<<" ";55. cout<<")";56. }57.58. bf=Flow(M,n,bestx);59.60.for(int i=0;i<=n;i++)61. {62.delete []M[i];63. }64.delete []M;65.66. M=0;67.68. cout<<endl<<"最优值是："<<bf<<endl;69. cout<<"最优调度是：";70.71.for(int i=1;i<=n;i++)72. {73. cout<<bestx[i]<<" ";74. }75. cout<<endl;76.return 0;77.}78.79.void Flowshop::Backtrack(int i)80.{81.if (i>n)82. {83.for (int j=1; j<=n; j++)84. {85. bestx[j] = x[j];86. }87. bestf = f;88. }89.else90. {91.for (int j = i; j <= n; j++)92. {93. f1+=M[x[j]][1];94.//机器2执行的是机器1已完成的作业，所以是i-195. f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+M[x[j]][2];96.97. f+=f2[i];98.if (f < bestf)//剪枝99. {100. Swap(x[i], x[j]); 101. Backtrack(i+1); 102. Swap(x[i], x[j]); 103. }104. f1-=M[x[j]][1];105. f-=f2[i];106. }107. }108.}109.110.int Flow(int **M,int n,int bestx[]) 111.{112.int ub=30000;113.114. Flowshop X;115. X.n=n;116. X.x=new int[n+1];117. X.f2=new int[n+1];118.119. X.M=M;120. X.bestx=bestx;121. X.bestf=ub;122.123. X.f1=0;124. X.f=0;125.126.for(int i=0;i<=n;i++)127. {128. X.f2[i]=0,X.x[i]=i;129. }130. X.Backtrack(1);131.delete []X.x;132.delete []X.f2;133.return X.bestf;134.}135.136.template <class Type>137.inline void Swap(Type &a, Type &b) 138.{139. Type temp=a;140. a=b;141. b=temp;142.}由于算法Backtrack在每一个节点处耗费O(1)计算时间，故在最坏情况下，整个算法计算时间复杂性为O(n!)。
