当前位置： >>
第5章(5.3回溯算法)
5.3回溯算法1、回溯算法基本思想 ? 回溯算法是一种搜索算法，其基本思想是在搜索尝试中找问 题的解，当不满足求解条件就”回溯”返回，尝试别的路径。 ? 通俗地讲：回溯法是一种“能进则进，进不了则换，换不了 则退”的基本搜索方法 ? 基本思想： 回溯法在问题的解空间树中，按深度优先策略，从根结点出 发搜索解空间树。 算法搜索至解空间
树的任意一点时，先判断该结点是否包含 问题的解。 如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层 向其祖先结点回溯； 否则，进入该子树，继续按深度优先策略搜索。2、回溯算法解题步骤：(1)针对所给问题，定义问题的解空间, 确定易于搜 索的解空间结构；（排列树，子集树） (2)以深度优先方式(确定扩展规则) 搜索解空间， 并在搜索过程中不断回溯，同时用剪枝函数，剪去 无效的枝，避免无效搜索。? 常用的剪枝函数： 约束函数：在扩展结点处剪去不满足约束的子树； 限界函数(上界函数): 剪去得不到最优解的子树。?解空间树：子集树与排列树遍历子集树需O(2n)计算时间void backtrack (int t) { if (t&n) output(x); else for (int i=0;i&=1;i++) { x[t]=i; if (legal(t)) backtrack(t+1); } }遍历排列树需要O(n!)计算时间void backtrack (int t) { if (t&n) output(x); else for (int i=t;i&=n;i++) { swap(x[t], x[i]); if (legal(t)) backtrack(t+1); swap(x[t], x[i]); } }补充： 0－1背包问题1、问题提出 已知n个物体重量为：w1、w2… n个物体价值为：p1、p2… 背包载重为：M两类背包问题：①普通背包问题（贪心算法） 物体i可以部分的装入背包，若物体i的一部分xi装入 背包，则装入的重量为wi*xi，装入的价值为pi*xi； ②0－1背包问题（回溯算法） 每一件物体不能分割，要么全部放入，要么全部不 放入，称为0－1背包问题；2、基本思路 ①确定问题的解空间，并将解空间组织成易于查找的 子集树的形式；1 1 2 1 3 0 9061 10 0 80 1314051 71 110 121 14015②以深度优先的方式搜索整个解空间，遇到不满足 要求的节点就回溯，沿另一个分支继续搜索；3、举例 背包载重：M＝10 物品重量：w1＝6、w2＝5、w3＝5 物品价值：p1＝42、p2＝25、p3＝30 首先，定义问题的解空间（子集树）； 然后，深度优先搜索解空间(无剪枝函数)；1 1 2 1 0 6 0 5 1 7 0 8 1 11 1 10 0 12 1 14 0 9 0 13 0 1531 4为了提高搜索速度加入剪枝函数；可以避免一些无效搜索； 带剪枝函数: (当前价值+剩余价值)是否大于当前最优装载价值 大于进入右子树，否则剪去右子树；(当前价值+剩余价值) 42+20&42进入右子树1 0 1 2(当前价值+剩余价值) 0+55&42故进入右子树91 3061(当前价值+剩余价值) 0+30&55,不进入右子树 0 1310 014051718010 15111214bestp=554、算法描述double knaspack(double p[ ], double w[ ], double c) //c是背包载重 {double cw=0; //当前重量 double cp=0; //当前价值 double bestp=0; //当前最优装载价值 backtrack(1); //回溯搜索解空间 }double backtrack( int i) //搜索解空间函数 {double n=p. if ( i&n ) // i表示深度（层），即，搜索到叶子节点 { bestp= } //否则，向下深度搜索，并判断当前节点是否超载 else if (cw+w[ i]&=c) //当前物品放入背包不超载 { cw=cw+w[ i]; cp=cp+p[ i]; c=c-w[i]; backtrack(i+1); } //继续向下深度搜索 else //超载，则回溯进入右子树 if ( bound(i+1)&bestp ) //并利用上界函数剪枝，当前价值＋剩余物品价值 大于bestp，进入右子树 backtrack( i+1 ); }double bound(int i) // 计算上界函数 { // 计算当前价值与剩余价值和 double cleft = c - // 剩余容量 double b = // 当前物品价值 // 剩余物品单位重量价值递减序装入物品 while (i &= n && w[ i] &= cleft) { cleft = cleft -w[ i]; b= b + p[i]; i++; } // w[ i]& cleft 跳出循环，物品部分装入背包 if (i &= n) b += p[i]/w[i] * // 当前物品价值与剩余物品价值之和 }5、算法分析该算法计算上界函数bound时间复杂度为O(n); 在最坏的情况下，有2n/2个右孩子节点需要计算上界； 故该算法的时间复杂度记为O(n*2n-1)例5－5： n皇后问题1、问题提出在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际 象棋的规则，皇后可以攻击与之处在同一行或同一列或同一 斜线上的棋子。 令n＝8； 8皇后问题：等价于在8×8格的棋盘上放置8个 皇后，任何2个皇后不放在同一行或同一列或同一斜线上。 1 Q 2 Q 3 Q 4 Q 5 Q 6 Q 7 Q 8 Q 1 2 3 4 5 6 7 8例5－5： n皇后问题2、问题分析该问题可用一个n元数组x[ ]来表示n皇后问题的解； x[ i]表示皇后i放在棋盘的第i行，第x[ i]列； 皇后i与皇后j之间互相不攻击的条件： ①不再同一行： i≠j ②不再同一列： i≠j，且 x[ i] ≠ x[ j] ③不再同一斜线(对角线)上： （i, x[ i]）与 （j, x[ j]） 主对角线及其平行线特点：斜率为-1 或 (行号-列号) 相等; 不在主对角线： i - x[ i] ≠ j - x[ j] 负对角线及其平行线特点：斜率为1 或 (行号+列号) 相等; 不在负对角线： i + x[ i] ≠ j + x[ j] ③ 等价于| i- j | ≠ | x[ i] - x[ j] |例5－5： n皇后问题3、算法思路①首先，确定问题的解空间，并将解空间组织成易于查找的 排列树形式； （利用一颗排列树表示其解空间：例: n=4, 4皇后问题）1 x[1]=1 2 x[2]=4 x[2]=3 8x[3]=2x[1]=2x[1]=3 18x[1]=4x[2]=2 3 x[3]=3 x[3]=4 4 6x[2]=1 19x[2]=4 x[2]=3 24 2913x[3]=2 x[3]=3…… …x[3]=4 9 11x[3]=3 x[3]=1 x[3]=1 x[3]=3 x[3]=4 x[3]=4141620x[3]=42225273032x[4]=4x[4]=3 x[4]=4 x[4]=3 x[4]=3x[4]=2x[4]=3 x[4]=4 x[4]=1 x[4]=321 23 26 28 31x[4]=1571012151733②以深度优先的方式搜索解空间，并用约束函数剪枝（判断是 否满足条件），并不断回溯；1x[1]=1 2 x[2]=2 3 x[3]=3 x[3]=4 4 6 9 x[2]=4 x[2]=3 8x[3]=2x[1]=2x[1]=3 18x[1]=4x[2]=1 19x[2]=4 x[2]=324 2913 x[3]=4 11x[3]=2 x[3]=3…32x[3]=1 x[3]=1 x[3]=3 x[3]=3 x[3]=4 x[3]=4141620 x[4]=422252730… …x[4]=3 x[4]=4 x[4]=3 x[4]=3 x[4]=4 5 7 10 12 15x[4]=2x[4]=3 x[4]=4 x[4]=1 x[4]=3x[4]=117212326283133例5－5： n皇后问题4、算法描述double nqueen(int nn) { int n= int sum=0; // 放置皇后的方案数 int x[ n]; // x[ i]表示皇后i放在棋盘的第i行，第x[ i]列 for (int i=0;i&=n; i++;) x[ i]=0; // 初始化 backtrack(1); } // 回溯搜索解空间void backtrack ( int t) { if( t&n ) // 搜索到叶子节点，方案数＋1，t是层数 sum++; else for( int i=1; i&=n; i++) // 第t个皇后行号t，i列号 { x[ t]=i; // 将第t个皇后放在t行，i列 if( place(t) ) // 判断是否有冲突 backtrack (t+1); // 放下一个皇后 } } void place( int k) { for( int j=1;j&k; j++ ) //k之前的皇后1…k-1是否与k冲突 if( math.abs(k-j)=math.abs(x[ k]-x[ j]) ) }例5－5： n皇后问题4、算法描述 对于n皇后问题的解空间共有nn个叶子节点，最多 有n* nn个节点； 最坏的情况下每个节点都要用place函数判断是否 可行，每一个节点判断时间为O(n)； 故该算法的时间复杂度记为O(n* n*nn)＝ O(nn+2)5.3.4 满m叉树? 当所给问题的n个元素中每一个元素均有m种选择， 要求确定其中的一种选择，使得对这n个元素的选择 结果组成的向量满足某种性质，即寻找满足某种特性 的n个元素取值的一种组合。 这类问题的解空间树称为满m叉树。 ? 解的形式为n元组（x1,x2,……,xn），分量 xi(i=1,2,……,n)表示第i个元素的选择为xix1=1x1=2x1=3x2=1 x3=1 2 32 1 23 3 1 2 3 1 2x2=1 3 12 2 33 3 1x2=1 3 12 2 33 1 3222满3叉树树的根结点：初始状态 中间结点：某种情况下的中间状态 叶子结点：结束状态 分支：从一个状态过渡到另一个状态的行为 从根结点到叶子结点的路径：一个可能的解（n个元素 值的一个组合） 子集树的深度：等于问题的规模。例5－11： 图的着色问题1、问题提出给定无向连通图G和m种不同的颜色； 用这m种颜色为图G的各个顶点着色，是否有一种方法使得 图G中每一条边的两个顶点着不同颜色； 典型的应用： 地图着色，在一个平面或球面的地图，使用4种颜色进行着 色，可以使相邻国家的颜色不一致。 例： 如左图表示一张地图，把该地图转换成平面图如右图.4 1 3 5 2 2 5 3142、解决方法法1：well—powell算法 step1：将图的节点按度数递减排序； step2：用第1种颜色给第1个节点着色； 并按节点排列顺序，用同一种颜色给对不相邻的节 点 着色； step3：按节点度数，顺序选择下一个节点用step2方法着 色，直到所有节点全部着色；A1=4 A2=5A3=4A4=4A5=5A6=4A7=5A8=3Step1：按照节点度数，先用第一种颜色对A7着色，与A7不相邻节点A2用 同一颜色着色； Step2：按节点度，用第二种颜色对A5着色，与A5不相邻节点A1用同一颜 色着色； Step3：按节点度，用第三种颜色对A4着色，与A4不相邻节点A3， A8用同 一颜色着色； Step4：按节点度，用第四种颜色对A6着色；法2：回溯法 3、回溯法解决图的着色问题思路2 ①定义问题的解空间（满m叉树） 顶点i，所着颜色用x[ i]表示；颜色数m=4； 5X[1]=1 2 3 4134X[2]=123 44… …X[3]=123X[4]=12341 23412 3 4123 4…X[5]=1 2341234…②以深度优先的方式搜索解空间，并用约束函数剪枝（判断是否 满足条件,每一条边的两个顶点着不同颜色），并不断回溯；X[1]=1234X[2]=1 2 34……X[3]=1234…X[4]=1 23 4 1 2 3 4 1 2 3 4 1 2 3 4…X[5]=12344、算法描述 double mcoloring(int mm) {int m= //m可用颜色数 double sum=0; //sum当前着色方案数 backtrack( 1 ); //深度优先搜索解空间 }void backtrack( int t) { if ( t&n ) // 搜索到叶子节点 { sum++; //着色方案数加1 for (int i=1; i&=n; i++) system.out.print( x[ i] ); } //输出解,顶点i着颜色x[ i] else // 搜索到中间节点 for(int i=1; i&=m; i++) {x[ t]=i; //顶点t着颜色i if( ok( t ) ) backtrack(t+1); } } boolean ok( int k) //当前着色顶点与以前相邻顶点是否同色 { for(int j=1; j&=n; j++) if( a[ k][ j]&&( x[ j]==x[ k] ) ) //顶点k到j有边：a[ k][ j]，且色同：x[ j]==x[ k]}5、算法分析（m种色，n个节点） 计算限界函数需要O(n)时间; 需要判断限界函数的结点在最坏情况下有 1+m+m2+ m3+……+mn-1=(mn-1)/(m-1)个,故耗时 O(n*mn);在叶子结点处输出着色方案需要耗时O(n)； 在最坏情况下会搜索到每一个叶子结点，叶子结 点有mn个，故耗时为O(n*mn)。故图的m着色问题的回溯算法所需的计算时间为 O(n*mn)+O(n*mn)= O(n*mn)。例5－10 哈密顿回路（旅行售货员问题）1、问题提出设G=(V,E)是一个有n个顶点的连同图； 哈密顿回路是指：图中的n条边经过顶点一次且只有一次最后 回到起始点的一条回路； 旅行售货员问题：n个城市，存在一条路经过城市一次且只有 一次最后回到出发点的一条回路； 例：下图的一条哈密顿回路21 2 8 3 413456787652、回溯法解哈密顿回路思路①定义问题的解空间（同n皇后问题一样） 有n个顶点，所以他的解空间树是一颗高为n的排列树； 简单例子：12435x[ i ] 表示哈密顿回路的第i个顶点X[1]=12345X[2]=2345… …X[3]=345X[4]=4 53543…X[5]=5 45343…2、回溯法解哈密顿回路思路②深度优先的方式搜索解空间，并不断回溯 到叶节点判断是否可以回到起点；X[1]=12345X[2]=2345… …X[3]=345X[4]=453534…4 5 3 4 3X[5]=5…3、算法描述void hamilton (int n, int x[ ], boolean c[ ][ ]) {//x[ n ]存放哈密顿回路的n个顶点 //c[ ][ ]图的邻接矩阵，表示顶点之间有无连接 boolean s[ ]; //s[ i]标记顶点i是否已在哈密顿回路中 for( int i=1; i&=n; i++) { x[ i]=i; s[ i]= } //初始化 backtrack( 1); //深度优先搜索解空间 }void backtrack (int t ) { if ( t&n ) //到叶子节点 { if ( c[ x[ t] ] [ x[1] ]=true ) //且可以回到起点 s[ x[ t] ]= } else { for ( int i=t+1; i&=n; i++ ) if(c[ x[ t] ] [ x[ i] ]=true) {s[ x[ i] ]= backtrack(t+1); } } }例5－12：最小重量机器设计问题? 问题描述 设某一机器由n个部件组成，每一个部件可以从m个不同的供 应商处购得。 设wij是从供应商j处购得的部件i的重量， cij是相应的价格。 试设计一个算法，给出总价格不超过c的最小重量机器设计。 ? 问题分析 该问题实质上是为机器部件选供应商。机器由n个部件组成， 每个部件有m个供应商可以选择，要求找出n个部件供应商 的一个组合，使其满足n个部件总价格不超过c且总重量是 最小的。? 定义问题的解空间： 该问题的解空间形式为（x1,x2,…,xn），分量 xi(i=1,2, …,n)表示第i个部件从第xi个供应商处购买。 m个供应商的集合为S={1,2…,m}，xi∈S，i=1,2, …,n。 ? 确定解空间的组织结构。 一棵满m叉树，树的深度为n。 ? 搜索解空间。 n 约束条件： c ? c?ix ii ?1限界条件：cw&bestwcw ??i ?1twixi? 考虑n=3，m=3，c=7的实例。部件的重量如表5-2 所示、价格如表5-3所示。表5-2 部件的重量表表5-3 部件的价格表W 1 1 2 3 1 3 22 2 2 33 3 1 2C1231 2 31 5 22 4 13 2 2①定义问题的解空间（满m叉树） 第i个部件，从x[ i]供应商处获得； 约束条件：总价格不超过c的最小重量机器；x1=1x1=2x1=3x2=1 x3=1 2 32 3 1 2 3 1 2 3x2=1 1 3 2 12 2 33 3 1x2=1 3 12 23 3 1 3222满3叉树算法描述：void MinMachine::Backtrack(int t) { if(t&n) //到达叶子结点 { bestw= for(int j=1;j&=n; j++) //保存当前最优解 bestx[j]= x[j]; } for(int j=1; j&=m; j++) //非叶子结点，依次搜索每一个供应商 { x[t]=j; if(cc+c[t][j]&=COST && cw+w[t][j]&bestw)//判断约束条件和限界条件 { //c[ t][ j]第t个部件从j供应商获得的价格 cc+=c[t][j];cw+=w[t][j]; Backtrack(t+1); cc-=c[t][j];cw-=w[t][j]; } } }? 算法分析计算约束函数和限界函数需要O(1)时间，需要判断 约束函数和限界函数的结点在最坏情况下有 1+m+m2+ m3+……+mn-1=(mn-1)/(m-1)个，故耗 时O(mn-1)； 在叶子结点处记录当前最优方案需要耗时O(n)，在 最坏情况下会搜索到每一个叶子结点，叶子结点 有mn个，故耗时为O(nmn)。 最小重量机器设计问题的回溯算法所需的计算时间 为O(mn-1)+O(nmn)= O(nmn)。三类问题的时间复杂性子集树问题的时间复杂性O(n2n)排列树问题的时间复杂性O（(n+1)!）满m叉树问题的时间复杂性O(nmn)作业? 1、回溯法基本思想？回溯法解题步骤？ ? 2、什么叫子集树？什么叫排列树？ 什么叫满m叉树？? 3、利用回溯法，求解0－1背包问题，要求设计出相 应算法？并分析其时间复杂度？? 4、利用回溯法，求解n后问题，要求设计出相应算法， 并分析其时间复杂度？
第2章 线性表 第3章 栈和队列 第5章 数组和广义表...5. 空串是指__不含任何字符的串__,空格串是指_...简单模式匹配算法BF算法执行效率低的原因是有回溯存在...可以大大加快匹配速度; 二是主串指针不回溯, 可以使外设文件边读入边匹配。 2...3. 试设计一个算法,将数组 An 中的元素 A[0]至 A[n-1]循环右移 k 位...第5章习题及解答 8页 1财富值 第5章习题参考*** 3页 2财富值 习题第5章...递归算法,求解并输出此问题的所有合法布局.(提示:用回溯法.在第 n 行第 j ...无论我们是以下标方式或指针方式存取 第五章 数组与指针习题 3 数组元素时,系统都是转换为指针方法实现。这样做对多维数组尤其方便。 5.2.2 什么是回溯算法? ...C++程序设计(第2版)课后第五章习题解答_生活休闲。C++书后习题解答 ...回溯法能避免枚举法的许多不必要的搜索,使问题比较快地得到解决. 5.2.3 用...可以大大加快匹配速度; 二是主串指针不回溯, 可以使外设文件边读入边匹配。 2...3. 【严题集 5.18⑤】试设计一个算法,将数组 An 中的元素 A[0]至 A[...第 5 章 归纳法 5.3(本题不仅有以下一个***) 1.max(n) 过程:max(i)...优编码为 a:10 b:001 c:0001 d:0000 e:01 f:11 注意:编码不唯一 回溯...算法设计与分析第五章重点_工学_高等教育_教育专区。回溯法:具有限界凼数的深度...确定易于搜索的解空间结构;3、以深度优 先方式搜索解空间,并在搜索过程中用...人工智能*** 第二章_理学_高等教育_教育专区。1. 2. 3. 4. 5. 树式搜索...A 算法、A*算法} 线式搜索:a,盲目搜索{随即碰撞、回溯穷举} b,启发式搜索{...第五章 教育文献法1_管理学_高等教育_教育专区。教育...这种回溯过程往往会找出研究领域中重要的丰富的原始...2、农村“留守儿童” 的学习状况研究(略) 3、农村...
All rights reserved Powered by
copyright ©right 。文档资料库内容来自网络，如有侵犯请联系***。希望能有开年大作带来惊喜，然而这只是一个希望而已。
苹果 CEO 蒂姆?库克对增强现实技术的兴趣早就已经不是秘密了。这种技术将虚拟图像和...
《Braid》让独立游戏真正迎来了百花齐放的春天，鼓励着无数人走上了独立游戏开发的道...
这个经典，自然就是被国内外用户一致称赞的iPhone 4/4s了，你期待看到这样的 iPhone 8...
FBI 提供的这份文件中并没有显示他们雇佣了谁来解锁 iPhone，也没有显示他们支付了多...
事实上，Chris Lattner 并非唯一一个离开苹果加盟特斯拉的苹果高管。
看来大家真的对这款小配件评价相当的高~
《Pokémon Go》还没有在中国市场推出，因为中国的相关部门并没有给它颁发“通行证”...
本作在继承前作设定的基础上对画面、操作等方面都进行了改进，从而让游戏的品质有了一...
开放式的游戏《孤胆车神：新奥尔良（Gangstar New Orleans）》已经在菲律宾区的苹果商...
在这里玩家同样需要执棋杀出一片天地，最终通往胜利的大门，不过要说明的是，这不是一...
性能稳定，占用空间小，保存和读图速度也快，看来这个不起眼的免费 App也能让人眼前一...
在游戏中玩家将要扮演猎人双胞胎中的一员，通过各种手段来消灭敌人。
《超级游龙》在画面上采用了如今人气颇高的像素风格，再结合有着一定旋律的音乐，本作...
曲折的剧情、宏大又不失细腻的画面、酣畅淋漓的打斗、多元化的职业流派设定，这款游戏...
看来大家真的对这款小配件评价相当的高~
一项调查结果显示，有 65% 的受访者表示他们的 AirPods 不容易掉落。
AirPods的潜力，你认为究竟有多大呢？
有趣的是，现在还有很多人都还没有拿到这款耳机。
这款 Wireless Aluminum Keyboard 是为 Mac 用户而设计的，不仅配有数字键盘，还可以...
对于 iPhone 用户来说，设备的续航似乎总是不太够用，好在我们可以通过系统的一些设置...
新年购物促销活动，无论对于苹果还是消费者来说，似乎都是一次双赢。
日前，配件厂商 OtterBox 在 CES 2017 电子消费展会上发布了 uniVERSE 模块化保护壳的...
请教！N.O.V.A. 3
近地联盟先遣队3第一关中有个电缆线的怎么过??
注册时间 最后登录
在线时间2696 小时 UID
主题帖子人气
金苹果, 积分 2249, 距离下一级还需 751 积分
N.O.V.A. 3&&近地联盟先遣队3第一关中有个电缆线的怎么过??
电缆线一碰就会触电身亡，中间的缝隙又走不过，傍边有个沙发，跳不上去，也过不了！
有谁过了，请指教一下！谢谢！
(78 KB, 下载次数: 0)
16:36 上传

难道楼主没见到同行的ai是从右边柜子还是箱子上跳过去的，这个都难的话，后面更难玩
注册时间 最后登录
在线时间66 小时 UID
主题帖子人气
可以从右边绕过去，别碰到就行了，不然秒杀
注册时间 最后登录
在线时间1733 小时 UID
主题帖子人气
从右边窗口跳过去。
注册时间 最后登录
在线时间2696 小时 UID
主题帖子人气
没有会过的吗？
注册时间 最后登录
在线时间2696 小时 UID
主题帖子人气
右边的窗口路不通
注册时间 最后登录
在线时间19289 小时 UID
主题帖子人气
看你的队友怎么过的
注册时间 最后登录
在线时间1601 小时 UID
主题帖子人气
从右边窗口跳过去。记住是跳！
注册时间 最后登录
在线时间2696 小时 UID
主题帖子人气
没有会过的吗？
注册时间 最后登录
在线时间2696 小时 UID
主题帖子人气
对zhou1988cool于 17:40在6楼发表的回复评分:人气:+1;
从右边窗口跳过去。记住是跳！感谢指点，但窗口跳不过去，貌似ip4玩有BUG
注册时间 最后登录
在线时间1926 小时 UID
主题帖子人气
心如苍井空止水
威锋旗下产品
Hi~我是威威！
沪公网安备 29号　|　沪ICP备号-1
新三板上市公司威锋科技（836555）
增值电信业务经营许可证：
Powered by Discuz!