五⼤常见算法策略之——回溯策略
回溯策略
欢迎⼤家访问我的个⼈搭建的博客
回溯是五⼤常⽤算法策略之⼀，它的核⼼思想其实就是将解空间看作是⼀棵树的结构，从树根到其中⼀个叶⼦节点的路径就是⼀个可能的解，根据约束条件，即可得到满⾜要求的解。求解问题时，发现到某个节点⽽不满⾜求解的条件时，就“回溯”返回，尝试别的路径。回溯法是⼀种选优搜索法，按选优条件向前搜索，以达到⽬标。下⾯通过⼏个例⼦来讨论这个算法策略。
货郎问题
有⼀个推销员，要到n个城市推销商品，他要找出⼀个包含所有n个城市的具有最短路程的环路。（最后回到原来的城市），也就是说给⼀个⽆向带权图G<V,E>,⽤⼀个邻接矩阵来存储两城市之间的距离（即权值），要求⼀个最短的路径。
我们设置⼀组数据如下：4个城市，之间距离如下图所⽰，默认从0号城市出发
由此我们可以画出⼀棵解空间树：（只画了⼀部分，右边同理）
按照这个解空间树，对其进⾏深度优先搜索，通过⽐较即可得到最优结果（即最短路径）
package BackTrack;
//解法默认从第0个城市出发，减⼩了问题难度，主要⽬的在于理解回溯策略思想
public class Saleman {
红烧茄子的做法//货郎问题的回溯解法
static int[][] map ={
{0,10,5,9},
{10,0,6,9},
邓稼先的成就{5,6,0,3},
{9,9,3,0}
};//邻接矩阵
public static final int N =4;//城市数量
static int Min =10000;//记录最短的长度
static int[] city ={1,0,0,0};//默认第0个城市已经⾛过
static int[] road =new int[N];//路线，road[i] = j表⽰第i个城市是第j个经过的
/**
*
* @param city 保存城市是否被经过，0表⽰未被⾛过，1表⽰已经⾛过
* @param j 上⼀层⾛的是第⼏个城市
* @param len 此时在当前城市⾛过的距离总和
* @param level 当前所在的层数，即第⼏个城市
*/
public static void travel(int[] city,int j,int len,int level){
南医大研究生院if(level == N -1){//到达最后⼀个城市
/*do something*/
if(len+map[j][0]< Min){
Min = len + map[j][0];
for(int i =0; i < city.length; i++){
road[i]= city[i];
}
}
return;
}
for(int i =0; i < N; i++){
if(city[i]==0&& map[j][i]!=0){//第i个城市未被访问过，且上⼀层访问的城市并不是此城市
city[i]= level+2;//将此城市置为已访问
travel(city, i, len+map[j][i], level+1);
city[i]=0;//尝试完上⼀层的路径后，将城市⼜置为未访问，以免影响后⾯的尝试情况，避免了clone数组的情况，节省内存开销
}
}
}
public static void main(String[] args){
travel(city,0,0,0);
System.out.println(Min);
for(int i =0; i < N; i++){
System.out.print(road[i]+" ");
}
System.out.println("1");
}
}
⼋皇后问题
要在n*n的国际象棋棋盘中放n个皇后，使任意两个皇后都不能互相吃掉。规则：皇后能吃掉同⼀⾏、同⼀列、同⼀对⾓线的任意棋⼦。求所有的解。n=8是就是著名的⼋皇后问题了。
⽤⼀个position数组表⽰皇后的摆放位置，position[i] = j表⽰第i⾏皇后放在第j列，我们从第⼀⾏开始，对每⼀列进⾏尝试摆放，如果可⾏则继续第⼆⾏，同理第⼆⾏继续对每⼀列进⾏尝试，如果发现某⼀⾏不管放在哪⼀列都不可⾏，说明上⾯某⾏的摆放是不可⾏的，则回溯到上⾯⼀⾏，从摆放的那⼀列接着往下尝试…
这道题的解空间树⾮常庞⼤，第⼀层8个节点，然后往下每⼀个节点⼜有8个孩⼦（包含了所有可⾏和不可⾏解，但都要尝试过去），所以有8^8种可能解。
古筝教师
public class Empress {
final static int N =8;//皇后个数
static int count =0;//输出的结果个数
static int[] postion =new int[N];//保存每⼀⾏皇后摆放的位置，position[i] = j表⽰第i⾏皇后放在第j列
/**
* @param row 判断第row⾏摆放是否合理
* @return 合理返回true，否则fal
*/
public static boolean IsOk(int row){
for(int i =0; i < row; i++){//和前⾯的每⼀⾏进⾏对⽐围绕的近义词
if(postion[i]== postion[row]|| Math.abs(i-row)== Math.abs(postion[i]- postion[row])){
/
/如果在同⼀列则postion[i] == postion[row]
//如果在同⼀斜线上Math.abs(i-row) == Math.abs(postion[i] - postion[row])
return fal;
}
}
return true;
}
public static void Print(){
System.out.println("This is the No."+(++count)+" result:");
for(int i =0; i < N; i++){//i为⾏序号
for(int j =0; j < N; j++){//j为第i⾏皇后的列的序号
企业培训师
if(postion[i]== j){//不是皇后的拜访地址
System.out.print("# ");
}el{
System.out.print("@ ");
}
}
System.out.println();//换⾏
}
}
/**
仙客来好养吗* @param row 尝试第row⾏皇后的摆放位置，找到可⾏位置就继续深度搜索下⼀⾏，否则在尝试完i的所有取值⽆果后回溯
*/
public static void backtrack(int row){
if(row == N){//若已经等于N，则说明0~N-1已经赋值完毕，直接打印返回
Print();
return;
}
for(int i =0; i < N; i++){
postion[row]= i;//第row⾏皇后的位置在i处
if(IsOk(row)){
backtrack(row+1);
}el{
/
**
* 如果第row⾏的皇后拜访在i(0-N)处可⾏，则继续向下深度搜索，否则就直接让这层递归函数出栈
* 此层函数出栈也就是当前结点不满⾜继续搜索的限制条件，即回溯到上⼀层，继续搜索上⼀层的下⼀个i值
*/
}
}
}
public static void main(String[] args){
backtrack(0);
}
}
0-1背包的回溯解法
给定n个重量为w1，w2，w3，…，wn，价值为v1，v2，v3，…，vn的物品和容量为C的背包，求这个物品中⼀个最有价值的⼦集，使得在满⾜背包的容量的前提下，包内的总价值最⼤。
这个问题的解空间树是⼀棵决策树，每个节点都有两个孩⼦节点，分别对应了是否将这个物品装⼊背包的两种情况，0表⽰不装⼊，1表⽰装⼊，则我们可以画出3件物品的解空间树
package BackTrack;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
public class Package {
//0-1背包问题，回溯解法
public static final int N =5;//物品数量
static int[] values ={4,5,2,1,3};//物品的价值
static int[] weights ={3,5,1,2,2};//物品的质量
public static final int C =8;//背包的容量
static int MAX =-1;//记录最⼤的价值
static int[] bag ={0,0,0,0,0};//物品放置情况，bag[i] = 0表⽰第i个物品未被装⼊，等于1则表⽰已装⼊
static List<int[]> list =new LinkedList<int[]>();//保存最优的结果，可能有多个结果，所以⽤链表装
public static boolean IsOk(int[] bag,int level){//判断当前背包是否超重
int weight =0;
for(int i =0; i <= level; i++){//计算当前背包中所有的物品的总质量
if(bag[i]==1){//bag[i] == 1表⽰这个物品已被装⼊背包
weight += weights[i];
if(weight > C)
return fal;
}
}
return true;
}
public static void MaxValue(int[] bag,int level){
if(level == N){//已经判断完最后⼀个物品
//先计算当前总价值人间滋味
int value =0;
for(int i =0; i < N; i++){
if(bag[i]==1){
value += values[i];
}圆排列
}
if(value > MAX){
list.clear();//发现更优的结果
MAX = value;
list.add(bag.clone());
}el if(value == MAX){//其他放置情况的最优解
list.add(bag.clone());
}
return;
