第二讲回溯法课件

关于搜索人类的思维过程既是一个搜索过程。先来看一个智力游戏关于搜索人类的思维过程既是一个搜索过程。传教士与野人有三个传教士和三个野人渡河，河边有一条船，每次只能乘坐2人，为了传教士的安全，应如何规划渡船方案，使得任何时刻，在河的两岸及船上，传教士的人数不能少于野人数。 传教士与野人有三个传教士和三个野人渡河，河边有一条船，每次只第二讲回溯法课件搜索分类搜索分类基本思想回溯法是一种通用性解法，可以将回溯法看作是带优化的穷举法。回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度优先搜索，解为叶子结点。搜索过程中，每到达一个结点时，则判断该结点为根的子树是否含有问题的解，如果可以确定该子树中不含有问题的解，则放弃对该子树的搜索，退回到上层父结点，继续下一步深度优先搜索过程。在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在搜索过程，逐步构造出状态空间树，即边搜索，边构造。基本思想回溯法是一种通用性解法，可以将回溯法看作是带优化的穷第二讲回溯法课件应用步骤1、确定问题状态结构；2、分析问题状态空间树；3、确定深度搜索与回溯规则；4、确定解状态判别规则；应用步骤1、确定问题状态结构；二个问题八皇后问题全排列问题二个问题八皇后问题N皇后问题问题：在一个n×n的棋盘上布置n个王后，使其相互不能攻击，即每行、每列，每斜线都只有一个皇后；问题的状态即棋盘的布局状态，状态空间树的根为空棋盘，每个布局的下一步可能布局为该布局结点的子结点；由于可以预知，在每行中有且只有一个王后，因此为了简化状态空间树，采用逐行布局的方式，即每个布局有n个子结点；N皇后问题问题：在一个n×n的棋盘上布置n个王后，使其相互不N后问题回溯过程分析1、从空棋盘起，逐行放置棋子。2、每在一个布局中放下一个棋子，即推演到一个新的布局。3、如果当前行上没有可合法放置棋子的位置，则回溯到上一行，重新布放上一行的棋子。N后问题回溯过程分析N后问题算法描述初始化空棋盘（起始状态）；从第一行开始准备放子，直至第一行出现回溯在当前行r中查找下一个可以放置王后的位置

如果找到了可以摆放的位置放下一个子

如果已经是最后一行得到一个解撤掉该子，继续寻找下一个解

否则（未到最后一行）准备处理下一行

否则（没有找到可以摆放的位置）回溯到上一行，并撤掉该行的棋子N后问题算法描述第二讲回溯法课件算法伪码得到求解皇后问题的算法如下：

{

输入棋盘大小值n；

m=0;

good=1;

do{

if(good)

if(m==n)

{

输出解；

改变之，形成下一个候选解;

}

else

扩展当前候选接至下一列；

else

改变之，形成下一个候选解；

good=检查当前候选解的合理性；

}while(m!=0);

}算法伪码得到求解皇后问题的算法如下：

{

输入引入辅助变量一维数组（col[]），值col表示在棋盘第i列、col行有一个皇后。例如：col[3]=4，就表示在棋盘的第3列、第4行上有一个皇后。另外，为了使程序在找完了全部解后回溯到最初位置，设定col[0]的初值为0当回溯到第0列时，说明程序已求得全部解，结束程序运行。数组a[]，a[k]表示第k行上还没有皇后；数组b[]，b[k]表示第k列右高左低斜线上没有皇后；数组c[]，c[k]表示第k列左高右低斜线上没有皇后；引入辅助变量一维数组（col[]），值col表示在棋盘第i【程序】

#include

<stdio.h>

#include

<stdlib.h>

#define

MAXN

20

intn,m,good;

intcol[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*MAXN+1];

voidmain()

{

intj;

charawn;

printf(“Entern:

“);

scanf(“%d”,&n);

for(j=0;j<=n;j++)

a[j]=1;

for(j=0;j<=2*n;j++)

cb[j]=c[j]=1;

m=1;

col[1]=1;

good=1;

col[0]=0;

do{

if(good)

if(m==n)

{

printf(“列\t行”);

for(j=1;j<=n;j++)

printf(“%3d\t%d\n”,j,col[j]);

printf(“Enteracharacter(Q/qforexit)!\n”);

scanf(“%c”,&awn);

if(awn==’Q’||awn==’q’)

exit(0);

while(col[m]==n)

{

m--;

a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;

}

col[m]++;

}

else

{

a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=0;

col[++m]=1;

}

else

{

while(col[m]==n)

{

m--;

a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;

}

col[m]++;

}

good=a[col[m]]&&b[m+col[m]]&&c[n+m-col[m]];

}while(m!=0);

}

【程序】

#include

<stdio.h>

全排列问题问题生成1..n的全排列。问题状态可以将一个局部排列看作一个问题状态。问题状态空间树由空排列出发，在一个局部排列上每增排一位数字，即可得到新的一个排列。所有局部排列之间的推导关系即可构成一棵问题状态空间树。辅助向量设计可设置辅助向量D1..n，其中Di表示i是否已经被排列。全排列问题问题全排列问题算法描述初始化空排列，开始逐位进行排列；循环，直到第一位出现回溯寻找当前位的下一个可排列数字；若存在可排列数字排列若已排列满，则输出一个排列，并删除该位（准备下一个排列）否则准备排列下一位否则（无可排列数字）退回上一位，并删除所排列数字全排列问题算法描述回溯法的分析一个可以用回溯法求解的问题，通常可以表述为以下形式：

对由n元组(x1,x2,…,xn)组成的状态空间E={(x1,…,xn)}，给定n元组上的一个约束集D，求：E中满足D的全部约束条件的所有n元组。将E中满足D的全部约束条件的一个n元组称为问题的一个解。通常约束集D具有完备性，即若i元组(x1…xi)满足D中仅涉及x1…xi的所有约束，则(x1…xj)j<i也满足D中仅涉及x1…xj的所有约束；也就是说，若(x1…xj)不能满足D中所有涉及x1…xj的约束，则任何以(x1…xj)为前缀的i元组(x1…xi)i>j也不能满足D中涉及x1…xi的约束，不必再继续搜索问题的解。回溯法的分析一个可以用回溯法求解的问题，通常可以表述为以下形回溯法的分析回溯求解的效率在很大程度上依赖于：

产生局部解的时间；

计算约束所需的时间；

满足局部约束的解的个数；通常可以应用重排原理，先搜索分支较少的局部解，在约束不满足时，可以裁剪去较多的搜索分支，从而提高搜索效率。回溯法的分析回溯求解的效率在很大程度上依赖于：

产生局部解的一般图搜索回溯搜索：只保留从初始态到当前态的一条路径图搜索：保留所有搜索过的路径实际上，图搜索测量是实现从一个隐含图中，生成一部分确实含有一个目标节点的显示表示的子图搜索过程。一般图搜索回溯搜索：只保留从初始态到当前态的一条路径启发式搜索算法利用知识来引导搜索，达到减少搜索范围，减低问题复杂度的目的，希望引入启发知识，在保证找到最优解的情况下，尽可能减少搜索范围，提高搜索效率。强：降低搜索工作量，但可能导致找不到最优解弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解启发式搜索算法利用知识来引导搜索，达到减少搜索范围，减低问题小结

回溯方法的步骤如下：

1)定义一个解空间，它包含问题的解。

2)用适于搜索的方式组织该空间。

3)用深度优先法搜索该空间，利用限界函数避免移动到不可能产生解的子空间。

回溯算法的一个有趣的特性是在搜索执行的同时产生解空间。在搜索期间的任何时刻，仅保留从开始节点到当前E-节点的路径。因此，回溯算法的空间需求为O（从开始节点起最长路径的长度）。这个特性非常重要，因为解空间的大小通常是最长路径长度的指数或阶乘。所以如果要存储全部解空间的话，再多的空间也不够用小结

回溯方法的步骤如下：

1)定义一个解空间，它包含经典问题[迷宫老鼠][0/1背包问题][旅行商问题]经典问题[迷宫老鼠]练习1.找出所有从m个元素中选取n(n<=m)元素的组合。2.设有A,B,C,D,E5人从事j1,j2,j3,j4,j55项工作每人只能从事一项,它们的效益表如下。求最佳安排,使效益最高.练习1.找出所有从m个元素中选取n(n<=m)元素的组合。3.N个数中找出M个数(从键盘上输入