溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇內容主要講解“回溯算法是什么”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“回溯算法是什么”吧!
一、什么是回溯算法
回溯算法實際上是一個類似枚舉的搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解，當發現已不滿足求解條件時，就“回溯”返回，嘗試別的路徑。許多復雜的，規模較大的問題都可以使用回溯法，有“通用解題方法”的美稱。
回溯算法實際上是一個類似枚舉的深度優先搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解，當發現已不滿足求解條件時，就“回溯”返回（也就是遞歸返回），嘗試別的路徑。
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進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
