本篇内容主要讲解“回溯算法是什么”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“回溯算法是什么”吧!
一、什么是回溯算法
回溯算法实际上是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
回溯算法实际上是一个类似枚举的深度优先搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回（也就是递归返回），尝试别的路径。
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 List<String> generateParenthesis(int n)
{
List<String> list = new ArrayList<>();
add_list(list, "(", 1, n * 2);
return list;
}
//书写递归函数
public void add_list(List<String> 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<String> generater(int n) {
List<String> result=new ArrayList<String>();
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<String> 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);
}
}
}到此，相信大家对“回溯算法是什么”有了更深的了解，不妨来实际操作一番吧！这里是亿速云网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
