算法设计与分析实用教程-电子教案-杨克昌第5章 回溯法.ppt

《算法设计与分析实用教程-电子教案-杨克昌第5章 回溯法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、教学要求了解回溯算法的概念与回溯设计要领了解一般回溯与递归回溯的异同掌握应用回溯算法求解桥本分数式、数码串珠、逐位整除数以及情侣拍照等典型案例本章重点理解回溯法“向前走，碰壁回头”的实现第5章回溯法5.1回溯法概述5.1.1回溯的概念(1)回溯法（Backtrackmethod）有“通用解题法”之美称，是一种比枚举“聪明”的效率更高的搜索技术。(2)回溯法是一种试探求解的方法：通过对问题的归纳分析，找出求解问题的一个线索，沿着这一线索往前试探，若试探成功，即得到解；若试探失败，就逐步往回退，换其他路线再往前试探。(3)回溯法可以形象地概括

2、为“向前走，碰壁回头”，若再往前走不可能得到解，就回溯，退一步另找线路，这样可省去大量的无效操作，提高搜索效率。（4）回溯实现回溯法的试探搜索，是一种组织得井井有条的、能避免一些不必要搜索的枚举式搜索。回溯法在问题的解空间树中，从根结点出发搜索解空间树，搜索至解空间树的任意一点，先判断该结点是否包含问题的解；如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其父结点回溯；否则，进入该子树，继续搜索。从解的角度理解，回溯法将问题的候选解按某种顺序进行枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解。在回溯法中，放弃当前候选解，寻

3、找下一个候选解的过程称为回溯。若当前候选解除了不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。通过例5-1“4皇后问题的回溯”理解回溯过程的实现。1．回溯的数学概括对于已知的由n元组(x1,x2,…,xn)组成的一个状态空间E={(x1,x2,…,xn)

4、xi∈si,i=1,2,…,n}，给定关于n元组中的约束集D，要求E中满足D的全部约束条件的所有n元组。对于约束集D具有完备性的问题P，一旦检测断定某个j元组(x1,x2,…,xj)违反

5、D中仅涉及x1,x2,…,xj的一个约束，就可以肯定，以(x1,x2,…,xj)为前缀的任何n元组(x1,x2,…,xj,xj+1,…,xn)都不会是问题P的解，因而就不必去搜索它们，省略了对部分元素(xj+1,…,xn)的操作与测试。5.1.2回溯的数学概括与效益分析2.回溯法的效益分析应用回溯设计求解实际问题，由于解空间的结构差异，很难精确计算与估计回溯产生的结点数，这是分析回溯法效率时遇到的主要困难。回溯法因“适时回头”省去了部分结点的操作与检测，实际操作的结点数通常只有解空间所有结点数的一小部分，这也是回溯法的探索效率高于枚举的原因所

6、在。对于元组长度为n的问题，若其状态空间树中结点总数为n!，则回溯算法的最坏情形的时间复杂度可达O(p(n)n!)；若其状态空间树中结点总数为2^n，则回溯算法的最坏情形的时间复杂度可达O(p(n)2^n)，其中p(n)为n的多项式。回溯法实际产生的结点数通常只有解空间所有结点数的一部分，这也是回溯法的探索效率大大高于枚举的原因所在。可见回溯法不失为一种快速有效的算法。1.迭代回溯迭代回溯是非递归回溯，通过迭代式实施回溯。框架描述：i=1;a[i]=<元素初值>;while(1){for(g=1,k=i-1;k>=1;k--)if(<约束条件

7、1>)g=0;//检测约束条件,不满足则返回if(g&&<约束条件2>)printf(a[1：m]);//输出解if(i;continue;}while(a[i]=<回溯点>&&i>1)i--;//实施回溯if(a[i]==n&&i==1)break;//退出循环，结束elsea[i]=a[i]+1;}5.1.3回溯法分类2.递归回溯递归也能实现回溯。递归回溯通过递归尝试遍历问题的各个可能解的通路。当发现此路不能时，回溯到上一步。框架描述：intput(intk){inti,j,u;if(k<=<规模

8、>){u=0;if(<约束条件>)u=1;//当u=1时不可操作if(u==0)//当u=0时可操作{if(k==<规模>)//已满足规模，打印一个解printf(<一个解>);elseput(k+1);//调用put(k+1)}}}5.2桥本分数式案例提出：日本数学家桥本吉彦教授于1993年10月在我国山东举行的中日美三国数学教育研讨会上提出以下填数趣题：把1,2,…,9这9个数字填入下式的9个方格中(数字不得重复)，使下面分数等式成立:□□□──+──=──□□□□□□桥本教授当即给出了一个解答。这一填数趣题的解是否唯一？如果不唯一究竟有

9、多少个解？试求出所有解答(等式左边两个分数交换次序只算一个解答)。(1)回溯设计要点设置a数组，式中每一□位置用一个数组元素表示：为避免解重复，设a(1)