当前位置:首页 >> 学科竞赛 >> 回溯1

回溯1


回溯法
算法思想 回溯是一种系统地搜索问题解答的方法。它通 过将解空间组织成一棵解空间树,然后以深度 优先的方式搜索解空间树,并且在搜索过程中 利用剪枝函数来避免无效搜索。 ? 回溯法的步骤如下: 1) 定义一个解空间,它包含问题的解。 2) 用适于搜索的方式组织该空间。 3) 用深度优先法搜索该空间,利用剪枝函数避 免移动到不可能产生解的子空间。
?

/>
解空间 一般搜索空间有两种组织方式: 子集树 排列树 ? 搜索的方式 主要采用深度优先搜索的方式 ? 数据结构 采用栈的先进后出的思想,主要用递归 函数的思想实现 ? 效率的提高 约束函数 限界函数 两者的结合
?

剪枝函数
为避免无效搜索,常采用下列两种剪枝函数: 1.用约束函数在扩展接点处剪去不满足约束的 子树 2.用限界函数剪去不能得到最优解的子树 ? 根据剪枝函数的不同,可得到不同的回溯法。 ? 剪枝函数主要根据具体问题来设计,如果设计 得好,可极大地提高搜索的效率。 ? 根据求解方式的不同,可得到两种回溯法: 递归回溯和迭代回溯
?

0-1背包问题 给定n种物品和一个背包。物品i的重量是wi其 价值为pi ,背包的容量为c,问如何将物体装入 背包中,使得装入背包中的物品的总价值最大? ? 问题的形式化描述:给定c >0,wi>0,pi>0, 1≤i≤n,要求找出一个n元的0-1向量 (x1,x2,…,xn), xi ?{0 ,1}(1≤i≤n),使得
?

?w x
i ?1

n

i i

?c

而且

max ? pi xi
i ?1

n

子集树 (0/1 背包问题)

用回溯法搜索子集树的算法
Backtrack(t) if t>n then Output(x) else for i← 0 to 1 do x[t] ←i if Constraint(t) and Bound(t) then Backtrack(t+1)

旅行商问题
问题描述: 某售货员要到若干城市去推销商品,已知各城 市之间的路程(或旅费)。他要选定一条从驻 地出发,经过每个城市一遍,最后回到驻地的 路线,使总的路程(或旅费)最小。 ? 或者:给出一个具有n 顶点的网络(有向或无 向图),要求找出一个包含所有n 个顶点的具 有最小耗费的环路。 ? 任何一个包含网络中所有n 个顶点的环路被称 作一个旅行。在旅行商问题中,要设法找到一 条最小耗费的旅行。
?

?

形式化描述 给定n个城市以及任意两城市i,j之间的距离 dij,问题是找n-1个城市(1,2,…,n)的一个排 列(1,x2,…,xn), 使得

min ? d xi xi?1 ? d xn 1
i ?1

n ?1

用回溯法搜索排列树的算法
Backtrack(t) if t>n then Output(x) else for i←t to n do exchange x[t] ?x[i] if Constraint(t) and Bound(t) then Backtrack(t+1) exchange x[t] ?x[i]

例7售货员难题 salesman
【问题描述】 某乡有n个村庄(1<=n<=40),有一个售货员,他要到各个村 庄去售货,各村庄之间的路程s(0<s<1000)是已知的,且A村到B 村与B村到A村的路程大多不同。为了提高效率,他从商店出发 到每个村庄一次,然后返回商店所在地,假设商店所在的村庄 为1,他不知道选择什么样的路线才能使所走的路程之和最短。 请你帮他选择一条最短的路。 【输入格式】村庄数n和各村之间的路程(均是正整数)。 【输出格式】最短的路程。 30 【样例】 1 2 salesman.in 5 4 {村庄数} 10 6 0 30 6 4 {村庄1到各村的路程} 4 30 0 5 10 {村庄2到各村的路程} 3 4 6 5 0 20 {村庄3到各村的路程} 20 4 10 20 0 {村庄4到各村的路程} salesman.out 25

一句话概括题意: 有n个村庄,每个村庄必须经过一次,也只能经过一次,求 一条走遍全部村庄的最短路。 ? 分治与贪心尝试: 可能会想到一种很自然的贪心策略:每次都抄近路!可是因 为每个村庄只能经过一次,不具备“贪心选择性质”,可以举出 反例,证明每次都抄近路的做法得不到全局最优解。所以不能用 贪心。 实际上因为任何两个村庄之间都可能有路,所以n个村庄分解 成两部分之后,彼此之间的村庄不是独立的,子问题不独立是不 能用分治的,连分治都不行,更别说贪心了。 ? 所以需要重新提炼问题特征: 如果我们能把所有的路线都替他走一遍,算一算,是不是一 定能知道哪条路最短呢?是的。 让我们当一回售货员,体验一下他的工作吧:
?

解题思路:

当一回售货员
1 30 2 10 售货员

5
6 3 20 3 20

4
4 5

30 2

1

4
4 1 30+5+20+4=59

共有6种不同的售货路线 有两种试探方法: (1)6个人从起点同时出发, 各走一条路; (2)1个人先后走完6条路。 2

售货员

1 3

4

3

4

2

4

2

3

4

3

4

2

3

2

1

1

1

1

1

1

1个人先后走完6条路
1 30 2 10 售货员

5
6 3 20 3 20

4
4 5

30 2

1

获得第一种可行解之后,如 何快速得到下一种可行解?

4
4 1 30+5+20+4=59

这种寻找到叶子结 点,为了获取下一 种可行解而采取的 “后退策略”就叫 回溯算法。
继续后退一步。选择 村庄4;再到达3,并 由3返回1,得到另一 种可行解。 3 20

售货员

30 2 5

1

10 4 20 3 6

向后退一步
4

4

1 30+5+20+4=59

1 30+10+20+6=66

采用进进退退的 “回溯算法”就 可以得到所有的 可行解。
2

售货员

1 3

4

3

4

2

4

2

3

4

3

4

2

3

2

1

1

1

1

1

1

?

重新提炼问题特征: 问题的解集合是确定的,最优解包含在众多可行解之中,需 要逐一寻找判断。为了便于寻找,需要把可行解组织成某一种 合适的状态,通常就组织成一棵树,叫解空间树,寻找时从根 结点出发,向儿子结点推进,遇到叶子结点就得到了一种可行 解。但是因为可行解很多,此时才得到一种,所以要采取一种 策略获取其它可行解。(其实后退一步,就可以获取另一种可行 解。) 这种寻找到叶子结点,为了获取下一种可行解而采取的“后 退策略”就叫回溯算法。 优化: 其实在寻找过程中,有的时候不一定非得遇到了叶子结点 才回溯,比如当前按某一种方案走遍全部村庄,经过的路程是 min,寻找下一种可行解的时候,如果还没走完全部村庄,但是 经过的路程已经大于min,那么这样继续走下去就没意义,应该 立即提前回溯。

?

售货员 第二种售货方案到达第3 个村庄的时候,经过的路 程之和60已经大于第一种 可行解,继续走下去只会 越来越长,所有再走下去 就没意思了,提前回溯吧。 5

1 30 2 10 4 20 3 4 2 3 2 3 4

3
20 4

2

4

2

3

4
1 30+5+20+4=59 1 1 1 1 1

30+10+20=60>59

剪枝函 数
目的:提高回溯法效率; 剪枝函数的设定:
采用当前已知的最优解(费用为X)为标准,对于有n个结点 的TSP问题来说,假设当前搜索层次为第i层(1<i<n)的某结点E
如果当前路径长度<X,则以E为扩展结点继续向下一层搜索;

如果当前路径长度>=X,则表明以E为根结点的子树中不包 含最优解,将以E为根结点的子树中所有结点都置为死结点,算 法向E最近的祖先活结点回溯;

回溯法的实现方式
t表示递归深度 void backtrack( int t) { if(t>n) output(x); else n用来控制递归深度 表示在当前扩展结点处未搜索过 的子树的起始编号

for(int i=f(n,t);i<=g(n,t);i++) { x[t]=h(i); if(constrain(t)&&bound(t)) 表示在当前扩展结点处未搜索过 的子树的终止编号 backtrack(t+1); 表示在当前扩展结点处的限界函数 表示当前扩展结点处的约束函数

}
}

参考程序:
var data:array[1..40,1..40] of byte; p:array[1..40] of 0..1; n,i,j,count:byte; min,m :longint; procedure road(k:byte); {搜索从村庄k出发} var i:byte; begin if count=n then {全程变量count用于统计走过的村庄数} begin if m+data[k,1]<min then min:=m+data[k,1]; {更新最优解} exit; end; for i:=2 to n do {在村庄2到n之间选择一个继续前进} if p[i]=0 then begin p[i]:=1; count:=count+1; m:=m+data[k,i]; if m<min then road(i); {考虑提前回溯,搜索从村庄i继续前进的解} p[i]:=0;count:=count-1; m:=m-data[k,i]; {遇到叶结点的回溯} end; end;

begin readln(n); for i:=1 to n do for j:=1 to n do read(data[i,j]); for i:=1 to n do p[i]:=0;min:=99999999; m:=0;p[1]:=1;count:=1; road(1); {按题目规定,从村庄1出发} writeln(min); end. 复杂度分析
算法road在最坏情况下可能需要更新 当前最优解O((n-1)!)次,每次更新 min需计算时间O(n),从而整个算法 的计算时间复杂性为O(n!)。

0/1背包问题
解空间 (x1,x2,…,xn), xi ?{0,1} ? 解题的思路 从第一个物体出发,把物体一个个放到 背包里面,直到背包装不下物体或者到 了一个叶子结点为止,然后回溯以求得 更好的解,反复进行,直到所有的叶子 都搜索到为止。
?

数据结构 可以用一个数组x[]来存储一个解。数组 元素x[i]的值表示物体是否放进背包。而 重量和价值均可以用数组来实现。 ? 递归函数就实现了先进后出的思想。 ? 程序效率的提高 1)利用约束函数 2)利用限界函数
?

?

根据剪枝函数的不同,可得到三种回溯法: 1)利用约束函数,即当搜索到一个结点时, 考虑当前重量是否超过背包重量,如果超过, 则不搜索该结点的子树。 2)利用限界函数,即如果当前价值与剩余价 值之和没有超过当前价值最大的,则不搜索该 结点的子树。 3)按收益密度pi / wi 对剩余对象排序,将对象 按密度递减的顺序去填充背包的剩余容量,当 遇到第一个不能全部放入背包的对象时,就使 用对象的一部分。

例子

n=3,c=30,w=[20,15,15],p=[40,25,25]

const maxn=50; var n,c,i,j:integer; p:array[1..maxn] of integer; w:array[1..maxn] of integer; x:array[1..maxn] of integer; cw,cp,bestp:integer; procedure back(t:integer); var i,j,rp:integer; begin if t>n then begin if cp>bestp then bestp:=cp; end else for i:=1 downto 0 do if cw+w[t]*i<=c then begin x[t]:=i; rp:=0; for j:=t+1 to n do rp:=rp+p[j]; cw:=cw+w[t]*i; cp:=cp+p[t]*i; if cp+rp>bestp then back(t+1); cw:=cw-w[t]*i; cp:=cp-p[t]*i; end; end;

begin assign(input,’bag.in’); reset(input); assign(output,’bag.out’); rewrite(output); readln(n,c); bestp:=0; for i:=1 to n do read(w[i]); for i:=1 to n do read(p[i]); back(1); writeln(bestp); close(input); close(output); end.

const maxn=50; var n,c:integer; p,w,temp:array[1..maxn] of real; x:array[1..maxn] of integer; cw,cp,bestp:real; procedure init; var i,j:integer; t:real; begin assign(input,’bag.in’);reset(input); assign(output,’bag.out’); rewrite(output); readln(n,c); bestp:=0; for i:=1 to n do begin readln(w[i],p[i]); temp[i]:=p[i]/w[i]; end; for i:=1 to n-1 do for j:=i to n do if temp[i]<temp[j] then begin t:=temp[i]; temp[i]:=temp[j]; temp[j]:=t; t:=w[i]; w[i]:=w[j]; w[j]:=t; t:=p[i]; p[i]:=p[j]; p[j]:=t; end; end;

procedure back(t:integer); var i,j:integer; begin if t>n then begin if cp>bestp then bestp:=cp; end else begin if cp+(c-cw)*temp[t]<bestp then exit else for i:=1 downto 0 do if cw+w[t]*i<=c then begin x[t]:=i; cw:=cw+w[t]*i; cp:=cp+p[t]*i; back(t+1); cw:=cw-w[t]*i; cp:=cp-p[t]*i; end; end; end; begin init; back(1); writeln(bestp:0:0); close(input); close(output); end.

回溯算法
回溯法的基本思想 在确定解空间的组织结构后,回溯法从根结点出发,以深度优 先方式搜索整个解空间。这个开始结点成为活结点,同时也成为 当前的扩展结点。 在当前扩展结点处,搜索向纵深方向移至一个新结点。这个新 结点成为新的活结点,并成为扩展结点。 如果在当前扩展结点处不能再向纵深方向移动,则当前扩展结 点就成为死结点。此时,应往回移动(回溯)到最近的活结点处, 并使该结点成为当前的扩展结点。 回溯法按上述方式递归地在解空间中搜索,“能进则进,不进 则退”,直到找到所要求的解或解空间中没有活结点为止。 ? 回溯法的主要步骤 (1)针对所给问题,定义问题的解空间;(排列树和子集树) (2)确定易于搜索的解空间结构; (3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数 避免无效搜索。
?

例8买鱼问题fish
问题描述: 吴奶奶一大早就到花鸟鱼虫市场买鱼,这个市场有各种各样的鱼。这 些鱼实在是太美了,买的人越来越多,可是因为货源有限,卖鱼的老板不 得不规定:同一种鱼,每个人最多只能买一条,并且有些鱼是不能一起买 的,因为它们之间会互相争斗吞食。 吴奶奶想尽可能地多买些鱼,但可惜她的资金有限,这可怎么办呢? 请编写一个程序帮助她。如果有多个方案都能买到尽可能多的鱼,则选择 所花资金最多的一个。 ? 输入文件fish.in 第一行为两个正整数M(M≤1000),N(N≤30),分别表示吴奶奶的资金和 鱼的种类。 以下N行,每行有两个正整数S(1≤S≤N),T(0<T≤30000),分别表 示某种鱼的编号和价格。 接着,每行有两个整数p,q。当p,q大于0时,表示p,q不能共处;当 p,q均等于0时,表示输入文件的结束。 ? 输出文件fish.out 第一行为两个正整数X,Y,分别表示所买鱼的条数和总花费。以下X 行,每行有一个整数,表示所买鱼的编号,编号按升序排列输出。 如果题目有多个解,只需输出其中一个。
?

输入样例: 170 7 1 70 2 50 3 30 4 40 5 40 6 30 7 20 14 17 34 35 57 67 00

输出样例: 4 160 2 4 5 6

解题思路:
?

?

?

?

?

一句话概括题意: 老人家有M元钱,市场上有N种鱼,有些鱼相互之间会打架,确定 一种方案,使老人家能买到尽量多的相互之间都不会打架的鱼。 贪心尝试: 先考虑能不能分治?也就是能不能分解成多个互相独立的子问题。 经过分析,不能分治,也就不能贪心了。 模型联想: 如果把钱当作背包,把鱼当作物品,本题就是一个带约束条件的01 背包问题。多次的解题经验反复告诉我们:01背包因为不一定总能把 背包装满,所以不能“贪心”。 解的集合是否确定? 是,考虑用回溯。 从最终的购买方案来说:任何一种鱼要么买了,要么没有买。如果 分别用1和0表示买了和不买某一种鱼,那么n条鱼共有2n种购买方案, 这些方案构成了一棵解空间树,而且是子集树。采用回溯算法系统地 搜索这棵树,就能得到最优解。 优化:在搜索的过程中有一个明显的优化方法,买了一种鱼之后,把 与它会打架的鱼全部排除掉,下一次搜索时就会剪掉很多枝。可以节 省很多时间,大大提高搜索的效率。

var cost,result,buy:array[1..30]of integer; {最终购买方案result,当前方案buy} f:array[1..30,1..30]of boolean; {鱼的相互关系,true表示能共处,flase表示会打架} v:array[1..30]of boolean; {记录某种鱼是否买过} n,m,i,j,total,max,count,num:integer; procedure search(k:integer); {搜索第k种鱼,它有买和不买两种选择} var i:integer; u:array[1..30]of boolean; begin if k>n then {递归出口,回溯} begin if count>num then {当买的鱼数量更多时更新最优解} begin for i:=1 to n do result[i]:=buy[i]; num:=count; max:=total; end else if (count=num)and (total>max) then {鱼数量相同,但花费更多时更新最优解} begin for i:=1 to n do result[i]:=buy[i]; max:=total; end; exit;

if (not v[k])and(total+cost[k]<=m) then {如果第k种鱼没买过, begin 钱又足够,就买!} v[k]:=true; inc(count); buy[count]:=k; inc(total,cost[k]); u:=v; for i:=1 to n do {买了第k种鱼,所有与之不能共处的鱼都不 能买,这是剪枝} if f[k,i]and(not v[i]) then v[i]:=true; search(k+1); {买了第k种鱼,在此基础上再搜索第k+1种鱼} dec(count); {以下四条语句都是回溯} dec(total,cost[k]); v:=u; v[k]:=false; end; search(k+1); {不买第k种鱼,直接搜索第k+1种鱼}
end; {else search}

Begin {主程序} readln(m,n); for i:=1 to n do readln(j,cost[j]); fillchar(f,sizeof(f),false); readln(i,j); while (i<>0) or (j<>0) do 复杂度分析 begin 时间复杂度O(n!) f[i,j]:=true; f[j,i]:=true; readln(i,j); end; max:=0;total:=0;num:=0;count:=0; fillchar(v,sizeof(v),false); search(1); {从第1种鱼开始搜索} writeln(num,' ',max); for i:=1 to num do writeln(result[i]); end.


更多相关文档:

回溯算法1.0

回溯算法程序设计课程:算法设计与分析 实验名称: 回溯法 班级:软工 143 学号 : 1400170316 姓名 :吴文鑫 实验日期:2016 年 5 月 1 日 实验目的:掌握回溯法的...

回溯讲义(1)

22页 1财富值 动态规划 18页 免费 ACM进位制 30页 免费 回溯与搜索初步 76页 2财富值 ACM图论 41页 2财富值如要投诉违规内容,请到百度文库投诉中心;如要提出...

第十一章_回溯法1

不同点: (1)回溯法的求解目标是找出 T 中满足约束条件的所有解,而分支限界法 的求解目标则是找出满足约束条件的—个解. 或是在满足约束条件的解中找出使 某...

(1)回溯

(1)回溯_工学_高等教育_教育专区。ACM之回溯例题及解析1.1 马拦过河卒 【问题描述】 棋盘上 A 点有个过河卒,需要走到目标 B 点。卒行走的规则:可以向下...

pascal教程1--回溯法

回溯1.1 过河卒 knight.???(pas, c, cpp) knight.exe knight.in knight.out 源程序名 可执行文件名 输入文件名 输出文件名 【问题描述】 ...

回溯法练习2-1

回溯法练习2-1_IT认证_资格考试/认证_教育专区 暂无评价|0人阅读|0次下载|举报文档 回溯法练习2-1_IT认证_资格考试/认证_教育专区。1、序关系计数问题 用...

实验五-1 回溯法

实验五-1 回溯法_数学_自然科学_专业资料。算法设计与分析实验报告 学号 姓名 教师 实验五 回溯法 班级 上课时间 上课地点 1. 实验目的 1.1.掌握回溯法的基本...

0-1背包问题(回溯法)

0-1 背包问题(回溯法) 实验报告 姓 名: 学 号: 指导老师: 一.算法设计名称: 0-1 背包问题(回溯法) 二.实验内容 问题描述: 给定 n 种物品和一背包。...

4 回溯法 (1)

4 回溯法 (1)_数学_自然科学_专业资料。n-皇后问题的回溯算法 n_Queens 描述: n_Queens(int n) 1 x[1] ← 0; 2 k ← 1; 3 while k > 0 4 do...

回溯算法 0-1 背包算法 c++

回溯算法 0-1 背包算法 2009-12-03 10:38:04 阅读 218 评论 0 【实验目的】 学习掌握回溯算法。 字号:大中小 订阅 . 【实验内容】 用回溯法求解 0—1 ...
更多相关标签:
回溯法 0 1背包问题 | 0 1背包回溯法 | 0 1背包问题 回溯 | 奇异人生1怎么回溯 | 回溯法 | 回溯算法 | 回溯迷踪 | n皇后问题 回溯法 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com