回溯算法是什么

本篇內(nèi)容主要講解“回溯算法是什么”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“回溯算法是什么”吧!

一、什么是回溯算法

回溯算法實(shí)際上是一個類似枚舉的搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解，當(dāng)發(fā)現(xiàn)已不滿足求解條件時，就“回溯”返回，嘗試別的路徑。許多復(fù)雜的，規(guī)模較大的問題都可以使用回溯法，有“通用解題方法”的美稱。

回溯算法實(shí)際上是一個類似枚舉的深度優(yōu)先搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解，當(dāng)發(fā)現(xiàn)已不滿足求解條件時，就“回溯”返回（也就是遞歸返回），嘗試別的路徑。

八皇后問題：

N皇后問題要求求解在N*N的棋盤上放置N個皇后，并使各皇后彼此不受攻擊的所有可能的棋盤布局?；屎蟊舜瞬皇芄舻募s束條件是：任何兩個皇后均不能在棋盤上同一行、同一列或者同一對角線上出現(xiàn)。

由于N皇后問題不允許兩個皇后在同一行，所以，可用一維數(shù)組X表示N皇后問題的解，X[i]表示第i行的皇后所在的列號。關(guān)鍵是代碼中把待處理行中不可用的點(diǎn)找出來。

由上述X數(shù)組求解N皇后問題，保障了任意兩個皇后不在同一行上，而判定皇后彼此不受攻擊的其他條件，可以描述如下：

1. X[i] = X[s]，則第i行與第s行皇后在同一列上。

2. 如果第i行的皇后在第j列，第s行皇后在第t列，即X[i] = j和X[s] = t，則只要 i-j = s-t 或者 i+j = s+t，說明兩個皇后在同一對角線上。

對兩個等式進(jìn)行變換后，得到結(jié)論：只要|i-s| = |j-t|（即i-s = X[i]-X[s]），則皇后在同一對角線上。

解N皇后問題需要遍歷解空間樹，遍歷中要隨時判定當(dāng)前結(jié)點(diǎn)棋盤布局是否符合要求，符合要求則繼續(xù)向下遍歷，直至判斷得到一個滿足約束條件的葉子結(jié)點(diǎn)，從而獲得一個滿足要求的棋盤布局；不符合要求的結(jié)點(diǎn)將被舍棄（稱之為剪枝），并回溯到上一層的結(jié)點(diǎn)繼續(xù)遍歷。當(dāng)整棵樹遍歷結(jié)束時，已獲得所有滿足要求的棋盤布局。

public class Queen
{
	// 方案數(shù)
	public static int num = 0;
	// 皇后數(shù)
	public static final int MAXQUEEN = 8;
	// 定義數(shù)組，表示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])
			{
				//如果這一行中的 某個列位置 不可放置則繼續(xù)看下個位置。
				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。問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?
        分析：問題是n個物品中選擇部分物品，可知，問題的解空間是子集樹。比如物品數(shù)目n=3時，其解空間樹如下圖，邊為1代表選擇該物品，邊為0代表不選擇該物品。使用x[i]表示物品i是否放入背包，x[i]=0表示不放，x[i]=1表示放入。回溯搜索過程，如果來到了葉子節(jié)點(diǎn)，表示一條搜索路徑結(jié)束，如果該路徑上存在更優(yōu)的解，則保存下來。如果不是葉子節(jié)點(diǎn)，是中點(diǎn)的節(jié)點(diǎn)（如B），就遍歷其子節(jié)點(diǎn)（D和E），如果子節(jié)點(diǎn)滿足剪枝條件，就繼續(xù)回溯搜索子節(jié)點(diǎn)。

【整體思路】

　　01背包屬于找最優(yōu)解問題，用回溯法需要構(gòu)造解的子集樹。對于每一個物品i，對于該物品只有選與不選2個決策，總共有n個物品，可以順序依次考慮每個物品，這樣就形成了一棵解空間樹： 基本思想就是遍歷這棵樹，以枚舉所有情況，最后進(jìn)行判斷，如果重量不超過背包容量，且價值最大的話，該方案就是最后的答案。深度遍歷的意思。

package practice;
 
/**
 * 給定n種物品和一背包。物品i的重量是wi，其價值為pi，背包的容量為C。 問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?
 * 
 * @author fulisha
 *
 */
public class _05 {
 
	static int BestValue = 0; // 最優(yōu)值；當(dāng)前的最大價值，初始化為0
	static int[] BestX; // 最優(yōu)解；BestX[i]=1代表物品i放入背包，0代表不放入
	//
	static int CurWeight = 0; // 當(dāng)前放入背包的物品總重量
	static int CurValue = 0; // 當(dāng)前放入背包的物品總價值
	static int N = 3;// 物品數(shù)量
	static int C = 16;// 物品的總?cè)萘?
	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) {
		// 如果是子節(jié)點(diǎn) 當(dāng)前價值和最佳價值做判斷 保存最佳價值
		if (t > N - 1) {
			if (CurValue > BestValue) {
				BestValue = CurValue;
			}
			return BestValue;
		}
		// 如果不是子節(jié)點(diǎn) 對子節(jié)點(diǎn)進(jìn)行遍歷
		else {
			// 就兩種情況 取或不取 用0/1表示
			for (int i = 0; i <= 1; i++) {
				x[t] = i;
				if (i == 0) {
					// 如果是不取 就不需要進(jìn)行判斷 直接到下一個節(jié)點(diǎn)
					backtrack(t + 1);
				} else
				// 放入背包就進(jìn)行約束條件 判斷放入背包的東西是否合法
				{
					if (CurWeight + W[t] <= C) {
						CurWeight += W[t];
						CurValue += v[t];
						// 當(dāng)東西裝進(jìn)入背包后你可以進(jìn)行對下個商品的判斷了
						backtrack(t + 1);
						//能執(zhí)行以下兩個語句就說明你回溯到了上一個節(jié)點(diǎn) 
                       // 所以你就需要恢復(fù)現(xiàn)場 把你剛剛拿的東西退出來 
                       // 我們要沖上一個節(jié)點(diǎn)又要重新來遍歷 如果不減你就會多加一遍 
						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 的二維數(shù)組，模擬迷宮，用2這個數(shù)字表示迷宮的墻壁 ，0表示迷宮的路線 ，那么我們主要的思路就是 在迷宮的入口 判斷入口的上下左右 哪一個方向不是墻壁 我們則進(jìn)入進(jìn)去，同時我們用1 這個數(shù)字表示走過的路線 0表示不通的路線 這就是我們大致的思路，關(guān)鍵是用完后記得把節(jié)點(diǎn)環(huán)境恢復(fù)下。

public class TestMaze
{
	// 定義一個二維數(shù)組做迷宮
	private int[][] maze = null;
	//表示此迷宮一共有幾種走法
	private int count = 0;
	// 迷宮的開始位置和結(jié)束位置的坐標(biāo)
	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 代表生成括號的對數(shù)，請你寫出一個函數(shù)，使其能夠生成所有可能的并且有效的括號組合。括號只有{}[]()這三種。

例如，給出 n = 3，生成結(jié)果為：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

 解法：

	/**
	 * list：用來存儲符合要求的括號組合。
	 * 局部變量temp:表示當(dāng)前函數(shù)的括號組成樣式。
	 * 計(jì)數(shù)器x：判斷遞歸次數(shù)，限制其底界。
	 * 總的形成括號對數(shù)n。
	 * */
	public List<String> generateParenthesis(int n)
	{
		List<String> list = new ArrayList<>();
		add_list(list, "(", 1, n * 2);
		return list;
	}

	//書寫遞歸函數(shù)
	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)
		{
			//在這里寫判斷條件是否負(fù)荷有效的括號組合
			char[] k = temp.toCharArray();
			//計(jì)數(shù)器
			int timer = 0;
			for (int i = 0; i < k.length; i++)
			{
                //無論何時 ( 個數(shù) >= ）個數(shù)
				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 {
	//參數(shù)有n對的{}()[],
	public static List<String> generater(int n) {
		List<String> result=new ArrayList<String>();
		generaterOneByOne("",result,n,n);
		return result;
	}
	/**
	 * left:左邊的括號就n個
	 * right:右邊的括號有n個
	 * 思想：
	 *   必須先放左邊的括號，以遞歸的方式，然后直到左邊的括的數(shù)目小于0時，以及右邊的括號為0時，截止并放到結(jié)果中
	 *   右邊的括號要后放：也就是right>left，保證右括號大于左邊括號的數(shù)目
	 * @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);
		}		
	}
 
}

到此，相信大家對“回溯算法是什么”有了更深的了解，不妨來實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！