深度优先搜索与回溯算法课件.ppt

《深度优先搜索与回溯算法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、深度优先搜索与回溯算法回溯是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。如迷宫问题：进入迷宫后，先随意选择一个前进方向，一步步向前试探前进,如果碰到死胡同，说明前进方向已无路可走，这时，首先看其它方向是否还有路可走，如果有路可走，则沿该方向再向前试探；

2、如果已无路可走，则返回一步，再看其它方向是否还有路可走；如果有路可走，则沿该方向再向前试探。按此原则不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。回溯法算法框架Proceduredfs(s)//访问状态sBeginif边界thenbegin判断是否为目标状态；exit;end;fori：=状态变换规则数beginsi=s+规则I保存局面dfs（si）还原局面end；End;【例1】设有n个整数的集合｛1,2,…,n｝，从中取出任意r个数（r

3、，r=2。那么有3种可能，（1,2），（1,3），（2,3）【例2】任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。当n=7共14种拆分方法：7=1+1+1+1+1+1+17=1+1+1+1+1+27=1+1+1+1+37=1+1+1+2+27=1+1+1+47=1+1+2+37=1+1+57=1+2+2+27=1+2+47=1+3+37=1+67=2+2+37=2+57=3+4total=14【例3】素数环:从1到n（<=20）这n个数摆成一个环，要求相邻的两个数的和是一个素数。【算法分析

4、】非常明显，这是一道回溯的题目。从1开始，每个空位有20种可能，只要填进去的数合法：与前面的数不相同；与左边相邻的数的和是一个素数。第20个数还要判断和第1个数的和是否素数。【例4】八皇后问题：要在国际象棋棋盘中放八个皇后，使任意两个皇后都不能互相吃。（提示：皇后能吃同一行、同一列、同一对角线的任意棋子。）１２３４５６７８１２３４５６７８｜／＼｜／＼｜／＼｜／－－－▲－－－－／｜＼／｜＼／｜＼【例5】马的遍历中国象棋半张棋盘如图4（a）所示。马自左下角往右上角跳。今规定只许往右跳，不许往左跳。比如图4（a）

5、中所示为一种跳行路线，并将所经路线打印出来。打印格式为：0,0->2,1->3,3->1,4->3,5->2,7->4,8…【例6】数的划分(NOIP2001)【问题描述】将整数n分成k份，且每份不能为空，任意两种分法不能相同(不考虑顺序)。例如:n=7,k=3,下面三种分法被认为是相同的。1，1，5；1，5，1；5，1，1；问有多少种不同的分法。【输入格式】n,k(6

6、;2,2,3说明部分不必输出}【例7】跳马问题。在5*5格的棋盘上，有一只中国象棋的马，从（1,1）点出发，按日字跳马，它可以朝8个方向跳，但不允许出界或跳到已跳过的格子上，要求在跳遍整个棋盘。输出前5个方案及总方案数。输出格式示例：1  16  21  10  2520 11  24  15  2217 2   19  6   912 7   4   23  143  18  13  8   5【课堂练习】1、输出自然数1到n所有不重复的排列，即n的全排列。【参考过程】intSearch(inti){In

7、tj;for(j=1;j<=n;j++)if(b[j]){a[i]=j;b[j]=false;if(I

8、。由于此时b[i]只能取k+1至n-r+i，对j=k+1,k+2,…,n-r+i，使b[i]:=j，再调用过程Search(i+1,j)，形成递归调用。直至i的值大于r时，就可以在b中构成一种组合并输出。3、输出字母a、b、c、d，4个元素全排列的每一种排列。4、显示从前m个大写英文字母中取n个不同字母的所有种排列。5、有A、B、C、D、E五本书，要分给张、王、刘、赵、钱五位同学，每人只能选一本，事先让每人把自已