積累算法經(jīng)驗(yàn)，積累解題方法——回溯算法，你必須要掌握的解題方法！

什么是回溯算法呢？

回溯算法實(shí)際上一個類似枚舉的搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解，當(dāng)發(fā)現(xiàn)已不滿足求解條件時，就“回溯”返回，嘗試別的路徑?；厮莘ㄊ且环N選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。但當(dāng)探索到某一步時，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿足回溯條件的某個狀態(tài)的點(diǎn)稱為“回溯點(diǎn)”。許多復(fù)雜的，規(guī)模較大的問題都可以使用回溯法，有“通用解題方法”的美稱。

最簡單的理解就是我們走迷宮的時候，走到一個節(jié)點(diǎn)，然后有很多路，選一條路不通則退回該節(jié)點(diǎn)走其他路；都走不通再往上一個節(jié)點(diǎn)倒退，直到找出迷宮出口。

---

只是簡單的概念無法真正理解這種算法的應(yīng)用場景，這里用一道力扣題來進(jìn)行講解：

leetcode 79. 單詞搜索

難度：中等

題目：給定一個二維網(wǎng)格和一個單詞，找出該單詞是否存在于網(wǎng)格中。

單詞必須按照字母順序，通過相鄰的單元格內(nèi)的字母構(gòu)成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內(nèi)的字母不允許被重復(fù)使用。

示例:
board =
[
[‘A’,‘B’,‘C’,‘E’],
[‘S’,‘F’,‘C’,‘S’],
[‘A’,‘D’,‘E’,‘E’]
]

給定 word = “ABCCED”, 返回 true
給定 word = “SEE”, 返回 true
給定 word = “ABCB”, 返回 false

提示：
board 和 word 中只包含大寫和小寫英文字母。
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3

來源：力扣（LeetCode）

• 鏈接：https://leetcode-cn.com/problems/word-search

這道題使用回溯算法就是非常好的解法，在性能上也是非常不錯的。

這里我們可以將首字母對應(yīng)的每一個坐標(biāo)都當(dāng)做我們的迷宮入口，之后上下左右進(jìn)行尋找，找到則繼續(xù)，找不到就往上一級回溯，具體解法如下👇

public class _79_單詞搜索 {public boolean exist(char[][] board, String word) {if(word.length() == 0){return false;}char start = word.charAt(0);for(int i = 0; i < board.length; i++){for(int j = 0; j < board[0].length; j++){if(start != board[i][j]){continue;}else{if(find(board, word, 0, i, j, 's')){return true;}else{continue;}}}}return false;}/**** @param board* @param word* @param index   word下標(biāo)* @param x       當(dāng)前的 board[x][y]* @param y       當(dāng)前的 board[x][y]* @param pre      規(guī)定了s為開頭  u為向上 d為向下 l為向左 r為向右*                 把已經(jīng)經(jīng)過的路徑中的字母換成0，避免重復(fù)，這一趟走完再復(fù)原，以免影響其他方向的進(jìn)行。* @return*/private boolean find(char[][] board, String word, int index, int x, int y, char pre){//System.out.println("index:" + index + ", " + "x:" + x + ",y:" + y);if(index == word.length() - 1 && word.charAt(index) == board[x][y]){return true;}if(index >= word.length() || word.charAt(index) != board[x][y]){return false;}boolean found = false;//向上尋找if(!found && pre != 'd' && x > 0){char tmp = board[x][y];board[x][y] = '0';found = find(board, word, index + 1, x - 1, y, 'u');board[x][y] = tmp;}//向下尋找if(!found && pre != 'u' && x < board.length - 1){char tmp = board[x][y];board[x][y] = '0';found = find(board, word, index + 1, x + 1, y, 'd');board[x][y] = tmp;}//向左尋找if(!found && pre != 'r' && y > 0){char tmp = board[x][y];board[x][y] = '0';found = find(board, word, index + 1, x, y - 1, 'l');board[x][y] = tmp;}//向右尋找if(!found && pre != 'l' && y < board[0].length - 1){char tmp = board[x][y];board[x][y] = '0';found = find(board, word, index + 1, x, y + 1, 'r');board[x][y] = tmp;}return found;}
}

以上！ 回溯算法你懂了嗎？

總結(jié)

以上是生活随笔為你收集整理的通用解题法——回溯算法（理解+练习）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。