搜索和回溯算法C版共43页文档

白色: 没有考虑过的点 黑色: 已经完全考虑过的点 灰色: 发现过, 但没有处理过, 是遍历边界


依次处理每个灰色结点u, 对于邻接边(u, v), 把v 着成灰色并加入树中, 在树中u是v的父亲(parent) 或称前驱(predecessor). 距离d[v] = d[u] + 1 用队列Q管理所有的灰色节点 整棵树的根为s


初始化: time为0, 所有点为白色, dfs森林为空 对每个白色点u执行一次DFS-VISIT(u)
2013-7-22
10
DFS-VISIT算法

初始化: time为0, 所有点为白色, dfs森林为空 对每个白色点u执行一次DFS-VISIT(u) 时间复杂度为O(V+E)
2013-7-22
2013-7-22
24
2013-7-22
25
n后问题 •解向量：(x1, x2, … , xn) •显约束：xi=1,2, … ,n •隐约束： 1)不同列：xixj 2)不处于同一正、反对角线：|i-j||xi-xj|
bool Queen::Place(int k) { for (int j=1;j<k;j++) if ((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])) return false; return true; } 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、定义一个解空间，它包含问题的解。

2、利用适于搜索的方法组织解空间。

3、利用深度优先法搜索解空间。

4、利用限界函数避免移动到不可能产生解的子空间。

问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。

下面通过一个具体实例加深大家对回溯算法的认识。

二、回溯算法的应用举例：例1：马的遍历中国象棋半张棋盘如图1(a)所示。

马自左下角往向右上角跳。

规定只许往右跳，不许往左跳，马只能走日字。

比如图1(a)所示为一种跳行路线，并将所经路线打印出来，打印格式为：0,0->2,1->3,3->1,4->3,5->2,7->4,8。

找出所有路径。

【算法分析】如图1（b）,马最多有四个方向，若原来的横坐标为j、纵坐标为i,则四个方向的移动可表示为：1: （i,j）→（i+2,j+1）； (i<3,j<8)2: （i,j）→（i+1,j+2）； (i<4,j<7)3: （i,j）→（i-1,j+2）； (i>0,j<7)4: （i,j）→（i-2,j+1）； (i>1,j<8)搜索策略：S1:Ａ[１]:=(0,0);S2:从Ａ[1]出发，按移动规则依次选定某个方向，如果达到的是（4,8）则转向S3,否则继续搜索下一个到达的顶点；S3:打印路径。

【算法设计】#include<cstdio>#include<iostream>#include<cstdlib>using namespace std;int a[100][100],t=0;int x[4]={2,1,-1,-2},y[4]={1,2,2,1};int search(int);int print(int);int main(){a[1][1]=0;a[1][2]=0;search(2);system("pause");}int search(int i){for(int j=0;j<=3;j++)if(a[i-1][1]+x[j]>=0&&a[i-1][1]+x[j]<=4&&a[i-1][2]+y[j]>=0&&a[i-1][2]+y[j]< =8){a[i][1]=a[i-1][1]+x[j];a[i][2]=a[i-1][2]+y[j];if(a[i][1]==4&&a[i][2]==8) print(i);else search(i+1);}}int print(int ii){{t++;cout<<t<<": ";for(int i=1;i<=ii-1;i++) cout<<a[i][1]<<","<<a[i][2]<<"-->";cout<<"4,8"<<endl;}}.例2：选书学校放寒假时，信息学竞赛辅导老师有A，B，C，D，E五本书，要分给参加培训的张、王、刘、孙、李五位同学，每人只能选一本书。

回溯算法学习重点：1、理解回溯法的基本思想；2、掌握回溯法解题的基本算法。

`学习过程:一、回溯法的基本思想回溯法又称试探法。

回溯法的基本做法是深度优先搜索，是一种组织得井井有条的、能避免不必要重复搜索的穷举式搜索算法。

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

具体说,就是：在搜索(依次用各种方法一一去试探)的过程中，当在P点有N种选择，则从第一种开始尝试，若第K种可行，即这一步搜索成功，打上标记，再向前(即 P+1点)搜索；如在P 点搜索失败(所有的方法都试探过，没有一种可行)，为了摆脱当前的失败，就返回搜索进程中的上一点(即P-1点)，再用第K+1种方法(假设上次在P-1点用第K种方法搜索成功，必须明确以前用过的方法不能再用，否则会陷入死循环)再去搜索，重新寻求解答。

这样搜索回溯，再搜索再回溯，如能搜索到终点，问题有解，如最后回溯到出发点，问题就无解。

这种在搜索的过程中，先对深度大的点进行扩展的算法，叫深度优先搜索法。

设搜索深度指针为P，搜索方法指针为I，可把深度优先搜索算法写成如下形式：P=0：I=0DOI=I+1(搜索到一种方法)IF 搜索方法有效 THEN试探产生临时新结点IF 符合条件 THENP=P+1(深入一步)，新结点记录，I=0，再全方位搜索IF到达终点 THEN 结束搜索，输出结果END IFELSE(搜索的方法无效)I=上次搜索的方法(下一轮将用I的下一方法去搜索)，P=P-1(后退一步返回上结点) END IFL00P UNTIL P=0IF P=0 THEN ’深度指针P为0，表示已退到起始状态，是本题无解的标志无解ELSE输出结果END IFEND二、应用举例1、【问题描述】有一迷宫(如图)，可用一个10行9列的0～1矩阵表示，其中0表示无障碍(白色)，1表示有障碍(黑色)。

设入口位置的坐标为(2，1)，出口为(9，9)，规定每次移动中只能从一个无障碍的单元移到其周围四个方向上任一无障碍的单元。

void dfs(int k){ 1： if(k==N+1)printf("%s\n",d+1); 2： else{ 3： d[k]='A'; 4： dfs(k+1); 5： d[k]='B'; 6： dfs(k+1); 7： d[k]='C'; 8： dfs(k+1); } }
栈区的变化：
Main函 数
栈区的变化：
Main函 数
dfs(1) k=1 执行位置：4 dfs(2) k=2 执行位置：4 dfs(3) k=3 执行位置：6
输出：AAB
dfs(4) k=4 执行位置：1
返回地址
返回地址
返回地址
返回地址
函数执行过程：
N=3
int main() { scanf("%d",&N); dfs(1); return 0; }
①从第1位开始，枚举第1位的第一种取值， 枚举第2位的第一种取值，直到第N位。 ②当k=n时，找到一种情况，输出n个字符。 ③当K位的所有可能取值都枚举，回到上一 位，枚举第K-1位的下一种取值
假设字符串长度固定为3，可以这样写
#include<stdio.h> ch("%s\n",d+1);} void dfs3(){ d[3]='A'; dfs4(); d[3]='B'; dfs4(); d[3]='C'; dfs4(); } void dfs2(){ d[2]='A'; dfs3(); d[2]='B'; dfs3(); d[2]='C'; dfs3(); }