回溯的基本思想是:从一个给定的起始位置,我们希望到达一个目的位置。我们重复地进行选择(可能是猜测)下一个位置应当是什么。如果一个给定的选择是有效的,即新的位置可能位于通向目的位置的途径中,则前进到这个新的位置,然后继续。如果一个给定的选择通向了死胡同 ,则回到前面的位置,进行其他的选择。回溯就是通过一系列位置选择到达目的位置,并且在不能到达目的位置时
反向退回的策略。
回溯类的通用接口如下:
import java.util.*;
public interface Application{
//如果位置pos为通向目标位置的路径上,返回true,否则返回false
boolean valid(Position pos);
//标记位置pos,这个位置pos可能在目标路径上
void record(Position pos);
//若pos是目标位置,返回true,否则,返回false
boolean done(Position pos);
//标记位置pos,此位置不在目标路径上
void undo(Position pos);
//返回路径的字符串
String toString();
//枚举从当前位置开始,所有可能的下一步位置
Iterator iterator(Position pos);
典型的回溯的代码:
public boolean tryToSolve(Position pos){
boolean success=false;
Iterator itr=app.iterator(pos);
while(!success&&itr.hasNext()){
pos=(Position)itr.next();
if(app.valid(pos)){
app.record(pos);
if(app.done(pos))
success=true;
else{
success=tryToSolve(pos);
if(!success)
app.undo(pos);
}
}
}
}
return success;
}
注意:从pos位置开始的移动选择,有三种可能性:
1) 其中的一个选择是目的位置。那么while循环结束,返回true,说明成功结束。
2) 其中的一个选择是有效选择,但不是目的位置。那么再次调用tryToSolve方法,从这个有效选择开始。
3)没有一个选择是有效的。那么while循环结束,返回false,说明从当前位置无法到达目标位置。
tryToSolve方法的参数表示一个有效的、记录了的位置。
分享到:
相关推荐
回溯法回溯法回溯法回溯法回溯法回溯法回溯法回溯法回溯法回溯法回溯法回溯法回溯法回溯法
算法分析论文——回溯算法的应用 包括算法的即便额概念,思想,回溯法应用及其在某些方面的改进
最优装载问题——回溯法 最优装载问题——回溯法 最优装载问题——回溯法
n 皇后 回溯法n 皇后 回溯法 n 皇后 回溯法 n 皇后 回溯法 n 皇后 回溯法 n 皇后 回溯法
算法设计与分析 3回溯法—地图填色问题 pre ppt 回溯法地图填色 路径选择(MRV DH) 剪枝策略(向前检测和颜色轮换) 运行时间随图规模增大而增大 图密度 (1) 通过本次实验,我了解到回溯法的基本思想: 不断尝试...
回溯法解决01背包问题c语言.rar 已调通
0-1背包的回溯法求解0-1背包的回溯法求解.rar
算法设计与分析-回溯法地图填色源代码.cpp (1) 回溯法算法设计思想。 (2) 地图填色问题的回溯法解法。 (1) 通过本次实验,我了解到回溯法的基本思想: 不断尝试每一条可行路径,出错时回退,直到找到可行解或全部...
算法分析与设计回溯法完整实验报告(包含java代码)
回溯法解决数独问题-2.docx
n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---...
主要介绍了Python基于回溯法解决01背包问题,结合实例形式分析了Python回溯法采用深度优先策略搜索解决01背包问题的相关操作技巧,需要的朋友可以参考下
提供各种常见的回溯法案例的解决思路,附该算法的算法的主要步骤及各步含义。
采用回溯法解决旅行商问题,获得最短路径回路。
搜索练习,回溯法,搜索练习,回溯法。。。
回溯法 0-1背包问题 计算机算法设计与分析 回溯法 背包问题
该资源是关于 n后问题(回溯法)的算法的实现代码
算法设计作业,用c++编写的,回溯法求解n皇后问题 运行环境VC6.0
回溯法解数独问题,能够准确给出数独的解.
经典的算法,八皇后问题,c++实现,回溯法