当前位置:首页 >> 高等教育 >>

回溯算法


回溯算法

JSOI 2008 夏令营(丹阳)

江苏省苏州中学 张信

引入
迷宫问题 n皇后问题
JSOI 2008 夏令营(丹阳) 江苏省苏州中学 张信

引入
? 问题的相似点: ?搜索过程;逐步尝试,遇阻回头。 ?多路选择。 ?结果状态。

JSOI 2008 夏令营(丹阳)

江苏省苏州中学 张信

迷宫问题
(1,1) (1,2) (2,1) (2,2) (2,3)

(2,4)

(3,3) (3,4)

(3,5)
JSOI 2008 夏令营(丹阳)

(4,4)
江苏省苏州中学 张信

迷宫问题
(4,4) (4,5) (4,6) (4,7) (4,8) (5,7) (3,7) (3,7) (3,5) (2,6)
江苏省苏州中学 张信

(5,4) (3,5) (5,6) (5,5) (6,4) (6,5) (6,6) (6,7)

(5,5) (3,6)

JSOI 2008 夏令营(丹阳)

四皇后问题
1 1 2 3 4 1 2 3 2 4 3 1 2 3 4 1 4 2 3 4 3 4 1 2 3 4

1 2 3 4 1 2 3 4

1 2 3 4 1 2 3 4 1 2

1 2 3 4 1 2 3 4

1 2 3 4 1 2 3 4

JSOI 2008 夏令营(丹阳)

江苏省苏州中学 张信

回溯的概念
? 从问题的某种可能情况出发,搜索

所有能到达的可能情况,然后以其 中一种可能的情况为新的出发点, 继续向下探索,当所有可能情况都 探索过且都无法到达目标的时候, 再回退到上一个出发点,继续探索 另一个可能情况,这种不断回头寻 找目标的方法称为“回溯法”。
JSOI 2008 夏令营(丹阳) 江苏省苏州中学 张信

回溯的概念
? 回溯算法是一种有条不紊的搜索问

题答案的方法,是一种能避免不必 要搜索的穷举式的搜索算法,其基 本思想就是穷举搜索。常用于查找 问题的解集或符合某些限制条件的 最佳解集。

JSOI 2008 夏令营(丹阳)

江苏省苏州中学 张信

回溯的一般描述
? 可用回溯法求解的问题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的一个解。
JSOI 2008 夏令营(丹阳) 江苏省苏州中学 张信

回溯的一般描述
即对E中的所有n元组逐一地检测其 是否满足D的全部约束,显然,其计 算量是相当大的。

? 解问题P的最朴素的方法就是枚举法,

JSOI 2008 夏令营(丹阳)

江苏省苏州中学 张信

回溯的一般描述
? 对于许多问题,所给定的约束集D具

有完备性。即i元组 (x1,x2,…,xi) 满足D中仅涉及到x1,x2,…,xi的 所有约束意味着j (j<i)元组 (x1, x2,…,xj) 一定也满足D中仅涉及 到x1,x2,…,xj的所有约束。
JSOI 2008 夏令营(丹阳) 江苏省苏州中学 张信

回溯的一般描述
? 一旦某个j元组 (x1, x2, …, xj) 违反D

中仅涉及x1, x2, …, xj的一个约束, 就可以肯定,以 (x1, x2, …, xj) 为前 缀的任何n元组 (x1, x2, …, xj, xj+1, …, xn) 都不会是问题P的解。

JSOI 2008 夏令营(丹阳)

江苏省苏州中学 张信

回溯的一般描述
? 回溯法正是针对这类问题,利用这

类问题的上述性质而提出来的比枚 举法效率更高的算法。

JSOI 2008 夏令营(丹阳)

江苏省苏州中学 张信

回溯的代码框架
procedure backtrack(n); begin k := 1; while k > 0 and k <= n do 对于没有试过的值x(k),if x(k)∈t(x(1)…x(k-1)) 且 b(x(1)…x(k))=true then begin if x(1)…x(k)是一个解 then write(x(1)…x(k)); inc(k); // 继续尝试 end else dec(k); // 回溯 end;
JSOI 2008 夏令营(丹阳) 江苏省苏州中学 张信

迷宫问题
? x(k) 表示什么? ?x(k) 表示第 k 步后所处的位置; ?表示位置最直接的方法是记录其坐标; ? x(k) 的所有可能的值是什么? ?每一个x(k) 最多有四个可能的值,但 其值无法确定;

JSOI 2008 夏令营(丹阳)

江苏省苏州中学 张信

迷宫问题
? 对四个方向进行编号1~4;
? x(k) 表示第 k 步的方向;

? 每一个x(k) 最多有四个可能的值,

其值为1~4; ? 另设置变量表示当前位置的坐标。

JSOI 2008 夏令营(丹阳)

江苏省苏州中学 张信

迷宫问题
procedure backtrack(); begin k := 1; x := 1; y := 1; while (x <> n) and (y <> m) do begin 更改当前方向; if 所有方向都已尝试过 then begin dec(k); 更新当前坐标; {回溯} end else if (当前方向可通行) then begin 记录当前方向; 更新当前坐标; inc(k); {继续尝试} end end; 输出解; end;
JSOI 2008 夏令营(丹阳) 江苏省苏州中学 张信

迷宫问题
? 坐标与方向的关系?
?x := x + dx(i); ?y := y + dy(i);

(0,-1)

(-1,0) (x,y) (1,0)
(0,1)

JSOI 2008 夏令营(丹阳)

江苏省苏州中学 张信

迷宫问题
? 在判断是否可通行 1 时,为了避免判断 1 “走出”迷宫的情 1 况,可在迷宫外加 1 一圈“墙”。 1 1 1 1
JSOI 2008 夏令营(丹阳)

1 0 0 1 1 0 0 1

1 1 0 0 1 0 0 1

1 1 0 0 1 1 0 1

1 1 1 0 0 0 0 1

1 0 0 1 0 1 0 1

1 0 1 0 0 1 0 1

1 0 0 1 0 1 0 1

1 1 1 1 1 1 1 1

江苏省苏州中学 张信

n皇后问题
? x(k) 表示什么? ?x(k) 表示第 k 个皇后的位置; ? x(k) 的所有可能的值是什么? ?每一个 x(k) 都有 n 个可能的值,其值 为 1~n。

JSOI 2008 夏令营(丹阳)

江苏省苏州中学 张信

n皇后问题
procedure backtrack(n); begin k := 1; while k > 0 do if k > n then begin 输出解; dec(k); end {输出解后回溯} else begin 更新当前皇后位置; if 当前皇后走出棋盘 then dec(k) {已走出棋盘,回溯} else if 当前皇后可以放在当前位置 then begin inc(k); 设置下一个皇后的起始位置; {继续尝试} end end end;
JSOI 2008 夏令营(丹阳) 江苏省苏州中学 张信

n皇后问题
? 攻击判断: ?同列(Q2) ?同对角线(Q1、 Q3)
? k 与行号相同
Q2 Q1 Q2 Q Q3
JSOI 2008 夏令营(丹阳)

Q3 Q3

? x(k) 与列号相同

Q2

Q1
江苏省苏州中学 张信

n皇后问题
function check(pos: integer): boolean; var i: integer; begin check := true; for i := 1 to pos - 1 do if (x[pos] = x[i]) or (abs(x[pos] - x[i]) = abs(pos - i)) then begin check := false; break; end; end;

JSOI 2008 夏令营(丹阳)

江苏省苏州中学 张信

n皇后问题
procedure backtrack(n); begin k := 1; while k > 0 do if k > n then begin 输出解; dec(k); end else begin inc(x[k]); if (x[k] > n) then dec(k) else if check(k) then begin inc(k); x[k] := 0; end end end;
JSOI 2008 夏令营(丹阳) 江苏省苏州中学 张信

回溯算法举例
? 跳马问题:在n×m棋盘上有一中国

象棋中的马:
?马走日字; ?马只能往右走。

? 请你找出一条可行路径,使得马可

以从棋盘的左下角(1, 1)走到右上角 (n, m)。
江苏省苏州中学 张信

JSOI 2008 夏令营(丹阳)

回溯算法举例
? 输入:9 5
? 输出:
(1,1)->(3,2)->(5,1)->(6,3)->(7,1)->(8,3)->(9,5)

JSOI 2008 夏令营(丹阳)

江苏省苏州中学 张信

回溯算法举例
? 多路选择?
? 样例所对应的搜索树?

? x(k) 表示什么?
? x(k) 的所有可能的值是什么?

JSOI 2008 夏令营(丹阳)

江苏省苏州中学 张信

回溯算法举例
? 自然数的有序拆分:任何一个自然

数x都可以被写成若干自然数之和的 形式,如:5=1+4;5=2+3;5= 1+1+1+1+1;……。现请你编写 一个程序,给出自然数x的所有拆分 等式(2+3和3+2视为相同形式)。

JSOI 2008 夏令营(丹阳)

江苏省苏州中学 张信

回溯算法举例
? 输入:4
? 输出:

4=1+3 4=1+1+2 4=1+1+1+1 4=2+2
JSOI 2008 夏令营(丹阳) 江苏省苏州中学 张信

回溯算法举例
? 多路选择?
? 样例所对应的搜索树?

? x(k) 表示什么?
? x(k) 的所有可能的值是什么?

JSOI 2008 夏令营(丹阳)

江苏省苏州中学 张信

回溯算法的优化
? 改变多路选择的顺序 4 3 1 3 1 2 4 4 2 2 1 3
1 2 3
JSOI 2008 夏令营(丹阳)

2 1 4 ? 3

4 4

4

2 3

1

2 1

3

? ?

?

江苏省苏州中学 张信

回溯算法的优化
? 通过挖掘隐藏条件、设置标记等手

段,有效控制回溯进入不可能产生 解的解空间。

JSOI 2008 夏令营(丹阳)

江苏省苏州中学 张信

回溯与穷举
? 回溯的本质是穷举;
? 回溯只能解决一类特殊的穷举问题;

? 回溯在穷举的过程中,通过判断避

免进入不可能产生解的空间,从而 提高了程序的效率。

JSOI 2008 夏令营(丹阳)

江苏省苏州中学 张信

回溯与递归
? 回溯算法需要得到问题的搜索树,

求解的过程是对搜索树进行深度优 先搜索的过程。

JSOI 2008 夏令营(丹阳)

江苏省苏州中学 张信

回溯与递归
1 123 12341234 2 4123 4 12341234 1 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
JSOI 2008 夏令营(丹阳) 江苏省苏州中学 张信

3 12341

4 234 341234

1234123412

12341234

回溯与递归
1 1 1 2 2 3 3 4 1 1 2 2 3 4 3 4 4 1 1 2 4 2 3 3 4 4

JSOI 2008 夏令营(丹阳)

江苏省苏州中学 张信

回溯与递归
? 回溯算法的搜索树 的组织形式、搜

索方式都符合递归的思路。 ? 回溯算法通常可以使用递归实现。

JSOI 2008 夏令营(丹阳)

江苏省苏州中学 张信

回溯与递归
procedure rbacktrack(k); begin if k > n then return else for each x(k),如果x(k)∈t(x(1)…x(k-1))且 b(x(1)…x(k))=true do begin if x(1)…x(k)是一个解 then write(x(1)…x(k) else rbacktrack(k+1); end; end;
JSOI 2008 夏令营(丹阳) 江苏省苏州中学 张信

迷宫问题
procedure backtrack (k, x, y: integer); begin if (x = n) and (y = m) then begin 输出路径; halt; end else for i := 1 to 4 do if (i方向可通行) then begin v[k] := i; backtrack(k + 1, x + dx[i], y + dy[i]); end; end;
JSOI 2008 夏令营(丹阳) 江苏省苏州中学 张信

n皇后问题
procedure backtrack(k: integer); begin if k > n then 输出解; else for i := 1 to n do begin x[k] := i; if check(k) then backtrack(k + 1); end; end;
JSOI 2008 夏令营(丹阳) 江苏省苏州中学 张信

回溯的一般步骤
1. 为问题定义一个解空间(solution

space),这个空间必须至少包含 问题的一个解; 2. 组织解空间,以便它能被容易地搜 索。典型的组织方法是图或树。 3. 对这个空间即可按深度优先的方法 从开始节点进行搜索。
JSOI 2008 夏令营(丹阳) 江苏省苏州中学 张信

回溯的一般步骤
? 开始节点既是一个活节点又是一个E-节点 ? ? ?

?

(expansion node、扩展节点)。 从E-节点可移动到一个新节点。 如果能从当前的E-节点移动到一个新节点,那么这 个新节点将变成一个活节点和新的E-节点,旧的E节点仍是一个活节点。 如果不能移到一个新节点,当前的E-节点就“死” 了(即不再是一个活节点),那么便只能返回到最 近被考察的活节点(回溯),这个活节点变成了新 的E-节点。 当我们已经找到了答案或者回溯尽了所有的活节点 时,搜索过程结束。
江苏省苏州中学 张信

JSOI 2008 夏令营(丹阳)

小结
? 通过前面的分析和讨论,我们可以得

到回溯算法的一些特点:

1. 搜索策略:符合递归的思路,采用深度优

先搜索; 2. 控制策略:在搜索过程中如遇到冲突,则 立即放弃此后的搜索,返回上一层继续搜 索; 3. 数据结构:常用栈来保存搜索过程中的状 态和路径,所需空间大小为搜索所需最长 路径的长度。
JSOI 2008 夏令营(丹阳) 江苏省苏州中学 张信

小结
? 在控制策略中,冲突产生的条件可能

来源于两个方面:
1. 一种是题目中明确给出的条件(显式约

束),对这类条件的把握比较容易; 2. 另一种是需要根据题目的描述以及一些常 识分析出来的条件(隐式约束),对这类 条件的把握就比较困难,容易遗漏。

JSOI 2008 夏令营(丹阳)

江苏省苏州中学 张信

小结
? 回溯算法在搜索执行的同时产生解

空间。在搜索期间的任何时刻,仅 保留从开始节点到当前E-节点的路 径。

JSOI 2008 夏令营(丹阳)

江苏省苏州中学 张信

骑士遍历
? 骑士遍历:在n×m棋盘上有一中国

象棋中的马,请你找出一条可行路 径,使得马可以不重复的走遍棋盘 上所有的格子。 ? 输入数据:四个整数n、m、x、y, 表示棋盘大小和马的起始位置。 ? 输出数据:一条可行路径。
JSOI 2008 夏令营(丹阳) 江苏省苏州中学 张信

骑士遍历
? 输入:4 5 1 1
? 输出:

0 19 6 15 2 5 14 1 10 7 18 9 12 3 16 13 4 17 8 11
JSOI 2008 夏令营(丹阳) 江苏省苏州中学 张信

0/1字符串问题
? 输出仅有0和1组成的长度为n的字符

串,并且其中不可含有三个连续的 相同字串。 ? 输入数据:一个整数n(n≤40) ? 输出数据:一个整数,表示所有满 足条件的字符串的个数
JSOI 2008 夏令营(丹阳) 江苏省苏州中学 张信

0/1字符串问题
? 输入:2
? 输出:4

? 可能的字符串为:00、01、10、11

JSOI 2008 夏令营(丹阳)

江苏省苏州中学 张信

0/1字符串问题
? 什么是三个连续的相同字串? ?三个子串长度相等且对应位置的数 字相同 ?三个子串顺序相连

JSOI 2008 夏令营(丹阳)

江苏省苏州中学 张信

0/1字符串问题
? 如何对某长度为n的0/1子串进行检测? ?我们知道,符合条件的子串长度范围为1~ L/3,因此我们要对这些长度子串逐一进行 检测; ?检测时,如果第一个子串首位置为x,子串 长度为y,则需要对(x+q,x+y+q,x+2y+q)这 y组数字进行检测(0≤q≤y-1);

JSOI 2008 夏令营(丹阳)

江苏省苏州中学 张信

0/1字符串问题
? 比如检测字符串“101101101”
? 第一轮子串长度为1

? 第二轮子串长度为2
? 读三轮子串长度为3

1 0 1 1 0 1 1 0 1
JSOI 2008 夏令营(丹阳) 江苏省苏州中学 张信

0/1字符串问题
? 从刚才的演示可以看出,如果n比较

大的时候,除了需要枚举所有长度 为n的字符串外,对于每一个长度为 字符串还需要大量的检测操作,不 可能在短时间内得到结果,还必须 进行优化。

JSOI 2008 夏令营(丹阳)

江苏省苏州中学 张信

0/1字符串问题
? 利用对称性优化
? 利用完备性优化

JSOI 2008 夏令营(丹阳)

江苏省苏州中学 张信

0/1字符串问题
procedure search(L: integer); begin if L > n then begin inc(total, 2); exit; end else begin a[L] := 0; if 不存在以L为最后一位的三个连续的相同子串 then search(L+1); a[L] := 1; if 不存在以L为最后一位的三个连续的相同子串 then search(L+1); end end;
JSOI 2008 夏令营(丹阳) 江苏省苏州中学 张信

圆盘移动问题
? 平台上从左往右有A、B、C、D四根柱

子,一开始在A柱上套有n(n≤20)个直径 相同的圆盘,从下到上依次用连续小写 字母a,b,c,……编号。圆盘可以在四根柱 子之间单向的向右移动(即允许A?B, 但不允许B?A)。现告诉你起始时圆盘 的数量和最后D柱上圆盘的顺序,请你 编程找出移动的过程。
JSOI 2008 夏令营(丹阳) 江苏省苏州中学 张信

圆盘移动问题
? 输入数据 ?输入数据共两行,第一行是A柱上圆盘的 总数,第二行是最终D柱上由下到上的圆 盘的序列。 ? 输出数据 ?输出数据共若干行,每行包含用空格隔开 的三个字母,分别表示当前要移动的圆盘 编号、移动前圆盘所在柱号和移动后圆盘 所在柱号。若无法移到目标状态,则输出 “no solution!”。
JSOI 2008 夏令营(丹阳) 江苏省苏州中学 张信

圆盘移动问题
? 输入 ?3 ?abc ? 输出 ?c A B ?b A C ?a A D ?b C D ?c B D
JSOI 2008 夏令营(丹阳)

c b a

c b a

江苏省苏州中学 张信

圆盘移动问题
? 所有的移动方式可以归纳为两大类: ?直接移到D柱 ?其他过渡移动
?A?B; ?A?C; ?B?C;

JSOI 2008 夏令营(丹阳)

江苏省苏州中学 张信

圆盘移动问题
? 由于最终状态圆盘的顺序是任意的,因此为

了下面表示的方便,我们不妨把最终状态的 盘子从下到上用数字1~n依次编号; ? 这样最后D柱上面的盘子序号一定是从下到 上递增的; ? 而由于C柱只能直接往D柱移动,因此C柱上 的圆盘编号一定是从下到上递减的(不一定 连续); ? 而A、B柱上圆盘编号没有明显的规律。
JSOI 2008 夏令营(丹阳) 江苏省苏州中学 张信

圆盘移动问题
? 移动的回溯思路 ?从某个状态开始,先检测A、B、C三柱柱 顶圆盘是否能直接移到D柱(循环检测至 均不能移到D柱为止) ?依次尝试A?B、A?C、B?C,如果某个 移到可行,则进入下一个状态重新检测。 当无法继续移到时,回溯到上一个状态继 续尝试。 ?当所有情况都检测完也无法到达目标状态 时,输出无解。
JSOI 2008 夏令营(丹阳) 江苏省苏州中学 张信


相关文章:
回溯算法原理和几个常用的算法实例.doc
IT技术| 算法| 回溯算法原理和几个常用的算法实例_IT/计算机_专业资料。回溯算法,八皇后问题,迷宫问题,骑士周游问题,幂集问题的算法原理和程序 回溯...
回溯算法(C++版).doc
回溯算法(C++版) - 一、回溯算法的定义: 回溯算法也叫试探法,它是一种系统地搜索问题的解的方法。回溯算法的基本思想是: 从一条路往前走,能进则进,不能进...
算法分析_回溯法(很不错).ppt
? 回溯法回溯算法是所有搜索算法中最为基本的一种算法,是一 种能避免不必要搜索的
算法设计与分析:回溯法-实验报告.doc
算法设计与分析:回溯法-实验报告 - 应用数学 学院 姓名 实验题目 信息安全 专业 班 学号 回溯算法 实验评分表 序 评分项目 号 1 指导教师评分标准 完成度 评分...
回溯算法_图文.ppt
回溯算法_学科竞赛_高中教育_教育专区。回溯算法2016冬令营第4讲 1 ?
回溯算法实例一.doc
回溯算法实例一 - 【问题】 填字游戏 问题描述: 在 3×3 个方格的方阵中要
回溯算法.doc
回溯算法 - 回溯算法 一、介绍: 回溯算法实际上一个类似枚举的搜索尝试过程,主
回溯算法实验.doc
回溯算法实验 - 算法设计分析实验: 素数环问题和n皇后问题... 回溯算法实验
搜索与回溯算法.doc
29 回溯算法一、回溯法的思想在求解一些问题(如走迷宫、地图着色等问题)时,题目
深度优先搜索与回溯算法_图文.ppt
深度优先搜索与回溯算法 - 深度优先搜索与回溯算法 回溯是计算机解题中常用的算法
回溯算法(含代码).doc
回溯算法(含代码) - 回溯算法 引言 寻找问题的解的一种可靠的方法是首先列出所
回溯算法的应用(DOC).doc
回溯算法的应用(DOC) - 回溯算法的应用 课程名称: 院系: 算法设计与分析
算法8_回溯法_图文.ppt
算法8_回溯法 - 第8章 回溯法 学习要点: ? ? ? ? 理解回溯法的深度优先搜索策略 理解剪枝函数(约束函数和限界函数)的作用 掌握回溯法解题的算法框架 (1)...
回溯算法_图文.ppt
回溯算法 - 回溯算法 JSOI 2008 夏令营(丹阳) 江苏省苏州中学 张信
回溯算法-八皇后_图文.ppt
回溯算法-八皇后 - 经典回溯算法 八皇后问题 八皇后问题-1850年高斯 ?
回溯算法_图文.ppt
回溯算法 - 回溯算法 奥赛暑假培训班专题之一 双十中学 庄晓芳 2006.7 回溯算法是所有搜索算法中最为基本的一种算法,是一种 能避免不必要搜索的穷举式的搜索...
回溯算法的应用.doc
回溯算法的应用_计算机软件及应用_IT/计算机_专业资料。回溯算法的应用回溯算法的应用 课程名称: 院系: 算法设计与分析 *** *** *** 学生姓名: 学号: 专业班...
哈密顿回路问题的回溯算法.doc
哈密顿回路问题的回溯算法 - ● 哈密顿回路问题: ● 解空间: A={ (x1
数学建模回溯法_图文.ppt
数学建模回溯法 - 第5章 回溯法 1 ? ? ? ? ? 学习要点 理解回溯法的深度优先搜索策略。 掌握用回溯法解题的算法框架 (1)递归回溯 (2)迭代回溯 ? ? (3...
算法分析复习题目及答案.doc
算法分析复习题目及答案 - 一。选择题 1、二分搜索算法是利用( A、分治策略 A )实现的算法。 C、贪心法 A D、回溯法 )。 D、定义最优解 B、动态规划法...
更多相关标签: