欢迎大家访问我的个人搭建的博客Vfdxvffd\’s Blog
回溯是五大常用算法策略之一，它的核心思想其实就是将解空间看作是一棵树的结构，从树根到其中一个叶子节点的路径就是一个可能的解，根据约束条件，即可得到满足要求的解。求解问题时，发现到某个节点而不满足求解的条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。下面通过几个例子来讨论这个算法策略。

有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的具有最短路程的环路。（最后回到原来的城市），也就是说给一个无向带权图G<V,E>,用一个邻接矩阵来存储两城市之间的距离（即权值），要求一个最短的路径。

我们设置一组数据如下：4个城市，之间距离如下图所示，默认从0号城市出发

在这里插入图片描述

由此我们可以画出一棵解空间树：（只画了一部分，右边同理）

在这里插入图片描述

按照这个解空间树，对其进行深度优先搜索，通过比较即可得到最优结果（即最短路径）

  1. package BackTrack;
  2. //解法默认从第0个城市出发，减小了问题难度，主要目的在于理解回溯策略思想
  3. public class Saleman {
  4. 	
  5. 	//货郎问题的回溯解法
  6.     static int[][] map = {
  7.             { 0,10,5,9},
  8.             {10,0,6,9},
  9.             { 5,6,0,3},
  10.             { 9,9,3,0}
  11.     };          //邻接矩阵
  12.     
  13.     public static final int N = 4;		//城市数量
  14.     static int Min = 10000;				//记录最短的长度
  15.     static int[] city = {1,0,0,0};		//默认第0个城市已经走过
  16.     static int[] road = new int[N];		//路线，road[i] = j表示第i个城市是第j个经过的
  17.     /**
  18.      * 
  19.      * @param city		保存城市是否被经过，0表示未被走过，1表示已经走过
  20.      * @param j			上一层走的是第几个城市
  21.      * @param len		此时在当前城市走过的距离总和
  22.      * @param level		当前所在的层数，即第几个城市
  23.      */
  24.     public static void travel(int[] city, int j, int len, int level) {
  25. 		if(level == N - 1) {	//到达最后一个城市
  26. 			/*do something*/
  27. 			if(len+map[j][0] < Min) {
  28. 				Min = len + map[j][0];
  29. 				for (int i = 0; i < city.length; i++) {
  30. 					road[i] = city[i];
  31. 				}
  32. 			}
  33. 			return;
  34. 		}
  35. 		for(int i = 0; i < N; i++) {
  36. 			if(city[i] == 0 && map[j][i] != 0) {	//第i个城市未被访问过，且上一层访问的城市并不是此城市
  37. 				city[i] = level+2;			//将此城市置为已访问
  38. 				travel(city, i, len+map[j][i], level+1);
  39. 				city[i] = 0;			//尝试完上一层的路径后，将城市又置为未访问，以免影响后面的尝试情况，避免了clone数组的情况，节省内存开销
  40. 			}
  41. 		}
  42. 		
  43. 	}
  44.     
  45. 	public static void main(String[] args) {
  46. 		travel(city,0,0,0);
  47.         System.out.println(Min);
  48.         for (int i = 0; i < N; i++) {
  49. 			System.out.print(road[i]+" ");
  50. 		}
  51.         System.out.println("1");
  52. 	}
  53. }

要在n*n的国际象棋棋盘中放n个皇后，使任意两个皇后都不能互相吃掉。规则：皇后能吃掉同一行、同一列、同一对角线的任意棋子。求所有的解。n=8是就是著名的八皇后问题了。

  用一个position数组表示皇后的摆放位置，position[i] = j表示第i行皇后放在第j列，我们从第一行开始，对每一列进行尝试摆放，如果可行则继续第二行，同理第二行继续对每一列进行尝试，如果发现某一行不管放在哪一列都不可行，说明上面某行的摆放是不可行的，则回溯到上面一行，从摆放的那一列接着往下尝试……

  这道题的解空间树非常庞大，第一层8个节点，然后往下每一个节点又有8个孩子（包含了所有可行和不可行解，但都要尝试过去），所以有8^8种可能解。

在这里插入图片描述

  1. public class Empress {
  2.     final static int N = 8;                   //皇后个数
  3.     static int count = 0;                    //输出的结果个数
  4.     static int[] postion = new int[N];      //保存每一行皇后摆放的位置，position[i] = j表示第i行皇后放在第j列
  6.     /**
  7.      * @param row   判断第row行摆放是否合理
  8.      * @return      合理返回true，否则false
  9.      */
  10.     public static boolean IsOk(int row){
  11.         for (int i = 0; i < row; i++) {     //和前面的每一行进行对比
  12.             if(postion[i] == postion[row] || Math.abs(i-row) == Math.abs(postion[i] - postion[row])){
  13.                 //如果在同一列则postion[i] == postion[row]
  14.                 //如果在同一斜线上Math.abs(i-row) == Math.abs(postion[i] - postion[row])
  15.                 return false;
  16.             }
  17.         }
  18.         return true;
  19.     }
  21.     public static void Print(){
  22.         System.out.println("This is the No."+(++count)+" result:");
  23.         for (int i = 0; i < N; i++) {           //i为行序号
  24.             for (int j = 0; j < N; j++) {       //j为第i行皇后的列的序号
  25.                 if(postion[i] == j){    //不是皇后的拜访地址
  26.                     System.out.print("# ");
  27.                 }else{
  28.                     System.out.print("@ ");
  29.                 }
  30.             }
  31.             System.out.println();       //换行
  32.         }
  33.     }
  35.     /**
  36.      * @param row   尝试第row行皇后的摆放位置，找到可行位置就继续深度搜索下一行，否则在尝试完i的所有取值无果后回溯
  37.      */
  38.     public static void backtrack(int row){
  39.         if(row == N){       //若已经等于N，则说明0~N-1已经赋值完毕，直接打印返回
  40.             Print();
  41.             return;
  42.         }
  43.         for (int i = 0; i < N; i++) {
  44.             postion[row] = i;           //第row行皇后的位置在i处
  45.             if(IsOk(row)){
  46.                 backtrack(row+1);
  47.             }else{
  48.                 /**
  49.                  * 如果第row行的皇后拜访在i(0-N)处可行，则继续向下深度搜索，否则就直接让这层递归函数出栈
  50.                  * 此层函数出栈也就是当前结点不满足继续搜索的限制条件，即回溯到上一层，继续搜索上一层的下一个i值
  51.                  */
  52.             }
  53.         }
  54.     }
  56.     public static void main(String[] args) {
  57.         backtrack(0);
  58.     }
  59. }

给定n个重量为w1，w2，w3，…，wn，价值为v1，v2，v3，…，vn的物品和容量为C的背包，求这个物品中一个最有价值的子集，使得在满足背包的容量的前提下，包内的总价值最大。

这个问题的解空间树是一棵决策树，每个节点都有两个孩子节点，分别对应了是否将这个物品装入背包的两种情况，0表示不装入，1表示装入，则我们可以画出3件物品的解空间树

在这里插入图片描述

  1. package BackTrack;
  3. import java.util.Iterator;
  4. import java.util.LinkedList;
  5. import java.util.List;
  7. public class Package {
  8. 	
  9. 	//0-1背包问题，回溯解法
  10. 	public static final int N = 5;		//物品数量
  11. 	static int[] values = {4,5,2,1,3};	//物品的价值
  12. 	static int[] weights = {3,5,1,2,2};	//物品的质量
  13. 	public static final int C = 8;		//背包的容量
  14. 	static int MAX = -1;				//记录最大的价值
  15. 	static int[] bag = {0,0,0,0,0};		//物品放置情况，bag[i] = 0表示第i个物品未被装入，等于1则表示已装入
  16. 	static List<int[]> list = new LinkedList<int[]>();	//保存最优的结果，可能有多个结果，所以用链表装
  17. 	
  18. 	public static boolean IsOk(int[] bag, int level) {	//判断当前背包是否超重
  19. 		int weight = 0;
  20. 		for (int i = 0; i <= level; i++) {	//计算当前背包中所有的物品的总质量
  21. 			if(bag[i] == 1) {	//bag[i] == 1表示这个物品已被装入背包
  22. 				weight += weights[i];
  23. 				if(weight > C)
  24. 					return false;
  25. 			}
  26. 		}
  27. 		return true;
  28. 	}
  29. 	
  30. 	public static void MaxValue(int[] bag, int level) {
  31. 		if(level == N) {				//已经判断完最后一个物品
  32. 			//先计算当前总价值
  33. 			int value = 0;
  34. 			for (int i = 0; i < N; i++) {
  35. 				if(bag[i] == 1) {
  36. 					value += values[i];
  37. 				}圆排列
  38. 			}
  39. 			if(value > MAX) {
  40. 				list.clear();		//发现更优的结果
  41. 				MAX = value;
  42. 				list.add(bag.clone());
  43. 			}else if (value == MAX) {	//其他放置情况的最优解
  44. 				list.add(bag.clone());
  45. 			}
  46. 			return;
  47. 		}
  48. 		for (int i = 0; i < 2; i++) {
  49. 			bag[level] = i;
  50. 			if(IsOk(bag, level)) {
  51. 				MaxValue(bag, level+1);
  52. 			}
  53. 		}
  54. 	}
  56. 	public static void main(String[] args) {
  57. 		MaxValue(bag, 0);
  58. 		System.out.println(MAX);
  59. 		Iterator<int[]> iter = list.iterator();
  60. 		while(iter.hasNext()) {
  61. 			int[] temp = iter.next();
  62. 			for (int i = 0; i < temp.length; i++) {
  63. 				System.out.print(temp[i]+" ");
  64. 			}
  65. 			System.out.println();
  66. 		}
  67. 	}
  68. }

  给定无向连通图G=(V, E)和m种不同的颜色，用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中相邻的两个顶点有不同的颜色?
  这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的两个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。
  编程计算：给定图G=(V, E)和m种不同的颜色，找出所有不同的着色法。

形如下面这种情况：

在这里插入图片描述

采用回溯策略，对每一个顶点用每一个颜色作尝试，按上图这个例子，3种颜色为这个4个顶点的图着色的解空间树（包括所有可能解和不可能解）有34个可能解。即mn个可能解（m为颜色种数，n为节点个数）。

  1. package BackTrack;
  3. import java.util.Scanner;
  5. public class Paint {
  7. 	static int[][] p_Maxtrix = new int[4][4];		//图的邻接矩阵
  8. 	static int Colornum = 3;						//颜色数目
  9. 	static int[] result = {-1,-1,-1,-1};			//保存结果
  10. 	
  11. 	/**
  12. 	 * @param index         当前顶点的下标
  13. 	 * @param color			颜色的编号
  14. 	 * @return                     染色方案是否可行
  15. 	 */
  16. 	public static boolean IsOk(int index, int color) {		//判断是否可以染色
  17. 		for (int i = 0; i < p_Maxtrix.length; i++) {
  18. 			if(p_Maxtrix[index][i] == 1 && result[i] == color) {
  19. 				return false;
  20. 			}
  21. 		}
  22. 		return true;
  23. 	}
  24. 	
  25. 	public static void backtrack(int index) {
  26. 		if(index == p_Maxtrix.length) {			//完成最后一个顶点的着色，输出其中一种结果
  27. 			for (int i = 0; i < result.length; i++) {
  28.                 System.out.print(result[i]+" ");
  29.             }
  30.             System.out.println();
  31.             return;
  32. 		}
  33. 		for (int i = 0; i < Colornum; i++) {	//对每一种颜色进行尝试
  34. 			result[index] = i;
  35. 			if(IsOk(index, i)) {
  36. 				backtrack(index+1);
  37. 			}
  38. 			result[index] = -1;
  39. 		}
  40. 	}
  42. 	public static void main(String[] args) {
  43. 		Scanner in = new Scanner(System.in);
  44.         for (int i = 0; i <p_Maxtrix.length ; i++) {
  45.             for (int j = 0; j < p_Maxtrix.length; j++) {
  46.                 p_Maxtrix[i][j] = in.nextInt();
  47.             }
  48.         }
  49. 		backtrack(0);
  50. 	}
  51. }

给定n个大小不等的圆c1,c2,…,cn，现要将这n个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。例如，当n=3，且所给的3个圆的半径分别为1，1，2时，这3个圆的最小长度的圆排列如图所示。其最小长度为img。

img

算法思路：将每个圆在每个位置上的所有可能作全排列，找出最短距离。

  • swap函数：用于交换圆之间的顺序，将两个圆互换位置。

  • center函数：计算第t个圆的圆心的坐标，用于给x数组赋值。

  • compute函数：其实是在当将最后一个圆排列完成后的操作，计算出当前的排列的距离，与已知的最优解比较，若更优就更新最优解。

  • backtrack函数：对每一种排列组合进行回溯尝试。

    参考博文：圆排列

  1. package BackTrack;
  3. public class Round {
  4. 	
  5. 	public static final int N = 3;			//圆的数目
  6. 	static double min = 1000;				//最短距离
  7. 	static double[] x = new double[N];		//每个圆的圆心
  8. 	static int[] r = {1,1,2};				//每个圆的半径
  9. 	static int[] best = new int[N];			//最优解
  10. 	
  11. 	//交换函数，交换某两个圆的位置
  12. 	public static void swap(int[] a, int x, int y) {
  13. 		int temp1 = a[x];
  14.         int temp2 = a[y];
  15.         a[x] = temp2;
  16.         a[y] = temp1;位置
  17. 	}
  18. 	
  19. 	/**
  20.      *  对为什么要使用循环做一解释：
  21.      *      因为可能存在第x个圆，它太过于小，而导致其对第x-1和x+1，甚至其他的圆来说，第x个圆存在于不存在都是没影响的
  22.      *      取x-1，和x+1来说：可能x太小，x+1与x-1相切，所以计算第x+1圆心坐标的时候，只能以x-1的圆心与它的圆心来计算
  23.      *      所以要每次循环比较选择最大的那一个做半径
  24.      *      可以参考https://blog.csdn.net/qq_37373250/article/details/81477394中的图
  25.      */
  26. 	public static double center(int t) {
  27. 		double max = 0.0;				//默认第一个圆的圆心是0.0
  28. 		for(int i = 0; i < t; i++) {
  29. 			double temp = x[i]+2.0*Math.sqrt(r[i]*r[t]); 	//计算得到“以第i个圆的半径和待计算圆的半径”得出的圆心
  30. 			//取最大值
  31. 			if(temp > max) {
  32. 				max = temp;
  33. 			}
  34. 		}
  35. 		return max;
  36. 	}
  37. 	
  38. 	/**
  39.      * 针对为什么不能直接temp = x[N-1]+x[0]+r[N-1]+r[0]（直接用第一个圆到最后一个圆的圆心距离加上两圆半径）做一解释：
  40.      *      为避免第一个圆太小，而第二个圆太大，而导致第二个圆的边界甚至超过了第一个圆的边界，最右边同理
  41.      *      那也可以依次推出可能第三个，第四个...的边界超过了第一个圆的边界，右边同理，所以需要每一个都做一下比较
  42.      *      但是可以放心，x是按圆当前排列顺序放置圆心坐标的
  43.      */
  44. 	public static void compute() {			//计算按此排列得到的结果
  45. 		double low = 0, high = 0;			//分别表示最左边的边际，和最右边的边际
  46. 		for(int i = 0; i < N; i++) {
  47. 			if(x[i]-r[i] < low) {
  48. 				low = x[i]-r[i];
  49. 			}
  50. 			if(x[i]+r[i] > high) {
  51. 				high = x[i]+r[i];
  52. 			}
  53. 		}
  54. 		double temp = high - low;
  55. 		if(temp < min) {
  56. 			min = temp;
  57. 			for (int i = 0; i < N; i++) {
  58. 				best[i] = r[i];
  59. 			}
  60. 		}
  61. 	}
  62. 	
  63. 	public static void backtrack(int t) {
  64. 		if(t == N) {
  65. 			compute();
  66. 			//return;
  67. 		}
  68. 		for(int i = t; i < N; i++) {	//t之前的圆已经排好顺序了，可能不是最优解，但是一种可能解
  69. 			swap(r, t, i);
  70. 			double center_x = center(t);
  71. 			x[t] = center_x;
  72. 			backtrack(t+1);
  73. 			/*下面是使用了较为简陋的剪枝算法进行优化
  74. 			  if(center_x+r[i] < min) {
  75. 				x[t] = center_x;
  76. 				backtrack(t+1);
  77. 			}			  
  78. 			 */
  79. 			swap(r, t, i);			//恢复交换之前的
  80. 		}
  81. 	}
  82. 	public static void main(String[] args) {
  83. 		backtrack(0);
  84.         for (int i = 0; i < N; i++) {
  85.             System.out.print(best[i]+" ");
  86.         }
  87.         System.out.println();
  88.         System.out.println(min);
  90. 	}
  91. }

假设国家发行了n种不同面值的邮票，并且规定每张信封上最多只允许贴m张邮票。连续邮资问题要求对于给定的n和m的值，给出邮票面值的最佳设计，在1张信封上可贴出从邮资1开始，增量为1的最大连续邮资区间。例如，当n=5和m=4时，面值为(1,3,11,15,32)的5种邮票可以贴出邮资的最大连续邮资区间是1到70。

解法思路：解决这个问题其实不光用到回溯，还用到了前面的动态规划策略。

  • 首先要明确必须要有一张面值为1的邮票，否则连刚开始一元的邮资都无法贴出。
  • 然后就是第x张邮票的面值必须介于第x-1张邮票的面值+1和前x-1张邮票所能贴出的最大邮资+1之间（闭区间）
  • 明确前面两点后，回溯的方法就很简单了。每层都是在上一层的面值+1和上一层最大邮资+1之间对所有的可能进行尝试求解最优解。
  • 最后就是dp求解每一层的最大邮资问题了。拆解来看，分为向下dp和向右dp，具体dp的理解方法可以参考这篇博文，一些细节问题在下面注释中写出来了。连续邮资问题 
  1. package BackTrack;
  3. public class Postage {
  5. 	public static final int MAX_Postage = 300;	//最大邮资不应该超过这个值
  6. 	public static final int N = 6;								//所用邮票张数
  7. 	public static final int M = 5; 								//所用面值种数		
  8. 	public static int[] best = new int[M+1];					//存放最优解，即所有的面值best[0]不用于存储
  9. 	public static int[] x = new int[M+1];						//当前解
  10. 	public static int MAX = 0;									//最大邮资
  11. 	public static int[][] dp = new int[M+1][MAX_Postage];		//用于动态规划保存第x[0]到x[cur]的最大邮资，dp[i][j] = k表示用i种面值的邮票表示j元最少需要k张
  12. 	//应该将dp数组初始化到dp[1][i] = i;		即让第一层都等于张数		
  13. 	
  14. 	
  15. 	public static int findMax(int cur) {		
  16. 		if(cur == 1) {			//第一层，只能用面值为1的，能表达出的最大邮资为N（张数）
  17. 			return N;
  18. 		}
  19. 		//向下dp
  20. 		int j = 1;		//指示列坐标
  21. 		while (dp[cur-1][j] != 0) {
  22. 			//此处dp的思路其实就是利用动态规划解决0-1背包问题时的思路，对新加入面值的邮票用与不用？用了用几张的问题？
  23. 			//不用时
  24. 			dp[cur][j] = dp[cur-1][j];
  25. 			//用的时候，用几张？
  26. 			for(int i = 1; i*x[cur] <= j; i++) {		//i表示面值张数
  27. 				int temp = dp[cur-1][j-i*x[cur]] + i;	//dp[cur-1][j-i*x[cur]]表示除了新加入的面值之外前面所有的面值共同表达j-i*x[cur]元所需张数
  28. 				dp[cur][j] = Math.min(temp, dp[cur][j]);		//取最小的张数
  29. 			}
  30. 			j++;
  31. 		}
  32. 		
  33. 		//向右dp
  34. 		while(true) {
  35. 			int temp = MAX_Postage;		
  36. 			for(int i = 1; i <= cur; i++) {
  37. 				/**
  38. 	             * 这里很妙，因为向右dp时每次都是向右一个一个推进，所以我们从x[]的第一种面值开始往上加，直到超过限制张数，那么如果x[]的
  39. 	             * 第二种面值刚好能将前面的多个第一种替换，那就替换更新张数
  40. 	             * 反正意思就是每一次for循环是对前面的较小面值的邮票是一个浓缩的过程
  41. 	             */
  42. 				temp = Math.min(dp[cur][j-x[i]]+1, temp);
  43. 			}
  44. 			if(temp > N || temp == MAX_Postage) {     //不管怎么使用当前解x[]中的已知面值，都不能在张数限制内表达出j元
  45. 				break;
  46. 			}else {
  47. 				dp[cur][j] = temp; 
  48. 			}
  49. 			j++;
  50. 		}
  51. 		/**对下面这条语句做一个解释
  52.          * 确保同一层上一次dp的结果不会影响下一次**尝试**时的dp，因为可能上一次尝试的一个分支中dp时已经给dp[2][10]赋过值了，但如果没有这一句
  53.          * 就会导致后面的某次尝试时一个分支中dp的时候，向下dp的时候直接将dp[2][10]向下dp了，而事实上，应该向右dp的时候才给dp[2][10]赋值的
  54.          * 其实就是向回溯的下一层发一个信号，表示这块是我上一层dp停止的地方，过了这块可能就是别的回溯分支给dp赋的值了
  55.          */
  56. 		dp[cur][j] = 0; 
  57. 		return j-1;
  58. 	}
  59. 	
  60. 	public static void backtrack(int t) {						//t表示当前层数
  61. 		if(t == M) {	//已经选够最多的面值种类
  62. 			int max = findMax(t);
  63. 			if(max > MAX) {
  64. 				MAX = max;
  65. 				for (int i = 0; i < best.length; i++) {
  66. 					best[i] = x[i];
  67. 				}
  68. 			}
  69. 		//return;	
  70. 		}else {
  71. 			int temp = findMax(t);								//得到当前层的最大邮资	
  72. 			for(int i = x[t]+1; i <= temp+1; i++) {
  73. 				x[t+1] = i;
  74. 				backtrack(t+1);
  75. 			}			
  76. 		}
  77. 	}
  78. 	
  79. 	public static void main(String[] args) {
  80. 		for (int i = 0; i <= N; i++) {
  81. 			dp[1][i] = i;
  82. 		}
  83. 		x[0] = 0;
  84. 		x[1] = 1;
  85. 		backtrack(1);
  86. 		System.out.println(MAX);
  87. 		for (int i = 0; i < best.length; i++) {
  88. 			System.out.print(best[i]+" ");
  89. 		}
  90. 	}
  91. }

版权声明：本文为vfdxvffd原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/vfdxvffd/p/12484932.html