当前位置：文档之家 › 第5章-回溯法-习题

第5章-回溯法-习题

  • 格式：ppt
  • 大小：286.00 KB
  • 文档页数：24

下载文档原格式

  / 24

合集下载

第5章 回溯法

第5章 回溯法
第5章
教学要求

回溯
了解回溯算法的概念与回溯设计要领 掌握应用回溯算法求解桥本分数式、素数环、 数码串珠以及情侣拍照等典型案例
本章重点

理解回溯法 “向前走，碰壁回头”的实现
5.1 回溯概述

1. 回溯的概念
(1) 回溯法（Back track method）有“通用解题法”之美 称，是一种比枚举“聪明”的效率更高的搜索技术。

4. 4皇后问题的回溯举例
如何在4×4的方格棋盘上放置4个皇后，使它们互不攻击:

4皇后问题回溯描述
i=1;a[i]=1; while


(1) { g=1;for(k=i-1;k>=1;k--) if(a[i]=a[k] || abs(a[i]-a[k])=i-k) g=0; // 检测约束条件,不满足则返回 if(g && i==4) printf(a[1：4]); // 输出一个解 if(i<4 && g) {i++;a[i]=1;continue;} while(a[i]==4 && i>1) i--; // 向前回溯 if(a[i]==4 && i==1) break; //退出循环结束探索 else a[i]=a[i]+1; }
（2） 回溯描述 对于一般含参量m,n的搜索问题,输入正整数n,m,(n≥m) i=1;a[i]=<元素初值>; while (1) {for(g=1,k=i-1;k>=1;k--) if( <约束条件1> ) g=0; // 检测约束条件,不满足则返回 if(g && <约束条件2>) printf(a[1：m]); // 输出解 if(i<n && g) {i++;a[i]=<取值点>;continue;} while(a[i]=<回溯点> && i>1) i--; // 向前回溯 if(a[i]==n && i==1) break; // 退出循环，结束 else a[i]=a[i]+1; }

第5章 回溯法2

第5章 回溯法2
1 2 3 4 5 1 2 3
4
5
U是G的最大团当且仅当U是G的最大独立集。 的最大团当且仅当U 的最大独立集。
void Clique::Backtrack(int i) {// 计算最大团 if (i > n) {// 到达叶结点 for (int j = 1; j <= n; j++) bestx[j] = x[j]; bestn = cn; return;} // 检查顶点 i 与当前团的连接 int OK = 1; for (int j = 1; j < i; j++) if (x[j] && a[i][j] == 0) { // i与j不相连 与 不相连 OK = 0; break;} if (OK) {// 进入左子树 x[i] = 1; cn++; Backtrack(i+1); x[i] = 0; cn--;} if (cn + n - i > bestn) {// 进入右子树 x[i] = 0; Backtrack(i+1);} }
n后问题程序源代码 后问题程序源代码
#include<stdlib.h> #include<iostream.h> class Queen { friend int nQueen(int); private: bool Place(int k); void Backtrack(int t); int n;//皇后个数 n;//皇后个数 int *x;//当前解 *x;//当前解 long sum;//当前已找到的可行方案数 sum;//当前已找到的可行方案数 }; bool Queen::Place(int k) { for(int j=1;j<k;j++) if((abs(k-j)==abs(x[j]if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])) return false; return true; }

python回溯法例题

python回溯法例题

python回溯法例题回溯法是一种常用的算法思想，用于解决各种组合优化问题，尤其在解决NP完全问题方面有着广泛的应用。

本文将通过一个具体的例题来介绍和解释python回溯法的实现过程。

任务名称：python回溯法例题问题描述：给定一个由不同整数组成的数组nums，编写一个函数，返回所有可能的排列组合。

解题思路：要解决这个问题，我们可以使用回溯法来生成所有可能的排列组合。

回溯法是一种通过试错的方式搜索解空间的算法。

具体来说，我们从问题的一个初始解开始，通过一系列的决策，逐步构建问题的解，如果在构建的过程中发现当前的解不符合要求，我们就回溯到上一个状态，重新进行决策。

在本例中，我们可以使用一个递归函数来实现回溯法。

我们定义一个辅助函数backtrack，它接受一个当前的排列，一个用于标记数字是否被使用的数组，以及一个用于存储所有解的结果数组。

在函数中，我们首先检查当前的排列是否已经包含了所有的数字，如果是的话，我们将当前的排列添加到结果数组中。

然后，我们遍历所有的数字，对于每一个数字，如果它没有被使用过，我们将其添加到当前的排列中，然后递归调用backtrack函数，继续构建下一个数字。

最后，我们将当前的数字从排列中移除，以便进行下一次决策。

下面是具体的代码实现：```pythondef permute(nums):def backtrack(curr_perm, used, result):if len(curr_perm) == len(nums):result.append(curr_perm[:])else:for i in range(len(nums)):if not used[i]:curr_perm.append(nums[i])used[i] = Truebacktrack(curr_perm, used, result)used[i] = Falsecurr_perm.pop()result = []used = [False] * len(nums)backtrack([], used, result)return result```我们可以使用这个函数来解决给定数组的排列组合问题。

回溯法习题汇总

回溯法习题汇总

回溯法习题汇总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）【输出】一个整数，即可能输出序列的总数目。

第5章-回溯法-习题

第5章-回溯法-习题
9
运动员最佳匹配问题
编程任务：
设计一个算法，对于给定的男女运动员竞赛优势，计算男女运 动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。
数据输入：
第一行有1 个正整数n (1≤n≤20)。接下来的2n 行，每行n 个数。 前n 行是p，后n 行是q。
结果输出: 男女双方竞赛优势的总和的最大值。输入示例：
}
//第lev位
//lev的前k位坐标x[0]~x[k-1] //下标必须大于0 //是相同的
//每隔i个位置
23
5-30 离散01串问题
//判断是否相同
bool same() {
int len = x[0] - x[1];
//计算位置差
for (int i=0; i<len; i++)
//搜索每一位
只有一个下标是变化的
11
运动员最佳匹配问题算法
解空间是一棵排列树 void pref::Backtrack(int t) {
if (t>n) Compute(); else
for (int j=t; j<=n; j++) { swap(r[t], r[j]); Backtrack(t+1); swap(r[t], r[j]);
课程安排
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 周二 P P T T P T T P T T P T T T T P
周四 P
P
P
P
P
P
P
P
P
P
P
P
P
P
端午
考试 T
1
第5章 回溯法习题课

第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 章——概论1.下列关于算法的说法中正确的有（）。

Ⅰ.求解某一类问题的算法是唯一的Ⅱ.算法必须在有限步操作之后停止Ⅲ.算法的每一步操作必须是明确的，不能有歧义或含义模糊Ⅳ.算法执行后一定产生确定的结果A.1个B.2个C.3个D.4个2.T(n)表示当输入规模为n时的算法效率，以下算法效率最优的是（）。

A.T(n)=T(n-1)+1，T(1)=1B.T(n)=2nC.T(n)= T(n/2)+1，T(1)=1D.T(n)=3nlog2n答案解析：1.答：由于算法具有有穷性、确定性和输出性，因而Ⅱ、Ⅲ、Ⅳ正确，而解决某一类问题的算法不一定是唯一的。

答案为C。

2.答：选项A的时间复杂度为O(n)。

选项B的时间复杂度为O(n)。

选项C 的时间复杂度为O(log2n)。

选项D的时间复杂度为O(nlog2n)。

答案为C。

第3 章─分治法1.分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。

这要求原问题和子问题（）。

A.问题规模相同，问题性质相同B.问题规模相同，问题性质不同C.问题规模不同，问题性质相同D.问题规模不同，问题性质不同2.在寻找n个元素中第k小元素问题中，如快速排序算法思想，运用分治算法对n个元素进行划分，如何选择划分基准？下面（）答案解释最合理。

A.随机选择一个元素作为划分基准B.取子序列的第一个元素作为划分基准C.用中位数的中位数方法寻找划分基准D.以上皆可行。

但不同方法，算法复杂度上界可能不同3.对于下列二分查找算法，以下正确的是（）。

A.intbinarySearch(inta[],intn,int x){intlow=0,high=n-1;while(low<=high){intmid=(low+high)/2;if(x==a[mid])returnmid;if(x>a[mid])low=mid;elsehigh=mid;}return –1;}B.intbinarySearch(inta[],intn,int x) { intlow=0,high=n-1;while(low+1!=high){intmid=(low+high)/2;if(x>=a[mid])low=mid;elsehigh=mid;}if(x==a[low])returnlow;elsereturn –1;}C.intbinarySearch(inta[],intn,intx) { intlow=0,high=n-1;while(low<high-1){intmid=(low+high)/2;if(x<a[mid])high=mid;elselow=mid;}if(x==a[low])returnlow;elsereturn –1;}D.intbinarySearch(inta[],intn,int x) {if(n>0&&x>=a[0]){intlow= 0,high=n-1;while(low<high){intmid=(low+high+1)/2;if(x<a[mid])high=mid-1;elselow=mid;}if(x==a[low])returnlow;}return –1;}答案解析：1.答：C。

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


{ if ((count>half)||(t*(t-1)/2-count>half)) return; if (t>n) sum++;
-++-+ -
else for (int i=0;i<2;i++) { p[1][t]=i;
-+
count+=i;
for (int j=2;j<=t;j++) { p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2]; count+=p[j][t-j+1];
对n=4, 四后问题的两个布局
无效布局
有效布局
14
对n=5, 五后问题
……
15
对n=8, 八后问题有92个解之多
1
Q
2
Q
3
Q
4
Q
5
Q
6Q
7
Q
8
Q
1 2345678
1
Q
2
Q
3
Q
4
Q
5
Q
6
Q
7Q
8
Q
1 2345678
16
四后问题的解空间
每行只能放置一个皇后，因此用xi表示第i行皇后 放置在xi列。
void Queen::Backtrack(int t)
{
if (t>n) sum++;
else
for (int i=1;i<=n;i++) {
x[t]=i;
if (Place(t)) Backtrack(t+1);

回溯法作业

回溯法作业答案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张邮票，求所有可能取得的面额，最后在确定最大连续面额的值。

第五章 回溯法


• Cr=C=30，V=0
C为容量，Cr为剩余空间，V为价值。 • A为唯一活结点，也是当前扩展结点。
H D 1 0 I 1
1 B 0 E 1 0 J K
A
0 C 1 F 1 0 L M N 0 G 1 0 O
5.1 回溯法的算法框架
• n=3, C=30, w={16,15,15}, v={45,25,25}
理论上
寻找问题的解的一种可靠的方法是首先列出所有候选解，然后依次检查每一个， 在检查完所有或部分候选解后，即可找到所需要的解。
但是
当候选解数量有限并且通过检查所有或部分候选解能够得到所需解时，上述方
法是可行的。
若候选解的数量非常大（指数级，大数阶乘），即便采用最快的计算机也只能 解决规模很小的问题。
显约束
对分量xi的取值限定。
隐约束 为满足问题的解而对不同分量之间施加的约束。
5.1 回溯法的算法框架
解空间（Solution Space）
对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该 实例的一个解空间。 注意：同一问题可有多种表示，有些表示更简单，所需状态空间更小（存储 量少，搜索方法简单）。
回溯法引言
以深度优先的方式系统地搜索问题的解的算法称为回溯法 使用场合
对于许多问题，当需要找出它的解的集合或者要求回答什么解是满足某些
约束条件的最佳解时，往往要使用回溯法。 这种方法适用于解一些组合数相当大的问题，具有“通用解题法”之称。 回溯法的基本做法 是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。
一个正在产生儿子的结点称为扩展结点
活结点（L-结点,Live Node）
一个自身已生成但其儿子还没有全部生成的节点称做活结点
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
最长处理时间作业优先, 机器空闲时间最长优先安排
18
最佳调度问题算法
void search(int dep) {
//初值为1
if (dep==n) {
//形成一种调度方案
int temp = comp();
//计算完成任务的时间
if (tmp<best) best = tmp; //更新最优解
return;
3
10 2 3
ห้องสมุดไป่ตู้
p 234
345
222
q
353
451
输出示例： 52
10
运动员最佳匹配问题
结果输出: 男女双方竞赛优势的总和的最大值。
样例分析
输出示例： 52
输入示例：
3
10 2 3 p 234
345
222
q
353
451
1 23
r1 3 2
10*2+4*5+4*3=52
for (int i=1,temp=0;i<=n;i++) temp += p[i][r[i]]*q[r[i]][i];
课程安排
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 周二 P P T T P T T P T T P T T T T P
周四 P
P
P
P
P
P
P
P
P
P
P
P
P
P
端午
考试 T
1
第5章 回溯法习题课
第5章 回溯法习题
1. 子集和问题 2. 运动员最佳匹配问题 3. 最佳调度问题 4. 离散01串问题
cw -= w[i];
//准备进入右子树
}
if (cw+r>bestw) {//上界函数
x[i] = 0;
//右子树
if (backtrack(i+1)) return true;
}
r += w[i];
//右子树无最优解
return false;
}
8
5-4 运动员最佳匹配问题
问题描述： 羽毛球队有男女运动员各n 人。
}
}
22
5-30 离散01串问题
bool bstrok(int lev) { for (int i=0; i<k; i++) x[i] = lev-i; while (x[k-1]>0) { if (same()) return false; for (int i=0; i<k; i++) x[i] -= i+1; } return true;
}
//从1开始调用 //计算完毕
//记录最优解
//满足条件(找到了)
7
子集和问题算法
r -= w[i];
//剩余大小
if (cw+w[i]<=c) {
//第i个数可以使用
x[i] = 1;
//左子树
cw += w[i];
//当前和加上w[i]
if (backtrack(i+1)) return true;
int tmp = 0;
//在k台机器中查找最大值
for (int i=0; i<k; i++)
if (len[i]>tmp) tmp = len[i];
return tmp;
}
20
5-30 离散01串问题
(n,k)01 串定义为：长度为n 的01 串，其中不含k 个连 续的相同子串。对于给定的正整数n 和k，计算(n,k)01 串的个数。
for (int j=1; j<k; j++)
//每次搜索k位
if (bstr[x[j]+i]!=bstr[x[j-1]+i]) //相邻位
return false;
//只要有一个不相同即可
return true;
//相同
}
24
5-30 离散01串问题
文件头： #include <iostream> using namespace std;
int n, k; int tot; short *bstr; int *x;
bool bstrok(int lev); bool same();
25
4
5-1 子集和问题
子集和问题的一个实例为〈S,t〉。其中，S={ x1,x2,…,xn}
是一个正整数的集合，c是一个正整数。
子集和问题判定是否存在S 的一个子集S1，使得 x c
xs1
试设计一个解子集和问题的回溯法。
编程任务：
对于给定的正整数的集合S={ x1,x2,…,xn}和正整数c，编
16
最佳调度问题
数据输入： 第一行有2 个正整数n 和k。第2 行的n 个正整数是完 成n 个任务需要的时间。 结果输出: 完成全部任务的最早时间。 输入示例 73 2 14 4 16 6 5 3 输出示例 17
17
4.7 多机调度问题
按算法greedy产生的作业调度如下图所示，所 需的加工时间为17。
给定2 个n×n 矩阵P 和Q。P[i][j] 是男运动员i 和 女运动员j 配对组成混合双打的男运动员竞赛优势； Q[i][j] 是女运动员i 和男运动员j 配合的女运动员竞 赛优势。 由于技术配合和心理状态等各种因素影响，P[i][j] 不一定等于Q[j][i] 。 男运动员i 和女运动员j 配对组成混合双打的男女双 方竞赛优势为P[i][j]*Q[j][i] 。 设计一个算法，计算男女运动员最佳配对法，使各 组男女双方竞赛优势的总和达到最大。
}
//第lev位
//lev的前k位坐标x[0]~x[k-1] //下标必须大于0 //是相同的
//每隔i个位置
23
5-30 离散01串问题
//判断是否相同
bool same() {
int len = x[0] - x[1];
//计算位置差
for (int i=0; i<len; i++)
//搜索每一位
9
运动员最佳匹配问题
编程任务：
设计一个算法，对于给定的男女运动员竞赛优势，计算男女运 动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。
数据输入：
第一行有1 个正整数n (1≤n≤20)。接下来的2n 行，每行n 个数。 前n 行是p，后n 行是q。
结果输出: 男女双方竞赛优势的总和的最大值。输入示例：
}
for (int i=0; i<k; i++) {
//对每台机器回溯
len[i] += t[dep];
//安排任务dep(左子树)
if (len[i]<best) search(dep+1);
len[i] -= t[dep];
//右子树
}
}
19
最佳调度问题算法
计算完成任务的时间
int comp() {
程计算S 的一个子集S1，使得
xc
xs1
5
子集和问题
数据输入： 第1行有2个正整数n和c，n表示S的大小，c是子集 和的目标值。接下来的1 行中，有n个正整数，表示 集合S 中的元素。 结果输出： 输出子集和问题的解。当问题无解时，输出“No solution! ”。 输入示例 5 10 22654 输出示例 226
} }
//从1开始回溯 //构成1次全排列
//从结点t到叶结点 //将结点j作为当前结点
//将结点还回去
12
运动员最佳匹配问题算法
void pref::Compute(void) {
//计算当前排列的竞赛优势
for (int i=1,temp=0;i<=n;i++) //按题目要求计算
temp += p[i][r[i]]*q[r[i]][i];
if (temp>best) {
//是更好的值？
best = temp;
for (int i=1; i<=n; i++) //构造最优解
bestr[i] = r[i];
}
}
13
运动员最佳匹配问题算法
14
运动员最佳匹配问题算法
main()中的前半部分：
15
5-17 最佳调度问题
假设有n 个任务由k 个可并行工作的机器完成。完成 任务i 需要的时间为ti。试设计一个算法找出完成这n 个任务的最佳调度，使得完成全部任务的时间最早。 编程任务： 对任意给定的整数n 和k，以及完成任务i 需要的时间 为ti，i=1~n 。编程计算完成这n个任务的最佳调度。
void backtrack(int lev) {
//lev从2开始
if (lev>n) {
//一种情况构造完毕
tot += 2;
//个数加倍
return ;
}
for (int i=0; i<2; i++) {
bstr[lev] = i;
//满足条件就回溯
// 0，1
if ( bstrok(lev) ) backtrack(lev+1);
只有一个下标是变化的
11
运动员最佳匹配问题算法
解空间是一棵排列树 void pref::Backtrack(int t) {
if (t>n) Compute(); else
for (int j=t; j<=n; j++) { swap(r[t], r[j]); Backtrack(t+1); swap(r[t], r[j]);