回溯法 作业

算法设计与分析——批处理作业调度（回溯法）之前讲过⼀个相似的问题流⽔作业调度问题，那⼀道题最开始⽤动态规划，推到最后得到了⼀个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.8 售货员的难题(salesman.pas)【问题描述】某乡有n个村庄（1<n<15），有一个售货员，他要到各个村庄去售货，各村庄之间的路程s（0<s<1000）是已知的，且A村到B村与B村到A村的路大多不同。

为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村，假设商店所在的村庄为1，他不知道选择什么样的路线才能使所走的路程最短。

请你帮他选择一条最短的路。

【输入】村庄数n和各村之间的路程（均是整数）。

【输出】最短的路程。

【样例】salesman,in3 {村庄数}0 2 1 {村庄1到各村的路程}1 02 {村庄2到各村的路程}2 1 0 {村庄3到各村的路程}salesman.out31.9 驾车旅行(tour.pas)【问题描述】如今许多普通百姓家有了私家车，一些人喜爱自己驾车从一个城市到另一个城市旅游。

自己驾车旅游时总会碰到加油和吃饭的问题，在出发之前，驾车人总要想方设法得到从一个城市到另一个城市路线上的加油站的列表，列表中包括了所有加油站的位置及其每升的油价（如3.25元/L）。

驾车者一般都有以下的习惯：⑴除非汽车无法用油箱里的汽油达到下一个加油站或目的地，在油箱里还有不少于最大容量一半的汽油时，驾驶员从不在加油站停下来；(2)在每个停下的加油站总是将油箱加满；(3)在加油站加油的同时，买快餐等吃的东西花去20元。

(4)从起始城市出发时油箱总是满的。

(5)加油站付钱总是精确到0.1元（四舍五入）。

(6)驾车者都知道自己的汽车每升汽油能够行驶的里程数。

现在要你帮忙做的就是编写一个程序，计算出驾车从一个城市到另一个城市的旅游在加油和吃饭方面最少的费用。

【输入】第一行是一个实数，是从出发地到目的地的距离（单位：km）。

第二行是三个实数和一个整数，其中第一个实数是汽车油箱的最大容量（单位：L）；第二个实数是汽车每升油能行驶的公里数；第三个实数是汽车在出发地加满油箱时的费用（单位：元），一个整数是1到50间的数，表示从出发地到目的地线路上加油站的数目。

火柴游戏• 有红，绿，蓝三种颜色的火柴，所有火柴长度一样。

用它们可以组成一些数字， 如下图所示：•• 为了让组成的火柴好看一些，我们规定：有公共点的火柴必须不同色。

例如，用红火柴4根和蓝火柴3根可以组成数12，21，7等。

而且有些方案虽然数字和它们的排列顺序都相同，但是有颜色之分。

问：一共可以组成多少个数（可以包含多个数字，但至少包含一个数字）？同一个数用不同颜色表示算作不同的数，火柴可以有剩余。

• 输入• 三个整数n1， n2， n3 (0 ≤ n1，n2，n3 ≤ 15)，即三种颜色的火柴的数目。

• 输出• 仅一个数，即可以组成的数的数目。

结果保证不超过1016。

骑士游历问题设有一个n*m 的棋盘(2≤n ≤50，2≤m ≤50)，如下图。

在棋盘上任一点有一个中国象棋马，马走的规则为：1.马走日字2.马只能向右走。

即左图所示：当n ，m 给出之后，同时给出马起始的位置和终点的位置，试找出从起点到终点的所有路径的数目。

例如：(n=10，m=10)，(1，5)(起点)，(3，5)(终点)。

应输出2(即由(1，5)到(3，5)共有2条路径，如下图)：输入：n ，m ，x1，y1，x2，y2(分别表示n ，m ，起点坐标，终点坐标) 输出：路径数目(若不存在从起点到终点的路径，输出0)过河卒如图，A点有一个过河卒，需要走到目标B点。

卒行走的规则：可以向下、或者向右。

••同时在棋盘上的任一点有一个对方的马（如上图的C点）,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。

例如上图C点上的马可以控制8个点（图中的P1，P2….P8）。

卒不能通过对方马的控制点。

•棋盘用坐标表示，A点（0，0）、B点（n，m）(n,m为不超过20的整数,并由键盘输入)，同样马的位置坐标是需要给出的（约定：C≠A，同时C≠B）。

现在要求你计算出卒从A点能够到达B点的路径的条数。

•输入：•键盘输入B点的坐标(n,m)以及对方马的坐标（X，Y）输出：•屏幕输出一个整数（路径的条数）。

回溯法习题汇总1.1 马拦过河卒源程序名knight.???（pas, c, cpp）可执行文件名knight.exe输入文件名knight.in输出文件名knight.out【问题描述】棋盘上A点有一个过河卒，需要走到目标B点。

卒行走的规则：可以向下、或者向右。

同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。

因此称之为“马拦过河卒”。

棋盘用坐标表示，A点(0, 0)、B点(n, m)(n, m为不超过15的整数)，同样马的位置坐标是需要给出的。

现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

【输入】一行四个数据，分别表示B点坐标和马的坐标。

【输出】一个数据，表示所有的路径条数。

【样例】knight.in knight.out6 6 3 3 6【算法分析】从起点开始往下走(只有两个方向可以走)，如果某个方向可以走再继续下一步，直到终点，此时计数。

最后输出所有的路径数。

这种方法可以找出所有可能走法，如果要输出这些走法的话这种方法最合适了，但是本题只要求输出总的路径的条数，当棋盘比较大时，本程序执行会超时，此时最好能找出相应的递推公式更合适，详见后面的递推章节。

1.2 出栈序列统计源程序名stack1.???（pas, c, cpp）可执行文件名stack1.exe输入文件名stack1.in输出文件名stack1.out【问题描述】栈是常用的一种数据结构，有n令元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。

你已经知道栈的操作有两·种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。

现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。

请你编程求出对于给定的n，计算并输出由操作数序列1，2，…，n，经过一系列操作可能得到的输出序列总数。

【输入】一个整数n（1<=n<=15）【输出】一个整数，即可能输出序列的总数目。

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!)。

回溯算法---解决批处理作业调度问题1、问题的描述n个作业{1, 2, …, n}要在两台机器上处理，每个作业必须先由机器1处理，然后再由机器2处理，机器1处理作业i所需时间为ai，机器2处理作业i 所需时间为bi（1≤i≤n），批处理作业调度问题要求确定这n个作业的最优处理顺序，使得从第1个作业在机器1上处理开始，到最后一个作业在机器2上处理结束所需时间最少。

利用回溯法解决批作业最优调度问题。

算法思想：对于有n个不同的任务，搜索出其最佳排列，属于一棵排列树搜索问题。

采用回溯法，搜索到第t层时，当已经是叶子节点时，说明该路径就是当前情况下的最优解。

当t不是叶子节点时，依次按照一定的顺序执行当前剩下的任务，将剩下的任务全部遍历一遍。

计算执行当前任务后，各个时间点的变化。

如果该层某个节点的任务执行之后，依然符合剪枝函数，则将当前的策略顺序做出调整，将刚刚执行的那个节点的任务序号放置到当前，然后继续向下进行搜索。

剪枝函数：当当前节点的总时间已经大于已找到的最优时间，则该节点后面的节点都不用进行搜索。

直接回溯。

2、代码及注释#include <iostream>using namespace std;#define MAX 1111111111//宏定义设置一个在适当范围内足够大的数字，方便以后进行比较//定义全局变量，包含如下int* 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];//得到一个新的作业调度方案。

N皇后问题—回溯算法经典例题题⽬描述: N 皇后是回溯算法经典问题之⼀。

问题如下：请在⼀个 n×n 的正⽅形盘⾯上布置 n 名皇后，因为每⼀名皇后都可以⾃上下左右斜⽅向攻击，所以需保证每⼀⾏、每⼀列和每⼀条斜线上都只有⼀名皇后。

题⽬分析： 在 N 皇后问题中，回溯算法思路是每⼀次只布置⼀个皇后，如果盘⾯可⾏，就继续布置下⼀个皇后。

⼀旦盘⾯陷⼊死局，就返回⼀步，调整上⼀个皇后的位置。

重复以上步骤，如果解存在，我们⼀定能够找到它。

可以看到，我们在重复“前进—后退—前进—后退”这⼀过程。

问题是，我们不知道⼀共需要重复这个过程多少次，也不能提前知道 n 是多少，更不知道每⼀次后退时需要后退⼏⾏，因此我们不能利⽤ for 循环和 while 循环来实现这个算法。

因此我们需要利⽤递归来实现代码结构。

逻辑如下：当⽅法布置完当前⾏的皇后，就让⽅法调⽤⾃⼰去布置下⼀⾏的皇后。

当盘⾯变成绝境的时候，就从当前⽅法跳出来，返回到上⼀⾏，换掉上⼀⾏的皇后再继续。

我们定义 NQueens(n) ⽅法，它负责输出所有成⽴的 n×n 盘⾯。

其中 1 代表皇后，0 代表空格。

代码：def NQueens(n): #输出所有成⽴的n·n盘⾯cols = [0 for _ in range(n)] #每⼀⾏皇后的纵坐标res = [] #结果列表def checkBoard(rowIndex): #检查盘⾯是否成⽴,rowIndex是当前⾏数for i in range(rowIndex):if cols[i]==cols[rowIndex]: #检查竖线return Falseif abs(cols[i]-cols[rowIndex]) == rowIndex-i: #检查斜线return Falsereturn Truedef helper(rowIndex): #布置第rowIndex⾏到最后⼀⾏的皇后if rowIndex==n: #边界条件board = [[0 for _ in range(n)] for _ in range(n)]for i in range(n):board[i][cols[i]] = 1res.append(board) #把当前盘⾯加⼊结果列表return#返回for i in range(n): #依次尝试当前⾏的空格cols[rowIndex] = iif checkBoard(rowIndex): #检查当前盘⾯helper(rowIndex+1) #进⼊下⼀⾏helper(0) #从第1⾏开始return resprint(NQueens(4))代码分析： 在 NQueens() ⽅法中，我们会定义 helper(x) ⽅法帮助实现递归结构。

算法分析与设计实验报告第五次附加实验cp += p[i];Backtrack(i+1); //回溯//回溯结束回到当前根结点cw -= w[i];cp -= p[i];}//进入右子树，条件是上界值比当前最优值大，否则就将右子树剪掉if(Bound(i+1)>bestp){Backtrack(i+1);}}测试结果当输入的数据有解时：当输入的数据无解时：当输入的数据稍微大点时：附录：完整代码（回溯法）//0-1背包问题 回溯法求解 #include <iostream> using namespace std;template <class Typew,class Typep>class Knap //Knap 类记录解空间树的结点信息 {template <class Typew,class Typep>friend Typep Knapsack(Typep [],Typew [],Typew,int ); private :Typep Bound(int i); //计算上界的函数void Backtrack(int i); //回溯求最优解函数实验分析在实验中并没有生成多组数据，进行比较，也没有利用随机生成函数，因为在这种有实际有关联的问题中，利用随机生成函数生成的数据是十分的不合适的，在此我们只需要验证该程序是否正确即可。

0-1背包问题和之前的最优装载其实质上一样的，都是利用解空间树，通过深度优先搜索子集树，通过利用上界函数和一些剪枝策略，从而得到最优解。

由于数据较小，所以时间上并不能反映出什么东西。

实验心得在这一章的回溯算法中，我们用的比较多的就是；利用子集树来进行问题的探索，就例如上图是典型的一种子集树，在最优装载、0-1背包都是利用了这种满二叉树的子集树进行求解，然后通过深度优先的策略，利用约束函数和上界函数，将一些不符合条件或者不包含最优解的分支减掉，从而提高程序的效率。

回溯法一、算法介绍：回溯是一种模拟人类思维过程的算法思想。

它的基本方法是：按照深度优先的顺序向下一层扩展结点；扩展到某一层时，若已无法继续扩展且仍未找到解，则退回到父结点，从父结点的下一个分支开始，按同样的策略继续扩展……，直到找到问题的解或证明无解。

代码框架：procedure try(i:integer);varbeginif i>nthen 输出结果else for j:=下界to 上界dobeginx[i]:=h[j];if 可行{满足限界函数和约束条件} thenbegin置值；try(i+1);{尝试下一个位置}对此位置还原；end;end;end;二、典型例题：1、n皇后：在一个n×n国际象棋盘上，有n个皇后，每个皇后占一格；要求皇后间不会出现相互“攻击”的现象，即不能有两个皇后处在同一行、同一列或同一对角线上。

问共有多少种不同的方法。

【思路】逐一对每行的n个位置进行尝试（横坐标记为i，纵坐标记为j）。

若此位置安全则占用，并表明此位置所在的两对角线、列不安全（由于是对每行进行尝试，故不需标注该行是否安全）。

若此位置不安全则尝试下一个位置。

找到本行的安全位置后，如果已经尝试n行则输出结果，否则对下一行进行同样的尝试。

无论是继续尝试还是输出结果，在进行操作后都要对所占位置进行释放（即返回，进行本行下一位置的尝试）。

【注】棋盘中，从左至右的对角线横纵坐标之和一定（如图），从右至左的对角线横纵坐标之差一定。

varn,i:longint;no:longint;{记录方案个数}ans:array[1..1000]of longint;｛储存答案｝ lr,rl,l:array[-1000..1000] of boolean; {储存左右对角线、右左对角线、列是否安全}procedure print; {输出答案}vari:longint;beginno:=no+1;write('NO.',no,':');for i:=1 to n do write(ans[i],' '); writeln;end;procedure try(j:longint);vari:longint;beginfor i:=1 to n doif l[i] and rl[i+j] and lr[j-i]thenbeginl[i]:=false;rl[i+j]:=false;lr[j-i]:=false;ans[j]:=i;if j<n then try(j+1)else print;l[i]:=true;{释放该位置}rl[i+j]:=true;lr[j-i]:=true;end;end;beginwriteln('How many queens?');read(n);no:=0;for i:=1 to n do l[i]:=true;for i:=2 to 2*n do rl[i]:=true;for i:=1-n to n-1 do lr[i]:=true;try(1);if no=0 then write('No way!');end.2、跳马：在5*5格的棋盘上，从（1,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 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!) 。

回溯法习题汇总1.1 马拦过河卒源程序名knight.???（pas, c, cpp）可执行文件名knight.exe输入文件名knight.in输出文件名knight.out【问题描述】棋盘上A点有一个过河卒，需要走到目标B点。

卒行走的规则：可以向下、或者向右。

同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。

因此称之为“马拦过河卒”。

棋盘用坐标表示，A点(0, 0)、B点(n, m)(n, m为不超过15的整数)，同样马的位置坐标是需要给出的。

现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

【输入】一行四个数据，分别表示B点坐标和马的坐标。

【输出】一个数据，表示所有的路径条数。

【样例】knight.in knight.out6 6 3 3 6【算法分析】从起点开始往下走(只有两个方向可以走)，如果某个方向可以走再继续下一步，直到终点，此时计数。

最后输出所有的路径数。

这种方法可以找出所有可能走法，如果要输出这些走法的话这种方法最合适了，但是本题只要求输出总的路径的条数，当棋盘比较大时，本程序执行会超时，此时最好能找出相应的递推公式更合适，详见后面的递推章节。

1.2 出栈序列统计源程序名stack1.???（pas, c, cpp）可执行文件名stack1.exe输入文件名stack1.in输出文件名stack1.out【问题描述】栈是常用的一种数据结构，有n令元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。

你已经知道栈的操作有两·种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。

现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。

请你编程求出对于给定的n，计算并输出由操作数序列1，2，…，n，经过一系列操作可能得到的输出序列总数。

【输入】一个整数n（1<=n<=15）【输出】一个整数，即可能输出序列的总数目。