回溯算法是什么
本篇内容主要讲解"回溯算法是什么"，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习"回溯算法是什么"吧!
一、什么是回溯算法
回溯算法实际上是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就"回溯"返回，尝试别的路径。许多复杂的，规模较大的问题都可以使用回溯法，有"通用解题方法"的美称。
回溯算法实际上是一个类似枚举的深度优先搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就"回溯"返回（也就是递归返回），尝试别的路径。
八皇后问题：
N皇后问题要求求解在N*N的棋盘上放置N个皇后，并使各皇后彼此不受攻击的所有可能的棋盘布局。皇后彼此不受攻击的约束条件是：任何两个皇后均不能在棋盘上同一行、同一列或者同一对角线上出现。
由于N皇后问题不允许两个皇后在同一行，所以，可用一维数组X表示N皇后问题的解，X[i]表示第i行的皇后所在的列号。关键是代码中把待处理行中不可用的点找出来。
由上述X数组求解N皇后问题，保障了任意两个皇后不在同一行上，而判定皇后彼此不受攻击的其他条件，可以描述如下：
X[i] = X[s]，则第i行与第s行皇后在同一列上。
如果第i行的皇后在第j列，第s行皇后在第t列，即X[i] = j和X[s] = t，则只要 i-j = s-t 或者 i+j = s+t，说明两个皇后在同一对角线上。
对两个等式进行变换后，得到结论：只要|i-s| = |j-t|（即i-s = X[i]-X[s]），则皇后在同一对角线上。
解N皇后问题需要遍历解空间树，遍历中要随时判定当前结点棋盘布局是否符合要求，符合要求则继续向下遍历，直至判断得到一个满足约束条件的叶子结点，从而获得一个满足要求的棋盘布局；不符合要求的结点将被舍弃（称之为剪枝），并回溯到上一层的结点继续遍历。当整棵树遍历结束时，已获得所有满足要求的棋盘布局。
public class Queen{ // 方案数 public static int num = 0; // 皇后数 public static final int MAXQUEEN = 8; // 定义数组，表示MAXQUEEN列棋子中皇后摆放位置 public static int[] cols = new int[MAXQUEEN]; public void getCount(int n) { boolean[] rows = new boolean[MAXQUEEN]; for (int m = 0; m < n; m++) { // rows 为true 表名不可以放，垂直上面不可放 rows[cols[m]] = true; int d = n - m; // y=x 这条线 往前判断 if (cols[m] - d >= 0) { rows[cols[m] - d] = true; } // y=-x这条线 往右边判断 if (cols[m] + d <= (MAXQUEEN - 1)) { rows[cols[m] + d] = true; } } for (int i = 0; i < MAXQUEEN; i++) { if (rows[i]) { //如果这一行中的 某个列位置 不可放置则继续看下个位置。 continue; } cols[n] = i; //如果下面还没填充完毕 则仍需合法位置 if (n < MAXQUEEN - 1) { getCount(n + 1); } else { // 找到完整的一套方案 num++; printQueen(); } } } private void printQueen() { System.out.println("第">背包问题：
问题：给定n种物品和一背包。物品i的重量是wi，其价值为pi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
分析：问题是n个物品中选择部分物品，可知，问题的解空间是子集树。比如物品数目n=3时，其解空间树如下图，边为1代表选择该物品，边为0代表不选择该物品。使用x[i]表示物品i是否放入背包，x[i]=0表示不放，x[i]=1表示放入。回溯搜索过程，如果来到了叶子节点，表示一条搜索路径结束，如果该路径上存在更优的解，则保存下来。如果不是叶子节点，是中点的节点（如B），就遍历其子节点（D和E），如果子节点满足剪枝条件，就继续回溯搜索子节点。
【整体思路】
01背包属于找最优解问题，用回溯法需要构造解的子集树。对于每一个物品i，对于该物品只有选与不选2个决策，总共有n个物品，可以顺序依次考虑每个物品，这样就形成了一棵解空间树： 基本思想就是遍历这棵树，以枚举所有情况，最后进行判断，如果重量不超过背包容量，且价值最大的话，该方案就是最后的答案。深度遍历的意思。
package practice; /** * 给定n种物品和一背包。物品i的重量是wi，其价值为pi，背包的容量为C。 问应如何选择装入背包的物品，使得装入背包中物品的总价值最大? * * @author fulisha * */public class _05 { static int BestValue = 0; // 最优值；当前的最大价值，初始化为0 static int[] BestX; // 最优解；BestX[i]=1代表物品i放入背包，0代表不放入 // static int CurWeight = 0; // 当前放入背包的物品总重量 static int CurValue = 0; // 当前放入背包的物品总价值 static int N = 3;// 物品数量 static int C = 16;// 物品的总容量 static int W[] = { 10, 8, 5 }; // 每个物品的重量 static int v[] = { 5, 4, 1 };// 每个物品的价值 static int x[] = { 0, 0, 0 };// x[i]=1代表物品i放入背包，0代表不放入 public static int backtrack(int t) { // 如果是子节点 当前价值和最佳价值做判断 保存最佳价值 if (t > N - 1) { if (CurValue > BestValue) { BestValue = CurValue; } return BestValue; } // 如果不是子节点 对子节点进行遍历 else { // 就两种情况 取或不取 用0/1表示 for (int i = 0; i <= 1; i++) { x[t] = i; if (i == 0) { // 如果是不取 就不需要进行判断 直接到下一个节点 backtrack(t + 1); } else // 放入背包就进行约束条件 判断放入背包的东西是否合法 { if (CurWeight + W[t] <= C) { CurWeight += W[t]; CurValue += v[t]; // 当东西装进入背包后你可以进行对下个商品的判断了 backtrack(t + 1); //能执行以下两个语句就说明你回溯到了上一个节点 // 所以你就需要恢复现场 把你刚刚拿的东西退出来 // 我们要冲上一个节点又要重新来遍历 如果不减你就会多加一遍 CurWeight -= W[t]; CurValue -= v[t]; } } } } return BestValue; } public static void main(String[] args) { backtrack(0); System.out.println(BestValue); for (int i = 0; i < 3; i++) { // System.out.println(BestX[i]); } } }也可以考虑剪枝的操作哦：剪枝操作
迷宫问题
首先我们定义一个 n * n 的二维数组，模拟迷宫，用2这个数字表示迷宫的墙壁 ，0表示迷宫的路线 ，那么我们主要的思路就是 在迷宫的入口 判断入口的上下左右 哪一个方向不是墙壁 我们则进入进去，同时我们用1 这个数字表示走过的路线 0表示不通的路线 这就是我们大致的思路，关键是用完后记得把节点环境恢复下。
public class TestMaze{ // 定义一个二维数组做迷宫 private int[][] maze = null; //表示此迷宫一共有几种走法 private int count = 0; // 迷宫的开始位置和结束位置的坐标 private static int startI, startJ, endI, endJ; private void setStart(int i, int j) { startI = i; startJ = j; } private void setEnd(int i, int j) { endI = i; endJ = j; } private void show() { System.out.println("第">{2, 2, 2, 2, 2, 2, 2, 2}, {2, 0, 0, 0, 0, 2, 2, 2}, {2, 0, 2, 0, 0, 0, 2, 2}, {2, 0, 0, 2, 0, 2, 0, 2}, {2, 0, 0, 2, 0, 2, 2, 0}, {2, 0, 2, 0, 0, 0, 0, 2}, {2, 0, 0, 0, 0, 2, 0, 2}, {2, 2, 2, 2, 2, 2, 2, 2}}; myMaze.maze = maze; myMaze.setStart(1, 1); myMaze.setEnd(6, 6); myMaze.play(1, 1); }}生成有效的括号组合：
给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。括号只有{}[]()这三种。
例如，给出 n = 3，生成结果为：
[ "((()))", "(()())", "(())()", "()(())", "()()()"]
解法：
/** * list：用来存储符合要求的括号组合。 * 局部变量temp:表示当前函数的括号组成样式。 * 计数器x：判断递归次数，限制其底界。 * 总的形成括号对数n。 * */ public ListgenerateParenthesis(int n) { List list = new ArrayList<>(); add_list(list, "(", 1, n * 2); return list; } //书写递归函数 public void add_list(List list, String temp, int x, int n) { x++; if (x <= n) { // 尽可能罗列 括号的存在 add_list(list, temp + "(", x, n); add_list(list, temp + ")", x, n); } if (x > n) { //在这里写判断条件是否负荷有效的括号组合 char[] k = temp.toCharArray(); //计数器 int timer = 0; for (int i = 0; i < k.length; i++) { //无论何时 ( 个数 >= ）个数 if (timer < 0 || timer > n / 2) { return; } else { if (k[i] == '(') { timer++; } else { timer--; } } } if (timer == 0) list.add(temp); } }====import java.util.ArrayList;import java.util.List; public class generateParenthesis { //参数有n对的{}()[], public static List generater(int n) { List result=new ArrayList (); generaterOneByOne("",result,n,n); return result; } /** * left:左边的括号就n个 * right:右边的括号有n个 * 思想： * 必须先放左边的括号，以递归的方式，然后直到左边的括的数目小于0时，以及右边的括号为0时，截止并放到结果中 * 右边的括号要后放：也就是right>left，保证右括号大于左边括号的数目 * @param substring * @param result * @param left * @param right */ private static void generaterOneByOne(String substring, List result, int left, int right) { if (left==0&&right==0) { result.add(substring); return; } if (left>0) { generaterOneByOne(substring+"(", result, left-1, right); } if (right>left) { generaterOneByOne(substring+')', result, left, right-1); } } }
到此，相信大家对"回溯算法是什么"有了更深的了解，不妨来实际操作一番吧！这里是网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！
