回溯法

来自计算思维百科
跳转至: 导航搜索

回溯法(Back Tracking)本质上是一种穷举法,它在问题的解空间中系统地搜索问题解,当当前的解不合适时,就回到前一个解,重新构造新的解,继续判断是否合适。如此反复。

基本描述

回溯的一种简单应用是老鼠走迷宫。老鼠从迷宫入口出发,任选一条路线向前走,在到达一个岔路口时,任选一个路线走下去,…,如此继续,直到前面没有路可走时,老鼠退回到上一个岔路口,重新在没有走过的路线中任选一条路线往前走。按这种方式走下去,直到走出迷宫,或一直退回到起点,也即迷宫不存在从入口到出口的路径。

上述搜索过程可表述为:每次从一个部分解集合出发(从入口到当前岔路口的路径),选择一个新成员(一条路线),并验证它是否满足某个约束条件(这条路线是否可继续走);如果满足,就把它加入到原来的部分解集合中,从而得到一个更大的部分解;继续这个过程,直到部分解扩展为原问题的一个解(找到通往出口的通路)。若新成员不满足约束条件,则去掉这个成员,并重新选择一个没被选到的新成员加入(另选一条没走过的路线)。若这一步没有满足约束条件的新成员,则从部分解集合中去掉最后加入的一个成员,回溯到上一个部分解(上一个岔路口),继续。简单的一句话描述这一过程是:从部分解往前走,能进则进,不能进则退回来,换一条路再试。

显然,回溯法在搜索过程中通过约束条件的判定,排除错误答案,提高搜索效率。

使用方法及步骤

1、将问题进行适当的转化,得出状态空间树;

2、这棵树的每条完整路径都代表了一种解的可能;

3、通过深度优先搜索这棵树,枚举每种可能的解的情况。

应用

搜索引擎

搜索引擎(Search Engine)是大家经常使用的,所有搜索引擎可提炼成下载、索引和排序三种基本服务,也即自动下载尽可能多的网页、建立快速有效地索引、根据相关性对网页进行公平准确的排序。

搜索引擎(search engine )是一种帮助用户在Web上检索信息的工具。搜索引擎其实也是一个Web服务器,其主要功能是搜集Web上的各种资源并按一定规律进行分类,提供给用户进行检索。当用户要查找某类信息而又不知道具体网址时,就可求助于搜索引擎。例如很多人都访问过“新浪”、“搜弧”、“Yahoo”等网站,它们都是搜索引擎。

搜索引擎由三部分组成,一个负责收集信息的程序,一个索引数据库和一个面向用户的检索界面。收集信息的程序被称作Robot(机器人)、Wanderer(流浪者)、Crawler(爬行者)、Spider(蜘蛛)等,它们的任务是自动访问Internet上的 Web、FTP、Gopher等站点中的资源,进行信息索引并建立数据库。面向用户的检索界面通常就是搜索引擎的主页,它接受用户的检索请求,从索引数据库中检索,并将结果返回给用户。

如何自动下载互联网所有网页?完成这个功能的程序叫网络爬虫(Web Crawlers),在一些文献中也称机器人,它使用了图论中的遍历算法。

图的遍历

图的遍历('Traversing Graph)是指从图中某一顶点出发访遍图中其余顶点,且使每个顶点仅被访问一次。图的一种遍历方式是深度优先,它是一种回溯算法。

深度优先遍历从图中一个顶点出发一直向前走,依次访问与最近访问顶点邻接的顶点,无顶点访问时,返回至上一顶点,选择它的另一个未被访问的邻接顶点继续。

假设图1中无向图(a)。从V1出发的深度优先遍历过程如图1(b)所示,图中实线表示搜索,虚线表示回溯,线上数字表示搜索、回溯步骤。

                9.2.1.png

                                 图1 图的深度优先遍历过程 

深度优先遍历从顶点V1出发,访问V2,然后依次访问V4、V8、V5,因V5没有未访问过的邻接点,回溯至V8,V8也没有未访问过的邻接点,继续回溯,直到V1,V1有未访问的邻接点V3,故访问V3,继续遍历,直到回溯到V1,V1没有未访问过的邻接点,算法终止。图3-3(a)的深度优先遍历顺序是:V1,V2,V4,V8,V5,V3,V6,V7

该算法如何在网络爬虫中应用呢?可以将网站看做节点,网页中的超链接看做弧,那么互联网的不同网站和超链接构成图。网络爬虫可以从一个网站出发,下载这个网站的所有网页,然后再通过超链接进入下一个网站,下载该网站的所有网页,按照深度优先遍历如此继续下去,可下载整个互联网。当然,网络爬虫并不只是简单的深度优先遍历,它也用到广度优先遍历。

商场中搜索货物

案例:为了在一间偌大的商场里面寻找某件物品,若要搜索商场里面所有的货架,则称为穷举搜索,此时,将耗费巨大的时间与精力。于是,我们可以通过忽略那些可以断定目标不在的其中的货架,以加快寻找的速度。

八皇后问题

回溯法的另一个经典案例是解八皇后'问题'('Eight Queens Problem')。 八皇后是一个古老而著名的问题,是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋的棋盘上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法?

回溯法解八皇后问题的思路是:逐行摆放皇后。初始,第1行皇后放第1列;摆放第i(i=2,∧,8)行皇后时,从第1列开始,逐列判定是否与前i-1行皇后攻击,直到找到一个不攻击的摆放位置,继续第i+1行的摆放;若第i行无摆放位置,则拿掉该行皇后,回溯至第i-1行,第i-1行皇后从当前位置的下一列开始判定,继续搜索。当第1行皇后的摆放位置超出棋盘时,全部求解过程结束,可找到八皇后问题的92种摆法。显然,这是一个由部分解扩展为问题解的过程(按行扩展),在扩展中,加入了是否攻击的约束条件判定。

读者可以简单的四皇后问题(在4X4格的国际象棋的棋盘上摆放四个皇后,使其不能互相攻击)为例,练习上述回溯过程。

回溯法有通用解法之称,当一个问题没有显而易见的解法时,可尝试使用回溯法求解,这实际是与穷举法一致的,因其本质仍是穷举。需要注意,回溯和穷举虽然能解很多问题,但其算法效率可能很低。

浏览网页

案例:假设我们在维基百科中搜索“中国”,页面中关于中国的信息就会显示出来,如下图所示。可以看到,用红框圈出来的部分蓝色字体也是一个链接,我们如果想要了解就可以在这个页面继续点击进入更深的页面。这个过程可以一直进行下去,直到不想再深入了解,而是想了解其他方面的内容,于是我们就回到最开始的“中国”页面,继续深入其他蓝色字体的链接。

回溯法3.png

先有鸡还是先有蛋

案例:先有鸡还是先有蛋?这是个问题。

如果我们说先有鸡,运用回溯的方法,则鸡从何来?来于蛋,蛋先鸡后;

如果我们说先有蛋,同样道理,则蛋从何来?来于鸡,鸡先蛋后。

自相矛盾,这就是著名的鸡蛋悖论。

在探讨这个问题时,我们就用到了回溯的思维方法。

小说《点对点》

案例:回溯在文学作品中也很常见,比如阿尔德斯.胡克利的《点对点》,安德.盖德的《伪造者》,诺尔曼.梅勒《笔记本》等等。

以《点对点》为例,小说的主人公卡尔斯就是一个小说家,而其作品中的小说家又在自己的作品中描写一个小说家…….这样循环下去。读者在阅读过程中,一层一层地返回作品中的现实,其实就是一个个回溯过程。

可以体现的计算思维

回溯法的优点在于其程序结构明确,可读性强,易于理解,而且通过对问题的分析可以大大提高运行效率,体现了计算思维的转化特点。