搜索与回溯（综合整理版）

nullnull** 根据“信息学初学者之家”网站的统计，Ural（俄罗斯的Ural州立大学的简称 ，有名的Ural Online Problem Set 就是该校的系统）的题目类型大概呈如下的分布： 搜索 动态规划 贪心 构造 图论 约10% 约15% 约5% 约5% 约10% 计算几何 纯数学题 数据结构 其它 约5% 约20% 约5% 约25% 统计信息：搜索与回溯**搜索与回溯什么是搜索算法呢？**什么是搜索算法呢？ 搜索算法是利用计算机的高性能来有目的地穷举一个问题的部分或所有的可能情况，从而求出问题的解的一种。 其实质就是---枚举，但又与枚举有所不同 搜索过程实际上是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的节点的过程。null** 搜索：一般是通过状态转移不断地寻找目标状态或最优状态。 状态：是对问题在某一时刻的进展情况的数学描述 状态扩展：是问题从一种状态转移到另一种状态的操作。 举例：二分查找**举例：二分查找2 3 4 5 6 8 12 20 32 45 65 74 86 95 100查找示意图：**查找示意图：……一、宽度优先遍历(BFS)**一、宽度优先遍历(BFS)基本算法**基本算法 给定图G和一个源点s, 宽度优先遍历按照从近到远的顺序考虑各条边. 算法求出从s到各点的距离 宽度优先的过程对结点着色. 白色: 没有考虑过的点 黑色: 已经完全考虑过的点 灰色: 发现过, 但没有处理过, 是遍历边界 依次处理每个灰色结点u, 对于邻接边(u, v), 把v着成灰色并加入树中, 在树中u是v的父亲(parent)或称前驱(predecessor). 距离d[v] = d[u] + 1 用队列Q管理所有的灰色节点 整棵树的根为snull**null**二、深度优先遍历(DFS)**二、深度优先遍历(DFS)基本算法**基本算法新发现的结点先扩展 特别之处: 引入时间戳(timestamp) 发现时间d[v]: 变灰的时间 结束时间f[v]: 变黑的时间 1<=d[v] < f[v] <= 2|V| 初始化: time为0, 所有点为白色, dfs森林为空 对每个白色点u执行一次DFS-VISIT(u)DFS-VISIT算法**DFS-VISIT算法初始化: time为0, 所有点为白色, dfs森林为空 对每个白色点u执行一次DFS-VISIT(u) 时间复杂度为O(V+E)null**DFS树的性质**DFS树的性质括号结构性质 对于任意结点对(u, v), 考虑区间[d[u], f[u]]和[d[v], f[v]], 以下三个性质恰有一个成立: 完全分离 u的区间完全包含在v的区间内, 则在dfs树上u是v的后代 v的区间完全包含在u的区间内, 则在dfs树上v是u的后代null**有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。 回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。 回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。回溯法问题的解空间**问题的解空间问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,…,xn)的形式。 显约束：对分量xi的取值限定。 隐约束：为满足问题的解而对不同分量之间施加的约束。 解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）。null**生成问题状态的基本方法扩展结点:一个正在产生儿子的结点称为扩展结点 活结点:一个自身已生成但其儿子还没有全部生成的节点 死结点:一个所有儿子已经产生的结点称做死结点 深度优先的问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个儿子（如果存在） 宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点 回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法null**回溯法的基本思想(1)针对所给问题，定义问题的解空间； (2)确定易于搜索的解空间结构； (3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。常用剪枝函数： 用约束函数在扩展结点处剪去不满足约束的子树； 用限界函数剪去得不到最优解的子树。用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。而显式地存储整个解空间则需要O(2h(n))或O(h(n)!)内存空间。null**递归回溯回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法。void backtrack (int t) { if (t>n) output(x); else for (int i=f(n,t);i<=g(n,t);i++) { x[t]=h(i); if (constraint(t)&&bound(t)) backtrack(t+1); } } constraint:约束 Bound:有义务的；受约束的； null**迭代回溯采用树的非递归深度优先遍历算法，可将回溯法表示为一个非递归迭代过程。void iterativeBacktrack () { int t=1; while (t>0) { if (f(n,t)<=g(n,t)) for (int i=f(n,t);i<=g(n,t);i++) { x[t]=h(i); if (constraint(t)&&bound(t)) { if (solution(t)) output(x); else t++;} } else t--;//回溯一步 } }null**子集树与排列树遍历子集树需O(2n)计算时间 遍历排列树需要O(n!)计算时间 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); } }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]); } } null问题1：走楼梯 楼梯有n级台阶，上楼可以一步上1级，也可以一步上2级。编一程序找出上到楼顶时的所有不同的走法。 问题分析 每一步走法都有两种选择，或上一级或上两级，于是可以画出一个上楼梯方法的树形图示。如图所示是走3步时的情况。 树中的每一个分支表示走上楼梯的一种走法，如果每一步都有两种选择，走n步，将有2n个分支！但是，按题目要求，每一步能否有两种选择是有限制的： 1.走到n级台阶，就结束上楼； 2.如果剩余台阶数不足走1或2，就不能走。 于是，当n=3时，图中有若干分支是不符合要求的，将其剪枝，图中画×的枝条就是被剪断处。这样，满足条件的分支上的结点连起来就是：1-1-1，1-2，2-1三种走法方案。 从起点出发，每一步试探两种选择，能走就走，不能走，就退回一步，走另外一个分之。所有情况都试探过了，也就找到了所有方案。null 上面这种试探的方法，就是搜索回溯算法。它是一种系统地搜索问题的解的方法。搜索回溯法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。 算法描述 设置一个a数组记录分支上的结点；设置变量passed记录走过的台阶数，当passed=n时，表示已经到顶，结束试探。每一步有两种选择：若可以走i级台阶，则走上i级（记录到a数组中）后，将passed加上i，继续下一步，如果无法走返回上一步，试探下一种走法，而试探下一种走法前，要将passed复位，即从passed中减去刚加上的i。 一个递归过程try(step)试探第step步走法： 1.如果passed=n，则输出当前走法方案，否则枚举走法i（1至2）： 如果可以走i级台阶，则 ① a[step] ←i; ② passed←passed+i; ③ try(step+1); ④ passed←passed-i; 2.结束过程null 上面这种试探的方法，就是搜索回溯算法。它是一种系统地搜索问题的解的方法。搜索回溯法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。 算法描述 设置一个a数组记录分支上的结点；设置变量passed记录走过的台阶数，当passed=n时，表示已经到顶，结束试探。每一步有两种选择：若可以走i级台阶，则走上i级（记录到a数组中）后，将passed加上i，继续下一步，如果无法走返回上一步，试探下一种走法，而试探下一种走法前，要将passed复位，即从passed中减去刚加上的i。 设计一个递归过程try(step)试探第step步走法： 1.如果passed=n，则输出当前走法方案，否则枚举走法i（1至2）： 如果可以走i级台阶，则 ① a[step] ←i; ② passed←passed+i; ③ try(step+1); ④ passed←passed-i; 2.结束过程null 上面这种试探的方法，就是搜索回溯算法。它是一种系统地搜索问题的解的方法。搜索回溯法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。 算法描述 设置一个a数组记录分支上的结点；设置变量passed记录走过的台阶数，当passed=n时，表示已经到顶，结束试探。每一步有两种选择：若可以走i级台阶，则走上i级（记录到a数组中）后，将passed加上i，继续下一步，如果无法走返回上一步，试探下一种走法，而试探下一种走法前，要将passed复位，即从passed中减去刚加上的i。 设计一个递归过程try(step)试探第step步走法： 1.如果passed=n，则输出当前走法方案，否则枚举走法i（1至2）： 如果可以走i级台阶，则 ① a[step] ←i; ② passed←passed+i; ③ try(step+1); ④ passed←passed-i; 2.结束过程null 这里passed不仅记录走过的台阶数，还做了占位标志。回溯算法中设置占位标志的方法很实用，可以很好地避免回溯试探的重复。当然，在退回到本层调用的时候，一定要记得恢复占位标志，为同一层的其他试探留出空间。 通过这个例子，可以归纳出寻求所有方案类问题用递归实现的回溯算法的一般模型： procedure try(i:integer); //当前在第i个结点 var j:integer; begin 如果当前结点是目标结点，则输出，否则     尝试所有满足条件的结点        if   新结点符合条件 then        begin        记录新结点； 设置占位; try(i+1); //试探下一个结点 删除结点； //在程序中，有时不必写出这一步 恢复占位标志；        end; end;null**n后问题在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。null**null**null**解题思路：  总体思想为回溯法。 求解过程从空配置开始。在第1列~的m列为合理配置的基础上，再配置第m+1列，直至第n列也是合理时，就找到了一个解。在每列上，顺次从第一行到第n行配置，当第n行也找不到一个合理的配置时，就要回溯，去改变前一列的配置null**null**算法描述 1、数据初始化； 2、从第1行，第1列放第一皇后开始调用递归过程try(i)； 3、输出方案总数； 3、结束。 回溯算法的递归过程try(i)描述： 如果i>8,说明已摆放好8个皇后，方案数加1，否则 行坐标设置为j（1至8），循环测试 如果当前位置(i,j)未被占（行和两条斜线的占位标志均为0），则 1.摆放第i个皇后； 2.设置行和两条斜线的占位标志为1； 3.继续递归，摆放下一个皇后try(i+1)； 4.恢复占位标志。null**解向量：(x1, x2, … , xn) 显约束：xi=1,2, … ,n 隐约束： 1)不同列：xixj 2)不处于同一正、反对角线：|i-j||xi-xj|n后问题bool Queen::Place(int k) { for (int j=1;jn) sum++; else for (int i=1;i<=n;i++) { x[t]=i; if (Place(t)) Backtrack(t+1); } }HDOJ_1238 Substrings **Sample Input 2 3 ABCD BCDFF BRCD 2 rose orchidSample Output 2 2 HDOJ_1238 Substrings 题目分析：**题目分析：这是一道入门级别的搜索题，基本思想比较简单，但是如果用最朴素的算法，可能会超时如何降低算法的复杂度呢？ 下面的算法如何： 先将字符串按长度从短到长排序，枚举最短的字符串的子串，判断是否都是别的字符串的子串，求出最大长度即可。说明：**说明： 本题除了可以练习基本搜索算法，也是练习字符串处理的好题目，题中用到的相关

知识点

高中化学知识点免费下载体育概论知识点下载名人传知识点免费下载线性代数知识点汇总下载高中化学知识点免费下载

有： 求反串 求子串 字符串查找 求字符串长度强烈推荐！！null代码： #include #include #include //STL reverse函数的头文件 using namespace std;int main() {  int t, n, i, j, k;  string s[102];  int sm, mlen = 200, max;   cin >> t; **null while(t--)  {   cin >> n;   for(i = 0; i < n; i++)   {    cin >> s[i];    if(mlen > s[i].size()) //找出最小的那个母串    {     sm = i;     mlen = s[i].size();    }   }  max = 0;  **nullfor(i = s[sm].size(); i > 0; i--) //从最小的母串开始从长到短找子串   for(j = 0; j < s[sm].size() - i + 1; j++) //长度为i的子串在母串中找   {    string s1, s2; //s1为子串正 ，s2为子串反    s1 = s[sm].substr(j, i);    s2 = s1;    reverse(s2.begin(), s2.end());   for(k = 0; k < n; k++)  **null  if(s[k].find(s1, 0) == -1 && s[k].find(s2, 0)) //当正反子串在母串中都未发现时即跳出         break;        if(k == n && max < s1.size())     max = s1.size();   }  cout << max << endl;   } return 0; } **null**回溯学习要点 理解回溯法的深度优先搜索策略。 掌握用回溯法解题的算法框架 （1）递归回溯最优子结构性质 （2）迭代回溯贪心选择性质 （3）子集树算法框架 （4）排列树算法框架 null**通过应用范例学习回溯法的设计策略。 （1）装载问题； （2）批处理作业调度； （3）符号三角形问题 （4）n后问题； （5）0-1背包问题； （6）最大团问题； （7）图的m着色问题 （8）旅行售货员问题 （9）圆排列问题 （10）电路板排列问题 （11）连续邮资问题附录：推荐搜索题：**附录：推荐搜索题：1010、1240、1241、1242 1072、 1253 、 1312、1372 1238、1239、1015、1016 1401、1515、1548 以上题目均为HDU的题目练习题(搜索，回溯)**练习题(搜索，回溯)北大ACM (http://acm.pku.edu.cn ) 上的 简单：1128, 1166, 1176, 1231, 1256, 1270, 1321, 1543, 1606, 1664, 1731 不易：1024, 1054, 1117, 1167, 1708, 1746, 1775, 1878, 1903, 1966, 2046