• 正在加载中...
  • 回溯算法

    回溯算法也叫试探法,它是一种系统地搜索问题的解的方法。回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。用回溯算法解决问题的一般步骤为: 1、定义一个解空间,它包含问题的解。 2、利用适于搜索的方法组织解空间。 3、利用深度优先法搜索解空间。 4、利用限界函数避免移动到不可能产生解的子空间。 问题的解空间通常是在搜索问题的解的过程中动态产生的,这是回溯算法的一个重要特性。

    编辑摘要

    目录

    来源/回溯算法 编辑

    回溯算法也叫试探法,它是一种系统地搜索问题的解的方法。

    用回溯算法解决问题的一般步骤:

    1 针对所给问题,定义问题的解空间,它至少包含问题的一个(最优)解。

    2 确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间 。

    3 以深度优先的方式搜索解空间,并且在搜索过程中用剪枝函数避免无效搜索。

    问题的解空间通常是在搜索问题解的过程中动态产生的,这是回溯算法的一个重要特性。

    确定了解空间的组织结构后,回溯法就从开始结点(根结点)出发,以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点,同时也成为当前的扩展结点。在当前的扩展结点处,搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点,并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动,则当前扩展结点就成为死结点。此时,应往回移动(回溯)至最近的一个活结点处,并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索,直至找到所要求的解或解空间中已没有活结点时为止。

    基本思想/回溯算法 编辑

    回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。八皇后问题就是回溯算法的典型,第一步按照顺序放一个皇后,然后第二步符合要求放第2个皇后,如果没有位置符合要求,那么就要改变第一个皇后的位置,重新放第2个皇后的位置,直到找到符合条件的位置就可以了。回溯在迷宫搜索中使用很常见,就是这条路走不通,然后返回前一个路口,继续下一条路。回溯算法说白了就是穷举法。不过回溯算法使用剪枝函数,剪去一些不可能到达 最终状态(即答案状态)的节点,从而减少状态空间树节点的生成。回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中,按照深度优先的策略,从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时,总是先判断该结点是否肯定不包含问题的解。如果肯定不包含,则跳过对以该结点为根的子树的系统搜索,逐层向其祖先结点回溯。否则,进入该子树,继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时,要回溯到根,且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时,只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法,它适用于解一些组合数较大的问题。

    实例分析/回溯算法 编辑

    例:骑士游历(1997年全国青少年信息学(计算机)奥林匹克分区联赛高中组复赛试题第三题)

    设有一个n×m的棋盘(2(2,3)->(4,4)

    若不存在路径,则输出"no"

    任务2:当n,m 给出之后,同时给出马起始的位置和终点的位置,试找出从起点到终点的所有路径的数目(若不存在从起点到终点的路径,则输出0)。

    例如:

    (n=10,m=10),(1,5)(起点),(3,5)(终点),

    输出:

    2(即由(1,5)到(3,5)共有2条路径,如图4)

    分析:为了解决这个问题,我们将棋盘的横坐标规定为x,纵坐标规定为y,对于一个m×n的棋盘,x的值从1到m,y的值从1到n。棋盘上的每一个点,可以表示为:(x坐标值,y坐标值),即用它所在的列号和行号来表示,比如(3,5)表示第3列和第5行相交的点。

    要寻找从起点到终点的路径,我们可以使用回溯算法的思想。首先将起点作为当前位置。按照象棋马的移动规则,搜索有没有可以移动的相邻位置。如果有可以移动的相邻位置,则移动到其中的一个相邻位置,并将这个相邻位置作为新的当前位置,按同样的方法继续搜索通往终点的路径。如果搜索不成功,则换另外一个相邻位置,并以它作为新的当前位置继续搜索通往终点的路径。

    为简单起见,先看4×4的棋盘,如图3。首先将起点(1,1)作为当前位置,按照象棋马的移动规则,可以移动到(2,3)和(3,2)。假如移动到(2,3),以(2,3)作为新的当前位置,又可以移动到 (4,4)、(4,2)和(3,1)。继续移动,假如移动到(4,4),将(4,4)作为新的当前位置,这时候已经没有可以移动的相邻位置了。 (4,4)已经是终点,对于任务一,我们已经找到了一条从起点到终点的路径,完成了任务,可以结束搜索过程。但对于任务二,我们还不能结束搜索过程。从当前位置(4,4)回溯到(2,3),(2,3)再次成为当前位置。从(2,3)开始,换另外一个相邻位置移动,移动到(4,2),……然后是(3,1)。(2,3)的所有相邻位置都已经搜索过。从(2,3)回溯到(1,1),(1,1)再次成为当前位置。从(1,1)开始,还可以移动到(3,2),从(3,2)继续移动,可以移动到(4,4),这时候,所有可能的路径都已经试探完毕,搜索过程结束。

    如果用树形结构来组织问题的解空间(如图5),那么寻找从起点到终点的路径的过程,实际上就是从根结点开始,使用深度优先方法对这棵树的一次搜索过程。

    对于任务一,要寻找一条从起点到终点的路径,为了确保路径上的点不被丢失,我们可以在程序中设置一个栈,用它来保存搜索过程中象棋马移动到的每一个点。

    算法程序如下:

    回溯算法回溯算法

    在求精以上算法程序的过程中还存在这样一个问题:怎样从当前位置herep移动到它的相邻位置?题目规定,象棋马有四种移动方法,如图2。从左到右,我们分别给四种移动方法编号为0、1、2、3;对每种移动方法,可以用横坐标和纵坐标从起点到终点的偏移值来表示,并将这些表示移动方法的偏移值保存在一个数组pyz中,如下表:

    回溯算法回溯算法

    从当前位置搜索它的相邻位置的时候,为了便于程序的实现,我们可以按照移动编号的固定顺序来进行,比如,首先尝试第0种移动方法,其次尝试第1种移动方法,再次尝试第2种移动方法,最后尝试第3种移动方法。

    对于任务二,要找出从起点到终点的所有路径的数目。我们可以设置一个统计变量ljs。在搜索解空间的过程中,每当搜索到一条从起点到终点的路径,就让统计变量ljs的值增1。这样,当对解空间的搜索过程结束之后,统计变量ljs的值就是问题的答案。

    应用举例/回溯算法 编辑

    1.跳棋问题:

    33个方格顶点摆放着32枚棋子,仅中央的顶点空着未摆放棋子。下棋的规则是任一棋子可以沿水平或成垂直方向跳过与其相邻的棋子,进入空着的顶点并吃掉被跳过的棋子。试设计一个算法找出一种下棋方法,使得最终棋盘上只剩下一个棋子在棋盘中央。

    算法实现提示

    利用回溯算法,每次找到一个可以走的棋子走动,并吃掉。若走到无子可走还是剩余多颗,则回溯,走下一颗可以走动的棋子。当吃掉31颗时说明只剩一颗,程序结束。

    2.中国象棋马行线问题:

    中国象棋半张棋盘如图1(a)所示。马自左下角往右上角跳。今规定只许往右跳,不许往左跳。比如

    图4(a)中所示为一种跳行路线,并将所经路线打印出来。打印格式为:

    0,0->2,1->3,3->1,4->3,5->2,7->4,8…

    回溯算法回溯算法

    算法分析:

    如图1(b),马最多有四个方向,若原来的横坐标为j、纵坐标为i,则四个方向的移动可表示为:

    1: (i,j)→(i+2,j+1); (i<3,j<8) 2: (i,j)→(i+1,j+2); (i<4,j<7)

    3: (i,j)→(i-1,j+2); (i>0,j<7) 4: (i,j)→(i-2,j+1); (i>1,j<8)

    搜索策略:

    S1:A:=(0,0);

    S2:从A出发,按移动规则依次选定某个方向,如果达到的是(4,8)则转向S3,否则继续搜索下

    一个到达的顶点;

    S3:打印路径。

    算法设计:

    procedure try(i:integer); {搜索}

    var j:integer;

    begin

    for j:=1 to 4 do {试遍4个方向}

    if 新坐标满足条件 then

    begin

    记录新坐标;

    if 到达目的地 then print {统计方案,输出结果}

    else try(i+1); {试探下一步}

    退回到上一个坐标,即回溯;

    end;

    end;

    参考程序:

    program exam2;

    const x:array[1..4,1..2] of integer=((2,1),(1,2),(-1,2),(-2,1)); {四种移动规则}

    var t:integer; {路径总数}

    a:array[1..9,1..2] of integer; {路径}

    procedure print(ii:integer); {打印}

    var i:integer;

    begin

    inc(t); {路径总数}

    for i:=1 to ii-1 do

    write(a[i,1],’,’,a[i,2],’-->’);

    writeln(’4,8’,t:5);

    readln;

    end;

    procedure try(i:integer); {搜索}

    var j:integer;

    begin

    for j:=1 to 4 do

    if (a[i-1,1]+x[j,1]>=0) and (a[i-1,1]+x[j,1]=0) and (a[i-1,2]+x[j,2]<=8) then

    begin

    a[i,1]:=a[i-1,1]+x[j,1];

    a[i,2]:=a[i-1,2]+x[j,2];

    if (a[i,1]=4) and (a[i,2]=8) then print(i)

    else try(i+1); {搜索下一步}

    a[i,1]:=0;a[i,2]:=0

    end;

    end;

    BEGIN {主程序}

    try(2);

    END.

    相关文献

    添加视频 | 添加图册相关影像

    互动百科的词条(含所附图片)系由网友上传,如果涉嫌侵权,请与客服联系,我们将按照法律之相关规定及时进行处理。未经许可,禁止商业网站等复制、抓取本站内容;合理使用者,请注明来源于www.baike.com。

    登录后使用互动百科的服务,将会得到个性化的提示和帮助,还有机会和专业认证智愿者沟通。

    互动百科用户登录注册
    此词条还可添加  信息模块

    WIKI热度

    1. 编辑次数:8次 历史版本
    2. 参与编辑人数:6
    3. 最近更新时间:2015-10-30 07:39:02

    互动百科

    扫码下载APP