在市场部做网站多少工资,微网站需要域名吗,选择网站建设公司好,珠海网站建设目录 6.1 回溯法的设计技术 #xff1a; 四皇后问题 回溯法#xff1a; 算法框架#xff1a; 思考题#xff1a; 回溯算法的适用条件 【例6-1】求满足下列不等式的所有整数解#xff1a; 6.2回溯算法的经典例题 【例6-2】装载问题 问题分析 计算模型 算法设计与描… 目录 6.1 回溯法的设计技术 四皇后问题 回溯法 算法框架 思考题 回溯算法的适用条件 【例6-1】求满足下列不等式的所有整数解 6.2回溯算法的经典例题 【例6-2】装载问题 问题分析 计算模型 算法设计与描述 算法分析 代码 【例6-3】n皇后问题。 问题分析 算法思想详见开篇。 计算模型 算法设计与描述 算法分析 另一种随机算法 【例6-4】 0-1背包问题。 问题分析 数学模型 计算模型 算法设计与描述 算法分析 代码 【例6-5】旅行商问题(Traveling Salesman Problem简称TSP)。 问题分析 计算模型 算法设计与描述 小结 分支限界法的设计技术 分支限界法 约束条件 剪枝 分支限界法的设计步骤 思考题 【例6-6】装载问题。 计算模型 【例6-7】背包 问题分析 问题分析 计算模型 计算模型 算法设计与描述 【例6-8】旅行商问题(Traveling Salesman ProblemTSP) 问题分析 计算模型 算法设计与描述 6.1 回溯法的设计技术 活结点可以生成子节点 扩展结点 死结点不能再进行子节点生成的 回溯法 在约束条件下对解空间树进行深度优先搜索的过程 并在搜索过程中剪去那些不满足条件的分支。 问题的解 为n元组(X 1 ,…,X i ,…X n )其中X i 选自有限集S · 当选出一组值X(x 1 ,…,x i ,…x n )能够使评价函数P(x 1 ,…,x i ,…x n ) 满足问题的某种约束条件或到达极值。 基本策略 每次只考虑一个分量逐次扩大建立n元组 并随时用评价函数P i (X 1 ,…,X i ,…X n)去判断正在形成的n元组是否有成功的希望 一旦确定部分元组(X 1 , … ,X i)不能求出解时则立即停止这种搜索“剪掉”以当前结点为 根的分枝 并逐次向上一个分量回溯 然后向其它分支继续探索 算法框架 (1) 开始结点 是一个活结点也是一个 扩展结点 (2) 如果能从当前的扩展结点移动到一个新的结点那么这 个新结点将变成一个活结点和可扩展结点旧的扩展结点 仍是一个活结点。 (3) 如果不能移动到一个新结点(已经找到一个解或违反约 束的情况)当前的扩展结点就变成了一个 死结点 便只能 返回到最近被考察的活结点(回溯),这个活结点就变成了新 的扩展结点。 (4) 当找到了最优解或者没有活结点的时候回溯尽了所有的活结点搜索过程结束 回溯的递归框架回溯的非递归模式输入n输出所有的解x[] int x[n],i1; search(int i) { if(in)//递归出口 输出结果; else//枚举所有可能的路径 { for(j下界;j上界;jj1)//当前结点的子节点的同一层 { //满足 界限函数和约束条件 if(P(j))// {//深度 下一层 x[i]j;//将符合要求的结点的编号存储到解的数组里 ...//其他操作 search(i1); 回溯前的清理工作;//再进行for循环 下一个结点 } } } } int x[n],i1; //还未回溯到头 i为真 表示有路可走 while(i(未达到目标) ) { if(in)//搜索到叶节点 搜索到一个解输出; else//处理第i个元素 { x[i]第一个可能的值 //x[i]不满足约束条件但在搜索空间内 while( !P(x[i]) x[i]在搜索空间内 ) x[i]下一个可能的值 if( x[i]在搜索空间内) { 标识占用的资源 ii1;//扩展下一个结点 } else { 清理所占的状态空间 ii-1;//回溯 } } } 思考题1 (1)不是唯一 n元组 3剪枝判断是否满足约束条件。执行将结点标为死结点。 回溯算法的适用条件 多米诺性质 设向量X i x 1 , x 2 ,…,x i X i XX x 1 , x 2 ,…,x i ,…,x n 将X i 输入评价函数P可以得到X i 的一组 特征值P(X i ) 取X i1 x 1 , x 2 ,…,x i , x i1 【增加一个元素】Xi1 X则P(Xi1) 真蕴涵P(X i )即 P(Xi1) - P(Xi) i∈(0,n) ,其中n代表解向量的维数。 【子集否则可能丢解】 【例6-1】求满足下列不等式的所有整数解 解令X i x 1 , x 2 ,…,x i P(X i )为对X i 的评估判断其Xi是否满 足不等式即P(X i ) ≤10。依据题目可知本例中向量为一个三元 组 x 1 , x 2 , x 3 。 【丢解】 当x11、x22时 P(x1 ,x2 ) 5x14x25*14*21310 不满足约束条件分支x22将被剪去 然而当x 1 1、x 2 2、x 33时 P(x 1 ,x 2 ,x 3 ) 5x 1 4x 2 - x 35*14*2 - 310 满足约束条件即1, 2, 3是不等式的解 显然此例中P(X 3 )不真蕴涵P(X 2)违反了多米诺性质从而丢解了。 【解决】 如果令x’34-x3 将原不等式变换为5x14x2x’3≤14 1≤xi , x’3≤3 i1, 2 则该不等式满足多米诺性质可以使用回溯法对所得到的解x 1 、x 2 、x’ 3 转 换成原不等式的解x 1 、x 2 、x 3 即可。 代码 #includeiostream
using namespace std;//
int n3;
int x[3]{1,1,1};void show(int a[])
{for(int i0;in;i)couta[i]\t;coutendlendl;
}//约束条件
bool P(int x[],int i)//表示第几层
{switch(i){case 0: if(5*x[0]14)return true;else return false;case 1:if(5*x[0]4*x[1]14)return true;else return false;case 2:if(5*x[0]4*x[1]x[2]14)return true;else return false;}} void fun(int i)
{
// couticendl;
// show(x);if(in-1)//已经结束了最后一个数 {
// cout结果:;show(x);return;//结束最后一层回溯到上一层 }//若不变 if(P(x,i)x[i]4)//符合约束条件 {x[i]1;fun(i1); //下一层 }//若2if(P(x,i)x[i]4)//符合约束条件 {int tx[i];x[i]2;fun(i1); //下一层 x[i]t;//回复 }//若3if(P(x,i)x[i]4)//符合约束条件 {int tx[i];x[i]3; fun(i1); //下一层 x[i]t;//回溯后本层尝试下一个可能 }
}int main()
{fun(0);return 0;}
/*
1 1 11 1 21 1 31 2 11 2 21 2 3
*/ 6.2回溯算法的经典例题 【例6-2】装载问题 有n个集装箱要装上一艘载重量为c的轮船其中集装箱i的重量为w i 。找出一种最优装载方案让轮船尽可能多装集装箱即在装载体积不受限制的情况下尽可能使轮船满载。 问题分析 设集装箱数量n5轮船载重c10集装箱的重量w{7,2,6,5,4} 对于n个集装箱的装载问题可将该问题的解定义为一个n元组 (x 1 ,…,x i ,…x n ), i∈Z, 1≤i≤n, x i ∈{0,1}, x i 1表示装入集装箱ix i0表 示不装入集装箱i。 其中wi 表示第i个集装箱的重量。 满足多米诺条件 计算模型 1. 数据结构定义 静态数据结构 轮船载重量为c集装箱数量为n集装箱重量数组 w[]这些变量在运算中不会发生改变。 动态数据结构 i表示搜索的层数加入一个集装箱后计算出的当前 载重量nowc、当前解x[]、当前最优重量maxc、当前最优解maxx[] 剩余的集装箱重量r初值为全部集装箱重量 这些值都是边测试 边生成的当所有计算全部完成后maxc和maxx[]就是题目要求的 最优值和最优解。 2. 迭代公式 算法设计与描述 输入c, n, w[] 输出最优值maxc和最优解maxx[] void search (int i){ /*递归法*/if(in){//搜索完if(nowcmaxc){//现在重量值maxcnowc;for(int j1;jn;j)maxx[j]x[j];}return;}//剩余量 rr-w[i]; //搜索第i层同时减少可用量//若不装则岸上重量减去if(nowcw[i]c){ //满足约束左子树x[i]1;nowcnowcw[i];search(i1);//递归搜索i1层nowcnowc-w[i];//回溯后恢复nowc} /*下面开始搜索右子树*/if(nowcrmaxc){ /*大于当前最优*/x[i]0;search(i1); //递归搜索i1层}rrw[i];//对第i层搜索完毕恢复r
}算法分析 (1)由算法设计与描述推导 T(1) 2T(1) //集装箱1选择与不选择 2T(1) 2*2T(1)2^ 2 T(1) …… 2 ^( n-1) T(1) 2*2^( n-1) T(1) 2^ n T(1) T(n) T(1) 2T(1) 2^ 2 T(1)……2^ n T(1) T(1)*(2^( n1) – 1)≤2×2^ n O(2^ n ) (2) 由选择树推导 结点数为: 122^ 2 ……2^ n 2^( n1) - 1≤ 2×2^ n O(2^ n ) 代码 #includeiostream
using namespace std;int n5;//集装箱数量
int c10;//轮船载重
int w[]{7,2,6,5,4};//集装箱的重量int nowc0;//当前载重量
int x[5];//当前解
int maxc0;//当前最优重量
int maxx[5]; //当前最优解
int r72654;//剩余集装箱的总重量 void show(int a[])
{for(int i0;in;i)couta[i]\t;coutendlendl;
}void search (int i){ /*递归法*/if(in-1){//搜索完 递归出口 if(nowcmaxc){//现在重量值当前最优 //更新最优解 maxcnowc;//记录最优解的路径 for(int j1;jn;j)maxx[j]x[j];}return;//结束最后一层的函数回溯到上一层进行递归调用 }rr-w[i]; //此时 陆地上集装箱的剩余重量 //若不装则岸上重量减去if(nowcw[i]c){ //满足约束小于轮船载重量左子树x[i]1;nowcnowcw[i];search(i1);//递归搜索i1层nowcnowc-w[i];//回溯后恢复nowc//回到上一层 }/*下面开始搜索右子树 *///右子树是否需要递归if(nowcrmaxc){ /*上界函数 此时当前轮船已载重量剩余集装箱重量 当前最优*/x[i]0;search(i1); //递归搜索i1层}//否则不进行递归也就是可以确认为死结点 rrw[i];//对第i层搜索完毕恢复r//陆地上增加
}int main()
{search(0);//从第1层开始 coutmaxcendl;show(maxx);return 0;
} 【例6-3】n皇后问题。 在n*n的棋盘上放置相互攻击不到的n个皇后。 国际象棋规则任意两个皇后之间不能处在同一行、同一列和同一斜线上否则皇后间就可以相互攻击。 请给出满足条件的所有方案。 问题分析 算法思想详见开篇。 计算模型 1数据结构 皇后数量为n sum为可行解的数量。 x[]记录皇后的摆放位置下标为皇后所在行值为列。 /*若数组下标 参与运算会大大遍历*/ 2计算模型 其中式2与式3共同构成了对式1中所取得的值的一个评价所以可以统称式2和式3为评价函数P。 算法设计与描述 输入皇后的数量n 输出皇后的摆放位置x[]可以有多组
/*判断当前格局x[1...i]是否符合约束*/
bool ok(int i){for(int j1;ji;j)//值相等 或 在对角线上 if(x[i]x[j]||(abs(x[i]-x[j])(i-j)))return false;return true;
}void queen(int i){if(in){//找到可行解for(int j1;jn;j)printf(%-5d,x[j]);printf(\n);sumsum1;//可行解数目1 }for(int j1;jn;j){//每一层都有n个元素 x[i]j;if(ok(i))//如果满足约束queen(i1);//搜索第i1层//否则就结束在这一层 }
} 算法分析 由选择树可知 由ok函数 时间复杂度为 另一种随机算法 程序设计可能很麻烦实际实现效率非常差。 回溯和随机相结合——更好 【例6-4】 0-1背包问题。 已知有n件物品物品i的重量为wi、价值为pi。现从 中选取一部分物品装入一个背包内背包最多可容纳的总重量是m如何选择才能使得物品的总价值最大 问题分析 物品数量n3 物品重量w{10,20,30} 物品价值p{60,100,120} 背包承重m50 数学模型 pi第i个物品价值0xi第i个物品是否被选择[0,1] 计算模型 1. 数据结构 背包容量m物品数量n物品重量数组w[]物品价值数组p[]。 当前背包重量bagw当前背包总价bagp当前最优解x[] 当前最优总价值maxp最优解maxx[]可用的物品价值r。 2. 迭代公式 算法设计与描述 void bag(int i){ if(in){ if(bagpmaxp){ maxpbagp; for(int j1;jn;j){ maxx[j]x[j]; } } return; } rr-p[i]; //对第i层进行搜索,用r减少 if(bagww[i]m){ //满足约束 x[i]1; bagwbagww[i]; bagpbagpp[i]; bag(i1); bagwbagw-w[i]; //回溯后恢复bagw bagpbagp-p[i]; //回溯后恢复bagp } if(bagprmaxp){ //搜索右子树 x[i]0; bag(i1); } rrp[i]; //对第i层进行搜索回来恢复r } 算法分析 思考题 蛮力法 回溯法区别回溯法有对右子树的剪枝时间渐进复杂度T(n)O(2^n)T(n)O(2^n)区别在实际运算中同样情况下回溯法的时间复杂度优于蛮力法回溯法最坏情况下的时间渐进复杂度与蛮力法相同。原因回溯法存在剪枝操作。 代码 #includeiostreamusing namespace std;int n3;//物品数量
int w[]{10,20,30};//物品重量
int p[]{60,100,120};//物品价值
int m50;//背包称重
//使物品总价值最大 int bagw0;//当前背包重量
int bagp0;//当前背包价值
int x[3];//当前最优解
int maxp0;//当前最优总价值
int maxx[3];//最优解
int r60100120;//可用的物品价值也就是物品总价值剩余量 void show(int a[])
{for(int i0;in;i)couta[i]\t;coutendlendl;
}void bag(int i)
{if(in-1){if(bagpmaxp){maxpbagp;for(int j0;jn;j){maxx[j]x[j];}}return ;}//rr-p[i];//对第i层进行搜索r 减少if(bagww[i]m)//小于背包总重量约束条件 {x[i]1;bagwbagww[i];//更新当前背包重量bagpbagpp[i];//更新价值bag(i1);//下一层bagwbagw-w[i];//回溯bagpbagp-p[i]; } if(bagpr maxp)//如果当前价值剩余价值 当前最大价值 还有递归的必要//如果是 当前价值剩余价值 当前最大价值,那么其实就没有递归的必要了 {x[i]0;//右子树 bag(i1);}rrp[i];//对第i层进行搜索回来回复r }int main()
{bag(0); coutmaxpendl;show(maxx);return 0;
} 【例6-5】旅行商问题(Traveling Salesman Problem简称TSP)。 问题分析 假设城市数量n4V{A,B,C,D}城市间的距离如图6-9所示的图结构。 设出发城市为A问题的解空间为{A→{BCD三者的全排列}→A} 计算模型 1. 数据结构 城市数量n距离矩阵d[][]城市名称city[]。 当前路径距离nowd当前路径nowx[],最短距离mind,最优路径x[]。 2. 迭代公式 算法设计与描述 输入城市数量n距离d[][] 城市名city[] 输出最优路径x[]最优值mind 算法分析 对由n个城市形成的全排列树来说所含的结点数目为 蛮力法回溯法区别时间渐进复杂度O( (n-1)! )O( n-1! ) 小结 二分查找算法 分治算法策略的设计模式 大整数乘法和Strassen矩阵乘法 棋盘覆盖问题 选择性问题
