一典尾、理論
回溯
- 本質(zhì)：和深度優(yōu)先遍歷思想是一致的身冀，都是遞歸的應用睹耐；搜索空間可以理解成一棵樹辐赞，需要自頂向下不斷枚舉出所有的情況。
- 寫法的關鍵：循環(huán)和遞歸硝训。
- for循環(huán)的作用在于另尋它路响委，可以逐個選擇當前節(jié)點下的所有可能往下走下去的分支路徑。
- 遞歸可以實現(xiàn)一條路走到黑和回退一步窖梁，把遞歸放在for循環(huán)內(nèi)部赘风，那么for每一次的循環(huán)，都在給出一個路徑后進入遞歸窄绒，繼續(xù)往下走贝次。
- 代碼模版
void backtracking(參數(shù)) {
if (終止條件) {
存放結(jié)果;
return;
}
for (選擇：本層集合中元素（樹中節(jié)點孩子的數(shù)量就是集合的大小）) {
處理節(jié)點;
backtracking(路徑彰导，選擇列表); // 遞歸
回溯蛔翅，撤銷處理結(jié)果
}
}
剪枝
- 定義：剪枝算法是排除搜索空間中不可能包含最優(yōu)解的部分，從而減少搜索時間以及空間復雜度位谋。
- 實現(xiàn)方式：
A. 可行性剪枝
利用問題的特性進行剪枝山析；在搜索過程中，根據(jù)問題的特點掏父，排除不符合條件的搜索分支笋轨。
B. 排除等效冗余
當幾個枝椏具有完全相同的效果的時候，只選擇其中一個走就可以了赊淑。
C. 最優(yōu)性剪枝
所謂最優(yōu)性剪枝爵政，是在我們用搜索方法解決最優(yōu)化問題的時候的一種常用剪枝方法。當搜到一半的時候陶缺，發(fā)現(xiàn)比已經(jīng)搜索到的最優(yōu)解差钾挟，則該方案肯定是不行的，即刻停止搜索饱岸，進行回溯掺出。
D. 順序剪枝
普遍來講，搜索的順序是不固定的苫费，對一個問題來講汤锨，算法可以進入搜索樹的任意的一個子節(jié)點。但假如我們要搜索一個最小值百框，而非要從最大值存在的那個節(jié)點開搜闲礼，就可能存在搜索到最后才出解。而我們從最小的節(jié)點開搜很可能馬上就出解铐维。這就是順序剪枝的一個應用柬泽。一般來講，有單調(diào)性存在的搜索問題可以和貪心思想結(jié)合方椎，進行順序剪枝聂抢。
E. 記憶化搜索
記憶化搜索其實是搜索的另外一個分支。在這里簡單介紹一下記憶化的原理：就是記錄搜索的每一個狀態(tài)棠众，當重復搜索到相同的狀態(tài)的時候直接返回琳疏。
二、算法實踐
問題鏈接
37. 解數(shù)獨
問題描述
編寫一個程序闸拿，通過填充空格來解決數(shù)獨問題空盼。
數(shù)獨的解法需 遵循如下規(guī)則：
數(shù)字 1-9 在每一行只能出現(xiàn)一次。
數(shù)字 1-9 在每一列只能出現(xiàn)一次新荤。
數(shù)字 1-9 在每一個以粗實線分隔的 3x3 宮內(nèi)只能出現(xiàn)一次揽趾。（請參考示例圖）
數(shù)獨部分空格內(nèi)已填入了數(shù)字，空白格用 '.' 表示苛骨。
示例
輸入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
輸出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解題思路
- 遍歷整個數(shù)獨篱瞎，獲取數(shù)字在行苟呐、列、宮格中的出現(xiàn)情況俐筋，以及空閑位置牵素。
- 用遞歸的方法，給空閑位置挨個放數(shù)澄者，放數(shù)的同時校驗行笆呆、列、宮格內(nèi)的重復性粱挡，如果發(fā)生重復赠幕，就剪掉并回溯。
代碼示例（JAVA）
class Solution {
// 表示行询筏、列榕堰、宮格中數(shù)字的出現(xiàn)情況
private boolean[][] row = new boolean[9][9];
private boolean[][] column = new boolean[9][9];
private boolean[][][] grid = new boolean[3][3][9];
// 找出需要放入數(shù)字的位置
private List<int[]> empty = new ArrayList<int[]>();
public void solveSudoku(char[][] board) {
// 遍歷整個數(shù)獨，獲取數(shù)字在行屈留、列局冰、宮格中的出現(xiàn)情況，以及空閑位置
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
if (board[i][j] == '.') {
empty.add(new int[]{i, j});
} else {
int index = board[i][j] - '0' - 1;
row[i][index] = column[j][index] = grid[i / 3][j / 3][index] = true;
}
}
}
dfs(board, 0);
}
public boolean dfs(char[][] board, int pos) {
// 遞歸終止條件
if (pos == empty.size()) {
return true;
}
int[] target = empty.get(pos);
int i = target[0], j = target[1];
for (int k = 0; k < 9; ++k) {
// 經(jīng)過校驗灌危，可以放入k康二；校驗失敗就不要了（剪枝）
if (!row[i][k] && !column[j][k] && !grid[i /3][j / 3][k]) {
// 放入k，并更新數(shù)字出現(xiàn)情況勇蝙，且繼續(xù)遞歸
board[i][j] = (char) (k + '0' + 1);
row[i][k] = column[j][k] = grid[i / 3][j / 3][k] = true;
// 遞歸到下一層
if (dfs(board, pos + 1)) {
return true;
}
// 失敗沫勿，回溯
row[i][k] = column[j][k] = grid[i / 3][j / 3][k] = false;
}
}
// 找不到可以放入的k，return false
return false;
}
}
