文章插图
算法四：回溯法
1、概念
回溯算法实际上一个类似枚举的搜索尝试过程 ， 主要是在搜索尝试过程中寻找问题的解 ， 当发现已不满足求解条件时 ， 就“回溯”返回 ， 尝试别的路径 。
回溯法是一种选优搜索法 ， 按选优条件向前搜索 ， 以达到目标 。但当探索到某一步时 ， 发现原先选择并不优或达不到目标 ， 就退回一步重新选择 ， 这种走不通就退回再走的技术为回溯法 ， 而满足回溯条件的某个状态的点称为“回溯点” 。
许多复杂的 ， 规模较大的问题都可以使用回溯法 ， 有“通用解题方法”的美称 。
2、基本思想
在包含问题的所有解的解空间树中 ， 按照深度优先搜索的策略 ， 从根结点出发深度探索解空间树 。当探索到某一结点时 ， 要先判断该结点是否包含问题的解 ， 如果包含 ， 就从该结点出发继续探索下去 ， 如果该结点不包含问题的解 ， 则逐层向其祖先结点回溯 。（其实回溯法就是对隐式图的深度优先搜索算法） 。
若用回溯法求问题的所有解时 ， 要回溯到根 ， 且根结点的所有可行的子树都要已被搜索遍才结束 。
而若使用回溯法求任一个解时 ， 只要搜索到问题的一个解就可以结束 。
3、用回溯法解题的一般步骤：
（1）针对所给问题 ， 确定问题的解空间：
首先应明确定义问题的解空间 ， 问题的解空间应至少包含问题的一个（最优）解 。
（2）确定结点的扩展搜索规则
（3）以深度优先方式搜索解空间 ， 并在搜索过程中用剪枝函数避免无效搜索 。
4、算法实例：求子集问题
public class 回溯法_求子集问题 {
private static int[] s = {2,2,3};
private static int n = s.length;
private static int[] x = new int[n];
/**
* 输出集合的子集
* @param limit 决定选出特定条件的子集
* 注：all为所有子集,num为限定元素数量的子集,
* sp为限定元素奇偶性相同 ， 且和小于8 。
*/
public static void all_subset(String limit){
switch(limit){
case "all":backtrack(0);break;
case "num":backtrack1(0);break;
case "sp":backtrack2(0);break;
}
}
/**
* 回溯法求集合的所有子集 ， 依次递归
* 注：是否回溯的条件为精髓
* @param t
*/
private static void backtrack(int t){
if(t >= n)
output(x);
else
for (int i = 0; i <= 1; i++) {
x[t] = i;
backtrack(t+1);
}
}
/**
* 回溯法求集合的所有(元素个数小于4)的子集 ， 依次递归
* @param t
*/
private static void backtrack1(int t){
if(t >= n)
output(x);
else
for (int i = 0; i <= 1; i++) {
x[t] = i;
if(count(x, t) < 4)
backtrack1(t+1);
}
}
/**
* (剪枝)
* 限制条件：子集元素小于4,判断0~t之间已被选中的元素个数 ，
* 因为此时t之后的元素还未被递归,即决定之后的元素
* 是否应该被递归调用
* @param x
* @param t
* @return
*/
private static int count(int[] x, int t) {
int num = 0;
for (int i = 0; i <= t; i++) {
if(x[i] == 1){
num++;
}
}
return num;
}
/**
* 回溯法求集合中元素奇偶性相同 ， 且和小于8的子集,依次递归
* @param t
*/
private static void backtrack2(int t){
if(t >= n)
output(x);
else
for (int i = 0; i <= 1; i++) {
x[t] = i;
if(legal(x, t))
backtrack2(t+1);
}
}
/**
* 对子集中元素奇偶性进行判断 ， 还需元素的数组和小于8
* @param x
* @param t
* @return
*/
private static boolean legal(int[] x, int t) {
boolean bRet = true; //判断是否需要剪枝
int part = 0; //奇偶性判断的基准
for (int i = 0; i <= t; i++) { //选择第一个元素作为奇偶性判断的基准
if(x[i] == 1){
part = i;
break;
}
}
for (int i = 0; i <= t; i++) {
if(x[i] == 1){
bRet &= ((s[part] - s[i]) % 2 == 0);
}
}
int sum = 0;
for(int i = 0; i <= t; i++){
if(x[i] == 1)
sum += s[i];
推荐阅读
- 简谈企业最常用的三种安卓app开发语言
- 解开“肺功能”检查五大疑惑
- 八大常用茶叶贮存方法简介
- 你必需知道的10个 Nginx 常用命令
- mysql之my.cnf/my.ini常用配置整理
- JAVA手写tomcat，带你了解tomcat的原理，附代码
- 普洱茶选购要掌握五大原则
- 茶叶产品4大常用有效贮存方法
- 中国古代五大酷刑是什么 中国古代最残酷的刑
- 简单了解Java消息队列