I. 回溯算法基礎(chǔ)
-
回溯與遞歸的區(qū)別和聯(lián)系
? 很多人不理解回溯與遞歸到底是什么關(guān)系谬返。其實很簡單，回溯算法是一種算法思想，是我們解決問題的策略铺董；而遞歸是一種算法結(jié)構(gòu)。遞歸就是函數(shù)調(diào)用本身禀晓，一般回溯法多用遞歸來實現(xiàn)精续。 -
回溯法的基本思想
? 在按某種搜索策略搜索的過程中，當(dāng)?shù)竭_(dá)某一狀態(tài)時粹懒，繼續(xù)向前搜索已經(jīng)確定不會得到正確答案的情況下重付，可以返回上一搜索狀態(tài)，沿著新的可能性繼續(xù)搜索凫乖。其求解過程的實質(zhì)是一個先序遍歷一棵“狀態(tài)樹”的過程确垫。 -
回溯法的特點
- 搜索策略:符合遞歸算法，問題解決可以化為子問題帽芽，算法類似删掀，規(guī)模減小;
- 控制策略:當(dāng)遇到失敗的搜索狀態(tài)，需要返回上一狀態(tài)导街，沿另外的路徑搜索;
- 數(shù)據(jù)結(jié)構(gòu):一般用數(shù)組保存搜索過程中的狀態(tài)披泪、路徑。
II. 回溯法的經(jīng)典例子
-
爬樓梯問題
? 對于一個與 n 級臺階組成的樓梯搬瑰，爬樓梯時一次可以上 1 級臺階或 2 級臺階款票。共有多少種不同的走法。
1. 問題分析
?由題可知泽论，在任何一級臺階我們往上爬的時候都有兩種選擇:爬 1 級臺階或者爬2 級臺階艾少。那就會產(chǎn)生回溯，當(dāng)我們爬 2 級臺階會超出樓梯時翼悴，我們再返回來爬 1 級臺階;其次缚够，n 級臺階可能是由第 n-1 級臺階爬上來的，也可能是從第 n-2 級臺 階爬上來的抄瓦。所以潮瓶，對于 n 級臺階的問題又可以分解成為兩個相似的字問題。符合遞歸的條件钙姊。
2. Java代碼實現(xiàn)
/**
* @Author: 落腳丶
* @Date: 2017/10/15
* @Time: 上午11:24
* @ClassName: ClimbStairs
* @Description: 爬樓梯方法的回溯解法
*/
public class ClimbStairs {
static int s = 1;
public static int[] steps = new int[10];
public static void main(String[] args){
System.out.println("請輸入臺階數(shù)：");
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
tryStep(n);
}
static void tryStep(int n){ // 爬n級樓梯
for (int i = 1; i <= 2; i++){
// 對于每次爬有兩次嘗試毯辅，一次爬1級或者一次爬2級
if (n < i)
break;
steps[s++] = i; // 一步走了i級臺階
n -= i; //縮小問題的規(guī)模
if (n == 0) {
for (int j = 1; j < s; j++){
System.out.print("第"+ j + "步走了" + steps[j]
+ "級臺階 ");
}
System.out.println();
} else {
tryStep(n);
}
n += i;
steps[s--] = 0;
}
}
}
/**
* 以4級臺階為例的輸出：
*
* 請輸入臺階數(shù)：
* 4
* 第1步走了1級臺階 第2步走了1級臺階 第3步走了1級臺階 第4步走了1級臺階
* 第1步走了1級臺階 第2步走了1級臺階 第3步走了2級臺階
* 第1步走了1級臺階 第2步走了2級臺階 第3步走了1級臺階
* 第1步走了2級臺階 第2步走了1級臺階 第3步走了1級臺階
* 第1步走了2級臺階 第2步走了2級臺階
*/
-
八皇后問題
? 在國際象棋棋盤8 × 8上放置八個皇后，使得任意兩個皇后之間不能在同一行煞额，同一列思恐，也不能位于同于對角線上沾谜。問共有多少種不同的方法，并且指出各種不同的放法胀莹。
1. 算法思路:
? 我們知道基跑，假如不考慮題中的限制，每行放置皇后都有 8 種放法描焰，我們可以用一個完全八叉樹來描述整個過程媳否。而實際問題中我們需要根據(jù)條件來對樹進(jìn)行枝。
? 我們可以定義一個數(shù)組 position[8]荆秦，其中 position[i] = j 代表第 i 行 j 列篱竭。于是，約束條件可以如下表示:
a. 不在同一列:position[i] != position[j];
b. 不在對角線上:|i ? j| != |position[i] ? position[j]|.? 從第一行確定第 1 個皇后的位置步绸，然后在第二行搜索第 2 個皇后的位置掺逼，... ， 每前進(jìn)一步檢查是否滿足約束條件瓤介，不滿足約束條件的時候回溯到上一個皇后的位置吕喘，嘗試該行其他列是否滿足條件，直到找到問題解刑桑。
2. 算法的Java實現(xiàn):
/**
* @Author: 落腳丶
* @Date: 2017/10/18
* @Time: 下午4:55
* @ClassName: EightQueen
* @Description: 8皇后問題回溯解法
*/
public class EightQueen {
private static int num = 1; // 方案的總數(shù)
private static final int MAX_QUEEN = 8;
private static int[] position = new int[MAX_QUEEN];
public static void main(String[] args) {
trail(0);
}
/**
* @Date: 2017/10/18
* @Time: 下午5:00
* @Method: isValid
* @Return: 位置是否滿足條件
* @Description: 判斷位置是否滿足條件
*/
static boolean isValid(int row) {
for (int i = 0; i < row; i++) {
/**
* 如果前面放好的位置不在同一行氯质、同一列、同一對角線
* 則返回true
* 否則返回false
*/
if (position[i] == position[row] ||
Math.abs(position[i] - position[row]) ==
Math.abs(i - row) ) {
return false;
}
}
return true;
}
/**
* @Date: 2017/10/18
* @Time: 下午5:29
* @Method: print
* @Description: 打印皇后擺放位置的結(jié)果
*/
static void print() {
System.out.println("第" + num++ +"種擺法：");
for (int i = 0; i < MAX_QUEEN; i++) {
for (int j = 0; j < MAX_QUEEN; j++) {
if(position[i] == j)
System.out.print("+ ");
else
System.out.print("0 ");
}
System.out.println();
}
System.out.println();
}
static void trail(int row) {
// 如果擺完MAX_QUEEN行漾月，則輸出結(jié)果
if (row == MAX_QUEEN) {
print();
return;
}
for (int column = 0; column < MAX_QUEEN; column++) {
position[row] = column; // 放在第row行第column列
// 如果滿足條件病梢，則進(jìn)行下一行
if (isValid(row))
trail(row + 1);
}
}
}
部分輸出結(jié)果（合成圖片）：
