回溯法的效率分析.docx
- 文档编号:12741956
- 上传时间:2023-06-07
- 格式:DOCX
- 页数:9
- 大小:38.92KB
回溯法的效率分析.docx
《回溯法的效率分析.docx》由会员分享,可在线阅读,更多相关《回溯法的效率分析.docx(9页珍藏版)》请在冰点文库上搜索。
回溯法的效率分析
回溯法概述
与穷举的“笨拙”搜索相较,回溯法那么是一种“伶俐”的求解效益更高的搜索法。
下面介绍回溯设计及其应用,体会回溯法相关于穷举的特点与优势。
回溯的概念
有许多问题,当需要找出它的解集或要求回答什么解是知足某些约束条件的最正确解时,往往利用回溯法。
回溯法是一种试探求解的方式:
通过对问题的归纳分析,找出求解问题的一个线索,沿着这一线索往前试探,假设试探成功,即取得解;假设试探失败,就慢慢往回退,换其他线路再往前试探。
因此,回溯法能够形象地归纳为“向前走,碰鼻转头”。
回溯法的大体做法是试探搜索,是一种组织得井井有条的、能幸免一些没必要要搜索的穷举式搜索法。
回溯法在问题的解空间树中,从根结点动身搜索解空间树,搜索至解空间树的任意一点,先判定该结点是不是包括问题的解;若是确信不包括,那么跳过对该结点为根的子树的搜索,逐层向其父结点回溯;不然,进入该子树,继续搜索。
从解的角度明白得,回溯法将问题的候选解按某种顺序进行列举和查验。
当发觉当前候选解不可能是解时,就选择下一个候选解。
在回溯法中,舍弃当前候选解,寻觅下一个候选解的进程称为回溯。
倘假设当前候选解除不知足问题规模要求外,知足所有其他要求时,继续扩大当前候选解的规模,并继续试探。
若是当前候选解知足包括问题规模在内的所有要求时,该候选解确实是问题的一个解。
与穷举法相较,回溯法的“伶俐”的地方在于能适时“转头”,假设再往前走不可能取得解,就回溯,退一步另找线路,如此可省去大量的无效操作。
因此,回溯与穷举相较,回溯更适宜于量比较大,候选解比较多的问题。
5.1.2回溯描述
1.回溯的一样方式
下面简要论述回溯的一样方式。
回溯求解的问题P,通常要能表达为:
关于已知的由n元组(x1,x2,…,xn)组成的一个状态空间E={(x1,x2,…,xn)|xi∈si,i=1,2,…,n},给定关于n元组中的一个分量的一个约束集D,要求E中知足D的全数约束条件的所有n元组。
其中si是分量xi的概念域,且|si|有限,i=1,2,…,n。
称E中知足D的全数约束条件的任一n元组为问题P的一个解。
解问题P的最朴素的方式确实是穷举法,上面已经作了介绍,即对E中的所有n元组一一地查验其是不是知足D的全数约束,假设知足,那么为问题P的一个解。
显然,其计算量是相当大的。
关于许多问题,所给定的约束集D具有完备性,即i元组(x1,x2,…,xi)知足D中仅涉及到x1,x2,…,xi的所有约束,意味着j(j
换句话说,只要存在0≤j≤n-1,使得(x1,x2,…,xj)违背D中仅涉及到x1,x2,…,xj的约束之一,那么以(x1,x2,…,xj)为前缀的任何n元组(x1,x2,…,xj,xj+1,…,xn)也必然违背D中仅涉及到x1,x2,…,xj的一个约束,n≥i>j。
因此,关于约束集D具有完备性的问题P,一旦检测判定某个j元组(x1,x2,…,xj)违背D中仅涉及x1,x2,…,xj的一个约束,就能够够确信,以(x1,x2,…,xj)为前缀的任何n元组(x1,x2,…,xj,xj+1,…,xn)都可不能是问题P的解,因此就没必要去搜索它们,即省略了对部份元素(xj+1,…,xn)的操作与测试。
回溯法正是针对这种问题,利用这种问题的上述性质而提出来的比穷举法效率更高的算法。
2.4皇后问题的回溯实施
为了具体说明回溯的实施进程,先看一个简单实例。
如安在4×4的方格棋盘上放置4个皇后,使它们互不解决,即任意两个皇后不许诺处在同一横排,同一纵列,也不许诺处在同一与棋盘边框成45°角的斜线上。
图5-1所示为应用回溯的实施进程,其中方格中的×表示试图在该方格放置一个皇后,但由于受前面已放置的皇后的解决而舍弃的位置。
图5-14皇后问题回溯实施求解
图(a)为在第1行第1列放置一个皇后的初始状态。
图(b)中,第2个皇后不能放在第一、2列,因此放置在第3列上。
图(c)中,表示第3行的所有各列均不能放置皇后,那么返回第2行,第2个皇后需后移。
图(d)中,第2个皇后后移到第4列,第3个皇后放置在第2列。
图(e)中,第4行的所有各列均不能放置皇后,那么返回第3行;第3个皇后后移的所有位置均不能放置皇后,那么返回第2行;第2个皇后已无位可退,那么返回第1行;第1个皇后需后移。
图(f)中,第1个皇后后移至第2格。
图(g)中,第2个皇后不能放在第1,2,3列,因此放置在第4列上。
图(h)中,第3个皇后放在第1列;第4个皇后不能放置1,2列,于是放置在第3列。
如此经以上回溯,取得4皇后问题的一个解:
2413。
继续以上的回溯探讨,可得4皇后问题的另一个解:
3142。
3.回溯算法框架描述
(1)回溯描述
关于一样含参量m,n的搜索问题,回溯法框架描述如下:
输入正整数n,m,(n≥m)
i=1;a[i]=<元素初值>;
while
(1)
{
for(g=1,k=i-1;k>=1;k--)
if(<约束条件1>)g=0;//检测约束条件,不知足那么返回
if(g&&<约束条件2>)
printf(a[1-m]);//输出一个解
if(i
while(a[i]==<回溯点>&&i>1)i--;//向前回溯
if(a[i]==n&&i==1)break;//退出循环,终止
elsea[i]=a[i]+1;
}
具体求解问题的试探搜索范围与要求不同,在应用回溯设计时,需依照问题的具体实际确信数组元素的初值、取值点与回溯点,同时需把问题中的约束条件进行必要的分解,以适应上述回溯流程。
其中实施向前回溯的循环
while(a[i]==<回溯点>&&i>1)i--;
是向前回溯一步,仍是回溯两步或更多步,完全依照a[i]是不是达到回溯点来确信。
例如,回溯点是n,i=6,当a[6]=n时回溯到i=5;假设a[5]=n时回溯到i=4;依此类推,到a[i]达到回溯点那么停止。
图5-1所示的4皇后问题迭代回溯进程描述为:
n=4;i=1;a[i]=1;
while
(1)
{
g=1;for(k=i-1;k>=1;k--)
if(a[i]=a[k]&&abs(a[i]-a[k])=i-k)
g=0;//检测约束条件,不知足那么返回
if(g&&i==4)
printf(a[1-4]);//输出一个解
if(i while(a[i]==n&&i>1)i--;//向前回溯 if(a[i]==n&&i==1)break;//退出循环终止 elsea[i]=a[i]+1; } 以上回溯体此刻迭代式i=i-1,因此又称为迭代回溯。 此外,递归也能实现回溯。 (2)递归回溯 intput(intk) {inti,j,u; if(k<=问题规模) {u=0; if(<约束条件>) u=1;//当k时不可操作 if(u==0)//当k时可操作 {if(k==规模)//假设已知足规模,那么打印出一个解 printf(<一个解>); elseput(k+1);//挪用put(k+1) } } } 在挪用put(k)时,当检测约束条件知不可操作(记u=1),即再往前不可能得解,现在固然不可能输出解,也不挪用put(k+1),而是回溯,返回挪用put(k)的地方。 这确实是递归回溯的机理。 若是是主程序挪用put (1),最后返回到主程序挪用put (1)的后续语句,完成递归。 图5.1所示的4皇后问题迭代回溯进程描述为: intput(intk) {inti,j,u; if(k<=4) {for(i=1;i<=4;i++)//探讨第k行从第1格开始放皇后 {a[k]=i; for(u=0,j=1;j<=k-1;j++) if(a[k]==a[j]||abs(a[k]-a[j])==k-j) u=1;//假设第k行第i格放不下,那么置u=1 if(u==0)//假设第k行第i格可放,那么检测是不是满4行 {if(k==4)//假设已放满到4行时,那么打印出一个解 {s++;printf(""); for(j=1;j<=4;j++) printf("%d",a[j]); } elseput(k+1);//假设没放满4行,那么放下一行put(k+1) } } } } 4.回溯法的效益分析 应用回溯设计求解实际问题,由于解空间的结构不同,很难精准计算与估量回溯产生的结点数,因此回溯法的复杂度是分析回溯法效率时碰到的要紧困难。 回溯法产生的结点数通常只有解空间结点数的一小部份,这也是回溯法的计算效率大大高于穷举法的缘故所在。 回溯求解进程实质上是一个遍历一棵“状态树”的进程,只是这棵树不是遍历前预先成立的。 回溯算法在搜索进程中,只要所激活的状态结点知足终结条件,应该把它输出或保留。 由于在回溯法求解问题时,一样要求输出问题的所有解,因此在取得结点后,同时也要进行回溯,以便取得问题的其他解,直至回溯到状态树的根且根的所有子结点均已被搜索过为止。 组织解空间便于算法在求解集时更易于搜索,典型的组织方式是图或树。 一旦概念了解空间的组织方式,那个空间即可从开始结点进行搜索。 回溯法的时刻通常取决于状态空间树上实际生成的那部份问题状态的数量。 关于元组长度为n的问题,假设其状态空间树中结点总数为n! ,那么回溯算法的最坏情形的时刻复杂度可达O(p(n)n! );假设其状态空间树中结点总数为2n,那么回溯算法的最坏情形的时刻复杂度可达O(p(n)2n),其中p(n)为n的多项式。 关于不同的实例,回溯法的计算时刻有专门大的不同。 关于很多具有大n的求解实例,应用回溯法一样可在很短的时刻内求得其解,可见回溯法不失为一种快速有效的算法。 关于某一具体实际问题的回溯求解,常通过计算实际生成结点数的方式即蒙特卡罗方式(Montecarlo)来评估其计算效率。 蒙特卡罗方式的大体思想是在状态空间树上随机选择一条途径(x0,x1,…,xn-1),设X是这一途径上部份向量(x0,x1,…,xk-1)的结点,若是在X处不受限制的子向量数是mk,那么以为与X同一层的其他结点不受限制的子向量数也都是mk。 也确实是说,假设不受限制的x0取值有m0个,那么该层上有m0个结点;假设不受限制的x1取值有m1个,那么该层上有m0m1个结点;依此类推。 由于以为在同一层上不受限制的结点数相同,因此,该途径上实际生成的结点数估量为 计算途径上结点数m的蒙特卡罗算法描述如下: //已知随机途径上取值数据m0,m1,…,mk-1 m=1;t=1; for(j=0;j<=k-1;j++) {t=t*m[j]; m=m+t; } printf(“%ld”,m); 把所求得的随机途径上的结点数(或假设干条随机途径的结点数的平均值)与状态空间树上的总结点数进行比较,由其比值能够初步看出回溯设计的效益。 在下面的n皇后问题的回溯求解时将具体应用以上蒙特卡罗算法估量回溯设计的效益。 5.8回溯应用小结 本章应用回溯设计求解了逐位整除数与桥本分数式等涉及数与数式的典型案例、求解了新颖的素数环与德布鲁金环等环序列,求解了直尺刻度散布与数码串珠等趣题,也求解了伯努利装错信封问题与别出心裁的情侣拍照等难度较大的组合案例。 可见回溯法的应用是超级广漠的。 回溯法有“通用解题法”之称,是一种比穷举“伶俐”的搜索技术,在搜索进程中动态地产生问题的解空间,系统地搜索问题的所有解。 当搜索到解空间树的任一结点时,判定该结点是不是包括问题的解。 若是该结点确信不包括,那么“见壁转头”,跳过以该结点为根的子树的搜索,逐层向其先人结点回溯,可大大缩减无效操作,提高搜索效率。 因此,结合具体案例的实际设计适合的回溯点是应用回溯法的关键所在。 值得注意的是,递归具有回溯的功能,很多问题应用递归回溯可探讨出问题的所有解。 例如,在求解桥本分数式中,既用了回溯法求解,也应用了递归求解,请认真比较这二者之间的关联。 尽管递归的效率不高,但递归设计的简明是一样回溯设计所不及的。 回溯法的时刻复杂度因案例的具体实际而异,其计算时刻可用蒙特卡罗方式计算。 一样来讲,其搜索效率要高于穷举。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 回溯 效率 分析