原文:http://leihong511.blog.163.com/blog/static/47256469200962353650348/
如果上期的“百钱买百鸡”中鸡的种类数是变化的,用枚举法就无能为力了,这里介绍另一种算法——回溯法。
回溯法是一种既带有系统性又带有跳跃性的搜索法,它的基本思想是:在搜索过程中,当探索到某一步时,发现原先的选择达不到目标,就退回到上一步重新选择。它主要用来解决一些要经过许多步骤才能完成的,而每个步骤都有若干种可能的分支,为了完成这一过程,需要遵守某些规则,但这些规则又无法用数学公式来描述的一类问题。下面通过实例来了解回溯法的思想及其在计算机上实现的基本方法。
例1、从N个自然数(1,2,…,n)中选出r个数的所有组合。
算法分析:设这r个数为a1,a2,…ar,把它们从大到小排列,则满足:
(1) a1>a2>…>ar;
(2) 其中第i位数(1<=i<=r)满足ai>r-i;
我们按以上原则先确定第一个数,再逐位生成所有的r个数,如果当前数符合要求,则添加下一个数;否则返回到上一个数,改变上一个数的值再判断是否符合要求,如果符合要求,则继续添加下一个数,否则返回到上一个数,改变上一个数的值……按此规则不断循环搜索,直到找出r个数的组合,这种求解方法就是回溯法。
如果按以上方法生成了第i位数ai,下一步的的处理为:
(1) 若ai>r-i且i=r,则输出这r个数并改变ai的值:ai=ai-1;
(2) 若ai>r-i且i≠r,则继续生成下一位ai+1=ai-1;
(3) 若ai<=r-i,则回溯到上一位,改变上一位数的值:ai-1=ai-1-1;
算法实现步骤:
第一步:输入n,r的值,并初始化; i:=1;a[1]:=n;
第二步:若a[1]>r-1则重复:
若a[i]>r-i,①若i=r,则输出解,并且a[i]:=a[i]-1;
②若i<>r,则继续生成下一位:a[i+1]:=a[i]-1; i:=i+1;
若 a[i]<=r-i,则回溯:i:=i-1; a[i]:=a[i]-1;
第三步:结束;
程序实现
var n,r,i,j:integer;
a:array[1..10] of integer;
begin
readln(n,r);i:=1;a[1]:=n;
repeat
if a[i]>r-i then {符合条件 }
if i=r then {输出}
begin
for j:=1 to r do write(a[j]:3);
writeln;
a[i]:=a[i]-1;
end
else {继续搜索}
begin a[i+1]:=a[i]-1; i:=i+1;end
else{回溯}
begin i:=i-1; a[i]:=a[i]-1;end;
until a[1]=r-1;
end.
下面我们再通过另一个例子看看回溯在信息学奥赛中的应用。
例2 数的划分(noip2001tg)
问题描述 整数n分成k份,且每份不能为空,任意两份不能相同(不考虑顺序)。
例如:n=7,k=3,下面三种分法被认为是相同的。
1,1,5; 1,5,1; 5,1,1;
问有多少种不同的分法。
输入:n,k (6<n<=200,2<=k<=6)
输出:一个整数,即不同的分法。
样例
输入: 7 3
输出:4 {四种分法为:1,1,5; 1,2,4; 1,3,3; 2,2,3;}
算法分析:此题可以用回溯法求解,设自然数n拆分为a1,a2,…,ak,必须满足以下两个条件:
(1) n=a1+a2+…+ak ;
(2) a1<=a2<=…<=ak (避免重复计算);
现假设己求得的拆分数为a1,a2,…ai,且都满足以上两个条件,设sum=n-a1-a2-…-ai,我们根据不同的情形进行处理:
(1) 如果i=k,则得到一个解,则计数器t加1,并回溯到上一步,改变ai-1的值;
(2) 如果i<k且sum>=ai,则添加下一个元素ai+1;
(3) 如果i<k且sum<ai,则说明达不到目标,回溯到上一步,改变ai-1的值;
算法实现步骤如下:
第一步:输入自然数n,k并初始化;t:=0; i:=1;a[i]:=1; sum:=n-1; nk:=n div k;
第二步:如果a[1]<=nk 重复:
若i=k,搜索到一个解,计数器t=t+1;并回溯;
否则:①若sum>=a[i]则继续搜索;
②若sum<a[i]则回溯;
搜索时,inc(i);a[i]:=a[i-1];sum:=sum-a[i];
回溯时,dec(i); inc(a[i]); sum:=sum+a[i+1]-1;
第三步:输出。
程序如下:
var
n,nk,sum,i,k:integer;
t:longint;
a:array[1..6]of integer;
begin
readln(n,k);
nk:=n div k;
t:=0; i:=1;a[i]:=1; sum:=n-1;{初始化}
repeat
if i=k then{判断是否搜索到底}
begin inc(t); dec(i);inc(a[i]); sum:=sum+a[i+1]-1; end {回溯}
else begin
if sum>=a[i] then {判断是否回溯}
begin inc(i);a[i]:=a[i-1];sum:=sum-a[i];end{继续搜}
else begin dec(i); inc(a[i]); sum:=sum+a[i+1]-1; end;{回溯}
end;
until a[1]>nk;
writeln(t);
end.
回溯法是通过尝试和纠正错误来寻找答案,是一种通用解题法,在NOIP中有许多涉及搜索问题的题目都可以用回溯法来求解
分享到:
相关推荐
回溯法回溯法回溯法回溯法回溯法回溯法回溯法回溯法回溯法回溯法回溯法回溯法回溯法回溯法
算法设计与分析 3回溯法—地图填色问题 pre ppt 回溯法地图填色 路径选择(MRV DH) 剪枝策略(向前检测和颜色轮换) 运行时间随图规模增大而增大 图密度 (1) 通过本次实验,我了解到回溯法的基本思想: 不断尝试...
算法设计与分析-回溯法地图填色源代码.cpp (1) 回溯法算法设计思想。 (2) 地图填色问题的回溯法解法。 (1) 通过本次实验,我了解到回溯法的基本思想: 不断尝试每一条可行路径,出错时回退,直到找到可行解或全部...
最优装载问题——回溯法 最优装载问题——回溯法 最优装载问题——回溯法
0-1背包的回溯法求解0-1背包的回溯法求解.rar
主要介绍了Python基于回溯法解决01背包问题,结合实例形式分析了Python回溯法采用深度优先策略搜索解决01背包问题的相关操作技巧,需要的朋友可以参考下
回溯法解决01背包问题c语言.rar 已调通
实验四:回溯法 【实验目的】 深入理解分治法的算法思想,应用分治法解决实际的算法问题。 【实验性质】 综合性实验 【实验内容与要求】 实验要求】 设下图G=(V,E)是一连通无向图,有3种颜色,用这些颜色为G的各顶点...
有许多问题,当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时,往往要使用回溯法。 回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法。这种方法适用于解一些...
回溯法解决数独问题-2.docx
提供各种常见的回溯法案例的解决思路,附该算法的算法的主要步骤及各步含义。
用回溯法实现陈列馆问题会帮助你理解回溯法的应用!
3) 回溯法求解问题的一般思路,回溯法求解本问题的思路及其C/C++程序实现与算法的效率分析。 4) 分支限界法求解问题的一般思路,分支限界法求解本问题的思路及其C/C++程序实现与算法的效率分析。 有代码!!
回溯法 0-1背包问题 计算机算法设计与分析 回溯法 背包问题
采用回溯法解决旅行商问题,获得最短路径回路。
回溯法解数独问题,能够准确给出数独的解.
经典的算法,八皇后问题,c++实现,回溯法
回溯法的基本思想:确定了解空间的组织结构后,回溯法就从开始结点(根结点)出发,以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点,同时也成为当前的扩展结点。在当前的扩展结点处,搜索向纵深...
算法设计作业,用c++编写的,回溯法求解n皇后问题 运行环境VC6.0