当前位置：文档之家 › 算法习题回溯法

算法习题回溯法

  • 格式：doc
  • 大小：34.50 KB
  • 文档页数：3

下载文档原格式

  / 3

合集下载

回溯法和分支限界法解决0-1背包题(精)[精品文档]

回溯法和分支限界法解决0-1背包题(精)[精品文档]

0-1背包问题计科1班朱润华 2012040732方法1：回溯法一、回溯法描述：用回溯法解问题时，应明确定义问题的解空间。

问题的解空间至少包含问题的一个（最优）解。

对于0-1背包问题，解空间由长度为n的0-1向量组成。

该解空间包含对变量的所有0-1赋值。

例如n=3时，解空间为：｛（0，0，0），（0，1，0），（0，0，1），（1，0，0），（0，1，1），（1，0，1），（1，1，0），（1，1，1）｝然后可将解空间组织成树或图的形式，0-1背包则可用完全二叉树表示其解空间给定n种物品和一背包。

物品i的重量是wi，其价值为vi，背包的容量为C。

问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大?形式化描述：给定c >0, wi >0, vi >0 , 1≤i≤n.要求找一n元向量(x1,x2,…,xn,),xi∈{0,1}, ? ∑ wi xi≤c,且∑ vi xi达最大.即一个特殊的整数规划问题。

二、回溯法步骤思想描述：0-1背包问题是子集选取问题。

0-1 背包问题的解空间可以用子集树表示。

在搜索解空间树时，只要其左儿子节点是一个可行节点，搜索就进入左子树。

当右子树中有可能含有最优解时，才进入右子树搜索。

否则，将右子树剪去。

设r是当前剩余物品价值总和，cp是当前价值；bestp是当前最优价值。

当cp+r<=bestp时，可剪去右子树。

计算右子树上界的更好的方法是将剩余物品依次按其单位价值排序，然后依次装入物品，直至装不下时，再装入物品一部分而装满背包。

例如：对于0-1背包问题的一个实例，n=4,c=7,p=[9,10,7,4],w=[3,5,2,1]。

这4个物品的单位重量价值分别为[3,2,3,5,4]。

以物品单位重量价值的递减序装入物品。

先装入物品4，然后装入物品3和1.装入这3个物品后，剩余的背包容量为1，只能装0.2的物品2。

由此得一个解为[1,0.2,1,1]，其相应价值为22。

算法设计与分析——批处理作业调度（回溯法）

算法设计与分析——批处理作业调度（回溯法）

算法设计与分析——批处理作业调度（回溯法）之前讲过⼀个相似的问题流⽔作业调度问题，那⼀道题最开始⽤动态规划，推到最后得到了⼀个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

回溯法练习1

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

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

例如，用红火柴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）输出：•屏幕输出一个整数（路径的条数）。

基本算法-回溯法（迷宫问题）

基本算法-回溯法（迷宫问题）

基本算法-回溯法（迷宫问题）作者：翟天保Steven版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处前言本文介绍一种经典算法——回溯法，可作为迷宫问题的一种解法，以下是本篇文章正文内容，包括算法简介、算法应用（迷宫问题）、算法流程和C++代码实现。

一、回溯法简介回溯法（Backtracking）是枚举法的一种，可以找出所有或者一部分的一般性算法，且有效避免枚举不对的解。

当发现某个解的方向不准确时，就不再继续往下进行，而是回溯到上一层，减少算法运行时间，俗称“走不通就回头换路走”。

特点是在搜索过程中寻找问题的解，一旦发现不满足条件便回溯，继续搜索其他路径，提高效率。

二、算法应用（迷宫问题）1.问题描述迷宫问题是回溯法的一种应用。

迷宫问题的描述为：假设主体（人、动物或者飞行器）放在一个迷宫地图入口处，迷宫中有许多墙，使得大多数的路径都被挡住而无法行进。

主体可以通过遍历所有可能到出口的路径来到达出口。

当主体走错路时需要将走错的路径记录下来，避免下次走重复的路径，直到找到出口。

主体需遵从如下三个原则：1.一次步进只能走一格；2.遇到路径堵塞后，退后直到找到另一条路径可行；3.走过的路径记录下来，不会再走第二次。

2.解题思路首先创建一个迷宫图，比如用二维数组人为定义MAZE[row][col]，MAZE[i][j]=1时表示有墙无法通过，MAZE[i][j]=0时表示可行，假设MAZE[1][1]为入口，MAZE[8][10]为出口，创建如下初始迷宫图：图1 初始迷宫图当主体在迷宫中前行时，有东南西北（即右下左上）四个方向可以选择，如下图所示：图2 方向示意图视情况而定，并不是所有位置都可以上下左右前进，只能走MAZE[i][j]=0的地方。

通过链表来记录走过的位置，并将其标记为2，把这个位置的信息放入堆栈，再进行下个方向的选择。

若走到死胡同且未到达终点，则退回到上一个岔路口选择另一个方向继续走。

算法习题回溯法

算法习题回溯法
x[j] = 0;
}
}
main(){
ifstream fin("input.txt",ios::in);
fin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
fin>>c[i][j];
x[j] = 0;
}
cost+=c[i][i];
}
work(1,0);
void backtrack(int i){
if(i>n){
if(cw<sum)
sum = cw;
return ;
}
for(int j=1;j<=m;j++){
cw+=w[i][j];
cp+=c[i][j];
if(cw<sum && cp<=d)
backtrack(i+1);
cw-=w[i][j];
ofstream fout("output.txt",ios::out);
cout<<cost<<endl;
fout<<cost<<endl;
system("pause");
fout.close();
return 0;
}
cp-=c[i][j];
}
}
int main(){
ifstream fin("input.txt",ios::in);
fin>>n>>m>>d;

第5章 回溯法(1-例子)

第5章 回溯法(1-例子)

n; // 作业数};
8
} //end Backtrack
旅行售货员问题
9
旅行售货员问题
解空间树 —— 排列树 剪枝函数：当搜索到第i 层，图G中存在从顶点1经i个 顶点到某其他顶点的一条路 径，且x[1:i]的费用和大于当前 已获得的最优值时，剪去该子 树的搜索。 算法效率：
O((n-1)!)*O(n) =O(n!)
cleft -= w[i];
b += p[i];
i++;
} // 装满背包
if (i <= n) b += p[i]/w[i] * cleft;
return b;
4
}
0-1背包问题
例：n=4，c=7，p=[9，10，7，4]，w=[3，5，2，1] 解空间树如下：
物品 1 物品 2 物品 3 物品 4
class Flowshop { friend Flow(int**, int, int []);
f+=f2[i];
private:
if (f < bestf) {
void Backtrack(int i);
Swap(x[i], x[j]);
int **M, // 各作业所需的处理时间
Backtrack(i+1);
(2)将剩余的集装箱装上第二艘轮船。
将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，
使该子集中集装箱重量之和最接近c1。由此可知，装载问题等
价于以下特n殊的0-1背包问题。
max wi xi i 1
用回溯法设计解装载问题的O(2n)计
n
s.t. wi xi c1
算时间算法。

回溯法

回溯法一、回溯法：回溯法是一个既带有系统性又带有跳跃性的的搜索算法。

它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。

算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。

如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。

否则，进入该子树，继续按深度优先的策略进行搜索。

回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。

而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。

这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。

二、算法框架：1、问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。

问题的解空间应到少包含问题的一个（最优）解。

2、回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。

这个开始结点就成为一个活结点，同时也成为当前的扩展结点。

在当前的扩展结点处，搜索向纵深方向移至一个新结点。

这个新结点就成为一个新的活结点，并成为当前扩展结点。

如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。

换句话说，这个结点不再是一个活结点。

此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。

回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。

运用回溯法解题通常包含以下三个步骤：（1）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间结构；（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；3、递归回溯：由于回溯法是对解空间的深度优先搜索，因此在一般情况下可用递归函数来实现回溯法如下：procedure try(i:integer);varbeginif i>n then 输出结果else for j:=下界 to 上界 dobeginx[i]:=h[j];if 可行{满足限界函数和约束条件} then begin 置值；try(i+1); end;end;end;说明：i 是递归深度；n 是深度控制，即解空间树的的高度；可行性判断有两方面的内容：不满约束条件则剪去相应子树；若限界函数越界，也剪去相应子树；两者均满足则进入下一层；二、习题：1、0-1背包：n=3,w=[16,15,15],p=[45,25,25],c=302、旅行售货员问题：某售货员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。

《算法设计与分析》课程实验报告 (回溯法(二))

《算法设计与分析》课程实验报告实验序号：10实验项目名称：实验十一回溯法（二）一、实验题目1.图的着色问题问题描述：给定无向连通图G和m种不同的颜色。

用这些颜色为图G的各顶点着色，每个顶点着一种颜色。

如果有一种着色法使G中每条边的2个顶点着不同颜色，则称这个图是m可着色的。

图的m着色问题是对于给定图G和m种颜色，找出所有不同的着色法。

2.旅行商问题问题描述：给出一个n个顶点的带权无向图，请寻找一条从顶点1出发，遍历其余顶点一次且仅一次、最后回到顶点1的最小成本的回路——即最短Hamilton回路。

3.拔河比赛问题描述：某公司的野餐会上将举行一次拔河比赛。

他们想把参与者们尽可能分为实力相当的两支队伍。

每个人都必须在其中一只队伍里，两队的人数差距不能超过一人，且两队的队员总体重应该尽量接近。

4.批处理作业调度问题描述：给定n个作业的集合J=(J1,J2, .. Jn)。

每个作业J都有两项任务分别在两台机器上完成。

每个作业必须先由机器1处理，再由机器2处理。

作业i需要机器j的处理时间为tji(i=1,2, ..n; j=1,2)。

对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间，则所有作业在机器2上完成处理的时间和，称为该作业调度的完成时间和。

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

二、实验目的（1）通过练习，理解回溯法求解问题的解状态空间树与程序表达的对应关系，熟练掌握排列树、子集树的代码实现。

（2）通过练习，体会减少搜索解空间中节点的方法，体会解的状态空间树的组织及上界函数的选取对搜索的影响。

（3）通过练习，深入理解具体问题中提高回溯算法效率的方法。

（4）（选做题）：在掌握回溯法的基本框架后，重点体会具体问题中解的状态空间搜索时的剪枝问题。

三、实验要求（1）每题都必须实现算法、设计测试数据、记录实验结果，并给出时间复杂度分析。

四、实验过程（算法设计思想、源码）1.图的着色问题(1)算法设计思想用邻接矩阵a[i][j]存储无向图，对于每一个顶点有m种颜色可以涂。

回溯法作业

回溯法作业答案1. 旅行商问题（作业实验)设有n个城市，城市之间道路的长度均大于或等于0，还可能是∞（对应城市之间无交通线路）。

一个旅行商从某个城市出发，要经过每个城市一次且仅一次，最后回到出发的城市，问他如何走才能使他走的路线最短？分析：旅行商问题对应的解的元组为n元组，其中假设第一个城市为1，则n元组中未确定的为剩下n-1个城市，元组为（1,x2,…,x n）,每个x i的取值为{2,…,n}；约束条件为已经经过的城市不能再走，最后回到出发城市。

算法：INPUT: n个城市分别为{1，2，…n},城市之间路径长度的矩阵d[i][j] 。

OUTPUT: 从城市1出发的最短巡回旅行路线及长度。

1. for k =1 to n2. c[k] =13. end for4. k =2,L=0,MinL=∞5. while k≥26. while c[k]≤n-17. c[k] =c[k]+18. L=L+d[c[k-1]][c[k]]9. if c为合法的thenMinL=min{MinL,L}, p[]=c[]10. else if c是部分解then11. if L>=MinL then continue12. else k =k+113. endif14. endif15. end while16. L=L-d[c[k-1]][c[k]]17. c[k] =118. k =k-119. end while20. output MinL, p[]2. 邮票问题(作业实验选做)设有已知面额的邮票m种（假设一定有面值为1的邮票；如果没有，连续值就从最小面额的邮票面额值开始），每种有n张，问用总数不超过n张的邮票进行组合，能组合的邮票面额中可以连续的面额数最多有多少？例如：n=4 m=3v1=1 v2=2 v3=4最后的解为14。

分析：第一种思路：邮票问题是从m种邮票中选择n张邮票，求所有可能取得的面额，最后在确定最大连续面额的值。

第五组回溯算法（硬币分配问题）

第五组回溯算法（硬币分配问题）实训⼀硬币分法问题的回溯算法与实现⼀、设计⽬的1）掌握硬币分法问题的回溯算法；2）进⼀步掌握回溯算法的基本思想和算法设计⽅法；⼆、设计内容1．任务描述1）算法简介回溯算法也叫试探法，它是⼀种系统地搜索问题的解的⽅法。

回溯算法的基本思想是：从⼀条路往前⾛，能进则进，不能进则退回来，换⼀条路再试。

⼋皇后问题就是回溯算法的典型，第⼀步按照顺序放⼀个皇后，然后第⼆步符合要求放第2个皇后，如果没有符合位置符合要求，那么就要改变第⼀个皇后的位置，重新放第2个皇后的位置，直到找到符合条件的位置就可以了回溯在迷宫搜索中使⽤很常见，就是这条路⾛不通，然后返回前⼀个路⼝，继续下⼀条路。

回溯算法说⽩了就是穷举法。

不过回溯算法使⽤剪枝函数，剪去⼀些不可能到达最终状态（即答案状态）的节点，从⽽减少状态空间树节点的⽣成。

回溯法是⼀个既带有系统性⼜带有跳跃性的的搜索算法。

它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。

算法搜索⾄解空间树的任⼀结点时，总是先判断该结点是否肯定不包含问题的解。

如果肯定不包含，则跳过对以该结点为根的⼦树的系统搜索，逐层向其祖先结点回溯。

否则，进⼊该⼦树，继续按深度优先的策略进⾏搜索。

回溯法在⽤来求问题的所有解时，要回溯到根，且根结点的所有⼦树都已被搜索遍才结束。

⽽回溯法在⽤来求问题的任⼀解时，只要搜索到问题的⼀个解就可以结束。

这种以深度优先的⽅式系统地搜索问题的解的算法称为回溯法，它适⽤于解⼀些组合数较⼤的问题。

2）硬币分法问题简介假设有5种硬币：50美分，25美分，10美分，5美分和1美分。

我们给⼀定数量的资⾦，要求这些硬币作出变化。

例如，如果我们有11美分，那么我们可以给出⼀个10美分的硬币和⼀个1美分硬币，或者2个 5美分的硬币和⼀个1美分硬币，或者⼀个5美分硬币和6个 1美分的硬币，或11个1美分硬币。

因此，有四个使上述11美分硬币的变化⽅式。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
fout<<cost<<endl;
system("pause");
fout.close();
return 0;
}
cw+=w[i][j];
cp+=c[i][j];
if(cw<sum && cp<=d)
backtrack(i+1);
cw-=w[i][j];
cp-=c[i][j];
}
}
int main(){
ifstream fin("input.txt",ios::in);
fin>>n>>m>>d;
for(int i=1;i<=n;i++){
Output
将计算的最小重量及每个部件的供应商输出到文件output.txt
Sample Input
3 3 41 2 33 2 12 2 21 2 33 2 12 2 2
Sample Output
4
1 3 1
#include<iostream>
#include<fstream>
#include <stdio.h>
3 4 5
输出：9
#include<iostream>
#include<fstream>
#include <stdio.h>
using namespace std;
int n,cost=0;
int x[100],c[100][100];
void work(int i,int count){
if(i>n && count<cost){
算法设计与分析第三次作业
计科三班康玥20110801330
5-3
设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设wi,j是从供应商j处购得的部件i的重量，ci,j是相应的价格。试设计一个算法，给出总价格不超过c的最小重量机器设计。
Input
由文件input.txt给出输入数据。每组测试数据第一行有3个正整数n，m和d。接下来的2n行，每行m个数。前n行是ci,j，后n行是wi,j。
cost = count;
return ;
}
if(count<cost)
for(int j=1;j<=n;j++)
if(x[j] == 0){
x[j] = 1;
work(i+1,count+c[i][j]);
x[j] = 0;
}
}
int main(){
ifst;
算法设计：设计一个算法，对于给定的工作费用，计算最佳工作分配方案，使总费用达到最小。
数据输入：由文件input.txt给出输入数据，第一行有一个正整数n（1<=n<=20）。接下来的n行，每行n个数，表示工作费用。
结果输出：将计算的最小总费用输出到文件output.txt
样例分析：
3
10 2 3
2 3 4
for(int j=1;j<=m;j++)
fin>>c[i][j];
sum+=c[i][1];
}
for(int k=1;k<=n;k++)
for(int j=1;j<=m;j++)
fin>>w[k][j];
backtrack(1);
ofstream fout("output.txt",ios::out);
cout<<sum<<endl;
fout<<sum<<endl;
system("pause"); fout.close();
return 0;
}
5-13
问题描述：
设有n件工作分配给n个人。为第i个人分配工作j所需的费用为c[i][j]。试设计一个算法，计算最佳工作分配方案，为每一个人都分配1件不同的工作，并使总费用达到最小。
fin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
fin>>c[i][j];
x[j] = 0;
}
cost+=c[i][i];
}
work(1,0);
ofstream fout("output.txt",ios::out);
cout<<cost<<endl;
#define N 1000
using namespace std;
int n,m,d,cp=0,cw=0,sum=0;
int c[N][N],w[N][N];
void backtrack(int i){
if(i>n){
if(cw<sum)
sum = cw;
return ;
}
for(int j=1;j<=m;j++){