第二讲回溯法精选PPT.ppt

《第二讲回溯法精选PPT.ppt》由会员分享，可在线阅读，更多相关《第二讲回溯法精选PPT.ppt（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二讲回溯法第1页，本讲稿共27页关于搜索n n人类的思维过程既是一个搜索过程。人类的思维过程既是一个搜索过程。n n先来看一个智力游戏先来看一个智力游戏第2页，本讲稿共27页传教士与野人n n有三个传教士和三个野人渡河，河边有有三个传教士和三个野人渡河，河边有一条船，每次只能乘坐一条船，每次只能乘坐2人，为了传教士人，为了传教士的安全，应如何规划渡船方案，使得任的安全，应如何规划渡船方案，使得任何时刻，在河的两岸及船上，传教士的何时刻，在河的两岸及船上，传教士的人数不能少于野人数。人数不能少于野人数。第3页，本讲稿共27页第4页，本讲稿共27页搜索分类第5页，本讲稿共27页基本思想n n回溯

2、法是一种通用性解法，可以将回溯法看作是带优化回溯法是一种通用性解法，可以将回溯法看作是带优化回溯法是一种通用性解法，可以将回溯法看作是带优化回溯法是一种通用性解法，可以将回溯法看作是带优化的穷举法。的穷举法。的穷举法。的穷举法。n n回溯法的基本思想是在一棵含有问题全部可能解的状态空间树回溯法的基本思想是在一棵含有问题全部可能解的状态空间树回溯法的基本思想是在一棵含有问题全部可能解的状态空间树回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度优先搜索，解为叶子结点。搜索过程中，每到达一上进行深度优先搜索，解为叶子结点。搜索过程中，每到达一上进行深度优先搜索，解为叶子结点。搜索过程

3、中，每到达一上进行深度优先搜索，解为叶子结点。搜索过程中，每到达一个结点时，个结点时，个结点时，个结点时，则判断该结点为根的子树是否含有问题的解则判断该结点为根的子树是否含有问题的解则判断该结点为根的子树是否含有问题的解则判断该结点为根的子树是否含有问题的解，如，如，如，如果可以确定该子树中不含有问题的解，则放弃对该子树的搜索，果可以确定该子树中不含有问题的解，则放弃对该子树的搜索，果可以确定该子树中不含有问题的解，则放弃对该子树的搜索，果可以确定该子树中不含有问题的解，则放弃对该子树的搜索，退回到上层父结点，继续下一步深度优先搜索过程。退回到上层父结点，继续下一步深度优先搜索过程。退回到上层

4、父结点，继续下一步深度优先搜索过程。退回到上层父结点，继续下一步深度优先搜索过程。n n在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在搜索过程，而是在搜索过程，而是在搜索过程，而是在搜索过程，逐步构造出状态空间树逐步构造出状态空间树逐步构造出状态空间树逐步构造出状态空间树，即边搜索，边构造。，即边搜索，边构造。，即边搜索，边构造。，即边搜索，边构造。第6页，本讲稿共27页第7页，本讲稿共27页应用步骤n n1、确定问题状

5、态结构；、确定问题状态结构；n n2、分析问题状态空间树；、分析问题状态空间树；n n3、确定深度搜索与回溯规则；、确定深度搜索与回溯规则；n n4、确定解状态判别规则；、确定解状态判别规则；第8页，本讲稿共27页二个问题n n八皇后问题八皇后问题n n全排列问题全排列问题第9页，本讲稿共27页N皇后问题n n问题：在一个问题：在一个问题：在一个问题：在一个nnnn的棋盘上布置的棋盘上布置的棋盘上布置的棋盘上布置n n个王后，使其相互不能攻击，即每行、个王后，使其相互不能攻击，即每行、个王后，使其相互不能攻击，即每行、个王后，使其相互不能攻击，即每行、每列，每斜线都只有一个皇后；每列，每斜线都

6、只有一个皇后；每列，每斜线都只有一个皇后；每列，每斜线都只有一个皇后；n n问题的状态问题的状态问题的状态问题的状态即棋盘的布局状态，状态空间树的根为空棋盘，即棋盘的布局状态，状态空间树的根为空棋盘，即棋盘的布局状态，状态空间树的根为空棋盘，即棋盘的布局状态，状态空间树的根为空棋盘，每个布局的下一每个布局的下一每个布局的下一每个布局的下一步可能布局步可能布局步可能布局步可能布局为该布局结点的子结点；为该布局结点的子结点；为该布局结点的子结点；为该布局结点的子结点；n n由于可以预知，在每行中有且只有一个王后，因此为了简化状态空间由于可以预知，在每行中有且只有一个王后，因此为了简化状态空间由于可

7、以预知，在每行中有且只有一个王后，因此为了简化状态空间由于可以预知，在每行中有且只有一个王后，因此为了简化状态空间树，采用逐行布局的方式，即每个布局有树，采用逐行布局的方式，即每个布局有树，采用逐行布局的方式，即每个布局有树，采用逐行布局的方式，即每个布局有n n个子结点；个子结点；个子结点；个子结点；第10页，本讲稿共27页N后问题n n回溯过程分析回溯过程分析n n1 1、从空棋盘起，逐行放置棋子。、从空棋盘起，逐行放置棋子。、从空棋盘起，逐行放置棋子。、从空棋盘起，逐行放置棋子。n n2 2、每在一个布局中放下一个棋子，即推、每在一个布局中放下一个棋子，即推、每在一个布局中放下一个棋子，

8、即推、每在一个布局中放下一个棋子，即推演到一个新的布局。演到一个新的布局。演到一个新的布局。演到一个新的布局。n n3 3、如果当前行上没有可合法放置棋子的、如果当前行上没有可合法放置棋子的、如果当前行上没有可合法放置棋子的、如果当前行上没有可合法放置棋子的位置，则回溯到上一行，重新布放上一行位置，则回溯到上一行，重新布放上一行位置，则回溯到上一行，重新布放上一行位置，则回溯到上一行，重新布放上一行的棋子。的棋子。的棋子。的棋子。第11页，本讲稿共27页N后问题n n算法描述算法描述算法描述算法描述n n初始化空棋盘（起始状态）；初始化空棋盘（起始状态）；初始化空棋盘（起始状态）；初始化空棋盘

9、（起始状态）；n n从第一行开始准备放子，直至第一行出现回溯从第一行开始准备放子，直至第一行出现回溯从第一行开始准备放子，直至第一行出现回溯从第一行开始准备放子，直至第一行出现回溯n n 在当前行在当前行在当前行在当前行r r中查找下一个可以放置王后的位置中查找下一个可以放置王后的位置中查找下一个可以放置王后的位置中查找下一个可以放置王后的位置n n 如果找到了可以摆放的位置如果找到了可以摆放的位置如果找到了可以摆放的位置如果找到了可以摆放的位置n n放下一个子放下一个子放下一个子放下一个子n n如果已经是最后一行如果已经是最后一行如果已经是最后一行如果已经是最后一行n n得到一个解得到一个解

10、得到一个解得到一个解n n撤掉该子，继续寻找下一个解撤掉该子，继续寻找下一个解撤掉该子，继续寻找下一个解撤掉该子，继续寻找下一个解n n否则（未到最后一行）否则（未到最后一行）否则（未到最后一行）否则（未到最后一行）n n准备处理下一行准备处理下一行准备处理下一行准备处理下一行n n 否则（没有找到可以摆放的位置）否则（没有找到可以摆放的位置）否则（没有找到可以摆放的位置）否则（没有找到可以摆放的位置）n n回溯到上一行，并撤掉该行的棋子回溯到上一行，并撤掉该行的棋子回溯到上一行，并撤掉该行的棋子回溯到上一行，并撤掉该行的棋子第12页，本讲稿共27页第13页，本讲稿共27页算法伪码n n得到求

11、解皇后问题的算法如下：得到求解皇后问题的算法如下：得到求解皇后问题的算法如下：得到求解皇后问题的算法如下：输入棋盘大小值输入棋盘大小值输入棋盘大小值输入棋盘大小值n n；m=0;m=0;good=1;good=1;dodoif(good)if(good)if(m=n)if(m=n)输出解；输出解；输出解；输出解；改变之，形成下一个候选解改变之，形成下一个候选解改变之，形成下一个候选解改变之，形成下一个候选解;elseelse扩展当前候选接至下一列；扩展当前候选接至下一列；扩展当前候选接至下一列；扩展当前候选接至下一列；elseelse改变之，形成下一个候选解；改变之，形成下一个候选解；改变之，

12、形成下一个候选解；改变之，形成下一个候选解；good=good=检查当前候选解的合理性；检查当前候选解的合理性；检查当前候选解的合理性；检查当前候选解的合理性；while(m!=0);while(m!=0);第14页，本讲稿共27页引入辅助变量n n一维数组（一维数组（一维数组（一维数组（colcol），值），值），值），值colcol表示在棋盘第表示在棋盘第表示在棋盘第表示在棋盘第i i列、列、列、列、colcol行有一个皇后。例如：行有一个皇后。例如：行有一个皇后。例如：行有一个皇后。例如：col3=4col3=4，就表示在棋盘的，就表示在棋盘的，就表示在棋盘的，就表示在棋盘的第第第第3

13、3列、第列、第列、第列、第4 4行上有一个皇后。另外，为了使程序在行上有一个皇后。另外，为了使程序在行上有一个皇后。另外，为了使程序在行上有一个皇后。另外，为了使程序在找完了全部解后回溯到最初位置，设定找完了全部解后回溯到最初位置，设定找完了全部解后回溯到最初位置，设定找完了全部解后回溯到最初位置，设定col0col0的初的初的初的初值为值为值为值为0 0当回溯到第当回溯到第当回溯到第当回溯到第0 0列时，说明程序已求得全部解，列时，说明程序已求得全部解，列时，说明程序已求得全部解，列时，说明程序已求得全部解，结束程序运行。结束程序运行。结束程序运行。结束程序运行。n n数组数组数组数组aa，

14、akak表示第表示第表示第表示第k k行上还没有皇后；行上还没有皇后；行上还没有皇后；行上还没有皇后；n n数组数组数组数组bb，bkbk表示第表示第表示第表示第k k列右高左低斜线上没有皇列右高左低斜线上没有皇列右高左低斜线上没有皇列右高左低斜线上没有皇后；后；后；后；n n数组数组数组数组cc，ckck表示第表示第表示第表示第k k列左高右低斜线上没有皇列左高右低斜线上没有皇列左高右低斜线上没有皇列左高右低斜线上没有皇后；后；后；后；第15页，本讲稿共27页nn【程序】【程序】【程序】【程序】#include#include#include#include#defineMAXN20#def

15、ineMAXN20intn,m,good;intn,m,good;intcolMAXN+1,aMAXN+1,b2*MAXN+1,c2*MAXN+1;intcolMAXN+1,aMAXN+1,b2*MAXN+1,c2*MAXN+1;voidmain()voidmain()intj;intj;charawn;charawn;printf(“Entern:“);scanf(“%d”,&n);printf(“Entern:“);scanf(“%d”,&n);for(j=0;j=n;j+)aj=1;for(j=0;j=n;j+)aj=1;for(j=0;j=2*n;j+)cbj=cj=1;for(j=0

16、;j=2*n;j+)cbj=cj=1;m=1;col1=1;good=1;col0=0;m=1;col1=1;good=1;col0=0;dodoif(good)if(good)if(m=n)if(m=n)printf(“printf(“列列列列tt行行行行”);”);for(j=1;j=n;j+)for(j=1;j=n;j+)printf(“%3dt%dn”,j,colj);printf(“%3dt%dn”,j,colj);printf(“Enteracharacter(Q/qforexit)!n”);printf(“Enteracharacter(Q/qforexit)!n”);scanf

17、(“%c”,&awn);scanf(“%c”,&awn);if(awn=Q|awn=q)exit(0);if(awn=Q|awn=q)exit(0);while(colm=n)while(colm=n)m-;m-;acolm=bm+colm=cn+m-colm=1;acolm=bm+colm=cn+m-colm=1;colm+;colm+;elseelseacolm=bm+colm=cn+m-colm=0;acolm=bm+colm=cn+m-colm=0;col+m=1;col+m=1;elseelsewhile(colm=n)while(colm=n)m-;m-;acolm=bm+colm

18、=cn+m-colm=1;acolm=bm+colm=cn+m-colm=1;colm+;colm+;good=acolm&bm+colm&cn+m-colm;good=acolm&bm+colm&cn+m-colm;while(m!=0);while(m!=0);第16页，本讲稿共27页全排列问题n n问题问题问题问题n n生成生成生成生成1.n1.n的全排列。的全排列。的全排列。的全排列。n n问题状态问题状态问题状态问题状态n n可以将一个局部排列看作一个问题状态。可以将一个局部排列看作一个问题状态。可以将一个局部排列看作一个问题状态。可以将一个局部排列看作一个问题状态。n n问题状态空

19、间树问题状态空间树问题状态空间树问题状态空间树n n由空排列出发，在一个局部排列上每增排一位数字，即可得由空排列出发，在一个局部排列上每增排一位数字，即可得由空排列出发，在一个局部排列上每增排一位数字，即可得由空排列出发，在一个局部排列上每增排一位数字，即可得到新的一个排列。所有局部排列之间的推导关系即可构成一到新的一个排列。所有局部排列之间的推导关系即可构成一到新的一个排列。所有局部排列之间的推导关系即可构成一到新的一个排列。所有局部排列之间的推导关系即可构成一棵问题状态空间树。棵问题状态空间树。棵问题状态空间树。棵问题状态空间树。n n辅助向量设计辅助向量设计辅助向量设计辅助向量设计n n

20、可设置辅助向量可设置辅助向量可设置辅助向量可设置辅助向量DD1.n1.n，其中，其中，其中，其中DDi i表示表示表示表示i i是否已经被排列。是否已经被排列。是否已经被排列。是否已经被排列。第17页，本讲稿共27页全排列问题n n算法描述算法描述算法描述算法描述n n初始化空排列，开始逐位进行排列；初始化空排列，开始逐位进行排列；初始化空排列，开始逐位进行排列；初始化空排列，开始逐位进行排列；n n循环，直到第一位出现回溯循环，直到第一位出现回溯循环，直到第一位出现回溯循环，直到第一位出现回溯n n寻找当前位的下一个可排列数字；寻找当前位的下一个可排列数字；寻找当前位的下一个可排列数字；寻找

21、当前位的下一个可排列数字；n n若存在可排列数字若存在可排列数字若存在可排列数字若存在可排列数字n n排列排列排列排列n n若已排列满，则若已排列满，则若已排列满，则若已排列满，则n n输出一个排列，并删除该位（准备下一个排列）输出一个排列，并删除该位（准备下一个排列）输出一个排列，并删除该位（准备下一个排列）输出一个排列，并删除该位（准备下一个排列）n n否则否则否则否则n n准备排列下一位准备排列下一位准备排列下一位准备排列下一位n n否则（无可排列数字）否则（无可排列数字）否则（无可排列数字）否则（无可排列数字）n n退回上一位，并删除所排列数字退回上一位，并删除所排列数字退回上一位，并

22、删除所排列数字退回上一位，并删除所排列数字第18页，本讲稿共27页回溯法的分析n n一个可以用回溯法求解的问题，通常可以表述为以下形式：一个可以用回溯法求解的问题，通常可以表述为以下形式：一个可以用回溯法求解的问题，通常可以表述为以下形式：一个可以用回溯法求解的问题，通常可以表述为以下形式：对由对由对由对由n n元组元组元组元组(x(x1 1,x,x2 2,x,xn n)组成的状态空间组成的状态空间组成的状态空间组成的状态空间E=(xE=(x1 1,x,xn n)，给定，给定，给定，给定n n元元元元组上的一个约束集组上的一个约束集组上的一个约束集组上的一个约束集DD，求：，求：，求：，求：E

23、 E中满足中满足中满足中满足DD的全部约束条件的所有的全部约束条件的所有的全部约束条件的所有的全部约束条件的所有n n元组。元组。元组。元组。将将将将E E中满足中满足中满足中满足DD的全部约束条件的一个的全部约束条件的一个的全部约束条件的一个的全部约束条件的一个n n元组称为问题的一个解。元组称为问题的一个解。元组称为问题的一个解。元组称为问题的一个解。n n通常约束集通常约束集通常约束集通常约束集DD具有完备性，即若具有完备性，即若具有完备性，即若具有完备性，即若i i元组元组元组元组(x(x1 1xxi i)满足满足满足满足DD中仅涉及中仅涉及中仅涉及中仅涉及x x1 1xxi i的所的

24、所的所的所有约束，则有约束，则有约束，则有约束，则(x(x1 1xxj j)ji)jj)ij也不能满足也不能满足也不能满足也不能满足DD中涉及中涉及中涉及中涉及x x1 1xxi i的约束，不必再继续的约束，不必再继续的约束，不必再继续的约束，不必再继续搜索问题的解。搜索问题的解。搜索问题的解。搜索问题的解。第19页，本讲稿共27页回溯法的分析n n回溯求解的效率在很大程度上依赖于：回溯求解的效率在很大程度上依赖于：产生局部解的时间；产生局部解的时间；计算约束所需的时间；计算约束所需的时间；满足局部约束的解的个数；满足局部约束的解的个数；n n通常可以应用重排原理，先搜索分支较通常可以应用重排

25、原理，先搜索分支较少的局部解，在约束不满足时，可以裁少的局部解，在约束不满足时，可以裁剪去较多的搜索分支，从而提高搜索效剪去较多的搜索分支，从而提高搜索效率。率。第20页，本讲稿共27页一般图搜索n n回溯搜索：只保留从初始态到当前态的回溯搜索：只保留从初始态到当前态的一条路径一条路径n n图搜索：保留所有搜索过的路径图搜索：保留所有搜索过的路径n n实际上，图搜索测量是实现从一个隐含图中，实际上，图搜索测量是实现从一个隐含图中，实际上，图搜索测量是实现从一个隐含图中，实际上，图搜索测量是实现从一个隐含图中，生成一部分确实含有一个目标节点的显示表生成一部分确实含有一个目标节点的显示表生成一部分

26、确实含有一个目标节点的显示表生成一部分确实含有一个目标节点的显示表示的子图搜索过程。示的子图搜索过程。示的子图搜索过程。示的子图搜索过程。第21页，本讲稿共27页启发式搜索算法n n利用知识来引导搜索，达到减少搜索范围，减低问利用知识来引导搜索，达到减少搜索范围，减低问利用知识来引导搜索，达到减少搜索范围，减低问利用知识来引导搜索，达到减少搜索范围，减低问题复杂度的目的，希望引入启发知识，在保证找到题复杂度的目的，希望引入启发知识，在保证找到题复杂度的目的，希望引入启发知识，在保证找到题复杂度的目的，希望引入启发知识，在保证找到最优解的情况下，尽可能减少搜索范围，提高搜索最优解的情况下，尽可能

27、减少搜索范围，提高搜索最优解的情况下，尽可能减少搜索范围，提高搜索最优解的情况下，尽可能减少搜索范围，提高搜索效率。效率。效率。效率。n n强：降低搜索工作量，但可能导致找不到最优解强：降低搜索工作量，但可能导致找不到最优解强：降低搜索工作量，但可能导致找不到最优解强：降低搜索工作量，但可能导致找不到最优解n n弱：一般导致工作量加大，极限情况下变为盲目弱：一般导致工作量加大，极限情况下变为盲目弱：一般导致工作量加大，极限情况下变为盲目弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解搜索，但可能可以找到最优解搜索，但可能可以找到最优解搜索，但可能可以找到最优解第22页，本讲

28、稿共27页n n小结小结小结小结回溯方法的步骤如下：回溯方法的步骤如下：回溯方法的步骤如下：回溯方法的步骤如下：1)1)定义一个解空间，它包含问题的解。定义一个解空间，它包含问题的解。定义一个解空间，它包含问题的解。定义一个解空间，它包含问题的解。2)2)用适于搜索的方式组织该空间。用适于搜索的方式组织该空间。用适于搜索的方式组织该空间。用适于搜索的方式组织该空间。3)3)用深度优先法搜索该空间，利用限界函数避免移动到不可能产生解的子空间。用深度优先法搜索该空间，利用限界函数避免移动到不可能产生解的子空间。用深度优先法搜索该空间，利用限界函数避免移动到不可能产生解的子空间。用深度优先法搜索该空

29、间，利用限界函数避免移动到不可能产生解的子空间。回溯算法的一个有趣的特性是在搜索执行的同时产生解空间。在搜索期间的任何时刻，仅保回溯算法的一个有趣的特性是在搜索执行的同时产生解空间。在搜索期间的任何时刻，仅保回溯算法的一个有趣的特性是在搜索执行的同时产生解空间。在搜索期间的任何时刻，仅保回溯算法的一个有趣的特性是在搜索执行的同时产生解空间。在搜索期间的任何时刻，仅保留从开始节点到当前留从开始节点到当前留从开始节点到当前留从开始节点到当前E-E-节点的路径。因此，回溯算法的空间需求为节点的路径。因此，回溯算法的空间需求为节点的路径。因此，回溯算法的空间需求为节点的路径。因此，回溯算法的空间需求为

30、OO（从开始节点起最长路（从开始节点起最长路（从开始节点起最长路（从开始节点起最长路径的长度）。这个特性非常重要，因为解空间的大小通常是最长路径长度的指数或阶乘。所径的长度）。这个特性非常重要，因为解空间的大小通常是最长路径长度的指数或阶乘。所径的长度）。这个特性非常重要，因为解空间的大小通常是最长路径长度的指数或阶乘。所径的长度）。这个特性非常重要，因为解空间的大小通常是最长路径长度的指数或阶乘。所以如果要存储全部解空间的话，再多的空间也不够用以如果要存储全部解空间的话，再多的空间也不够用以如果要存储全部解空间的话，再多的空间也不够用以如果要存储全部解空间的话，再多的空间也不够用 第23页，

31、本讲稿共27页经典问题n n迷宫老鼠迷宫老鼠n n0/1背包问题背包问题n n旅行商问题旅行商问题第24页，本讲稿共27页练习n n1.1.找出所有从找出所有从找出所有从找出所有从mm个元素中选取个元素中选取个元素中选取个元素中选取n(n=m)n(n=m)元素的组合。元素的组合。元素的组合。元素的组合。n n2.2.设有设有设有设有A,B,C,D,E5A,B,C,D,E5人从事人从事人从事人从事j1,j2,j3,j4,j55j1,j2,j3,j4,j55项工作每人只能从项工作每人只能从项工作每人只能从项工作每人只能从事一项事一项事一项事一项,它们的效益表如下。求最佳安排它们的效益表如下。求最佳

32、安排它们的效益表如下。求最佳安排它们的效益表如下。求最佳安排,使效益最高使效益最高使效益最高使效益最高.第25页，本讲稿共27页n n3.N3.N个数中找出个数中找出个数中找出个数中找出MM个数个数个数个数(从键盘上输入正整数从键盘上输入正整数从键盘上输入正整数从键盘上输入正整数N,MN,M后再输入后再输入后再输入后再输入NN个正个正个正个正数数数数),),要求从要求从要求从要求从NN个数中找出若干个数个数中找出若干个数个数中找出若干个数个数中找出若干个数,使它们的和为使它们的和为使它们的和为使它们的和为M,M,把满足条件的把满足条件的把满足条件的把满足条件的数组找出来数组找出来数组找出来数组找出来,并统计组数并统计组数并统计组数并统计组数.n n4.4.地图着色。如下图地图着色。如下图地图着色。如下图地图着色。如下图1212个区域用个区域用个区域用个区域用4 4种颜色着色要求相邻的区域种颜色着色要求相邻的区域种颜色着色要求相邻的区域种颜色着色要求相邻的区域着不同的颜色着不同的颜色着不同的颜色着不同的颜色第26页，本讲稿共27页n n5.将任意一正整数将任意一正整数(1n100)分解成若干分解成若干正整数的和正整数的和.如如:4=1+1+1+1=2+1+1=2+2=3+1第27页，本讲稿共27页