Backtrack 算法思路

1.引言

黃色的樹林里分出兩條路，可惜我不能同時去涉足,我選擇了人跡稀少的一條，從此決定了我一生的道路

2.什么是回溯算法？

Backtrack算法，中譯回溯算法，是一個非常實用的一個算法，如果用一個諺語來形容回溯算法，我愿意稱之為“不撞南墻不回頭”的一種算法。

為什么這么說呢？因為回溯算法實質(zhì)上就是一種不斷嘗試，通過不斷的“試錯”不斷更改信息的一種算法。

“不撞南墻”說明了當(dāng)回溯算法不遇到錯誤的時候，“不回頭”就是不返回上一步重新嘗試。

從引言的那首羅伯特.弗羅斯特的詩里，“可惜我不能同時去涉足”，可是對于回溯算法來說不是這樣的，回溯算法看到路走錯了就不會繼續(xù)走了，它會折返到最近的一個分岔口，重新選擇一條道路行走。

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-FIvQYVnT-1652531632747)(https://tse1-mm.cn.bing.net/th/id/R-C.91867e276501f596a4802b67aea756f6?rik=T2H1qdJZGAQe7g&riu=http%3a%2f%2fimg95.699pic.com%2fphoto%2f50123%2f6755.jpg_wh300.jpg!%2ffh%2f300%2fquality%2f90&ehk=6ZJzrS%2bT3A%2fCApII9W0nWQRrSgaCGaU1C3o6wI7aRLs%3d&risl=&pid=ImgRaw&r=0&sres=1&sresct=1)]

回溯算法可以用來解數(shù)獨，進(jìn)行排列組合，解決N皇后等問題

3.回溯算法的實現(xiàn)

讓我們來看一看79. 單詞搜索 這道題

這道題要求我們從board里面查找某一個單詞（例如：ABCDE)，如果查找到單詞，我們就返回True，否則返回False。

如上所示，黃色的路徑就代表我們成功找到了“ABCDE”這個連續(xù)的單詞。我們可以從上、下、左、右四個方向進(jìn)行單詞查找。

這里有一點需要注意，單詞并不需要第一行第一列的數(shù)字來開始，我們可以從任何點上開始單詞。

回溯算法的基本思路

1.確定Base case，即考慮一些越界情況，結(jié)果實現(xiàn)的情況。

2.在選擇列表中進(jìn)行選擇

3.迭代下一個情況

4.撤銷選擇

這個回溯算法可以如下定義：

def backtrack(x,y,index)

x,y就是我們傳進(jìn)去的board的行數(shù)和列數(shù)，index為單詞的索引

def dfs(x,y,index):#base caseif x<0 or x>=row or y<0 or y>=col: 、return Falseif board[x][y]!=word[index]:return Falseif index ==len(word)-1:return True#做選擇board[x][y] = '#' #進(jìn)行迭代for i in [[0,1],[1,0],[0,-1],[-1,0]]:next_x = x+i[0]next_y = y+i[1]if dfs(next_x,next_y,index+1):return True#撤銷選擇board[x][y] = word[index]return False#開始點，可以從任一行任一列開始for i in range(row):for j in range(col):if dfs(i,j,0):return Truereturn False

如上，按照思路，第一步：確立Base case，當(dāng)索引為index的單詞字符剛剛和board的x行y列的字符相同時，繼續(xù)走下去，如果不是，則return，程序返回上一步（即返回上一次for循環(huán)，進(jìn)行下一個循環(huán)），如果繼續(xù)走下去，就再次執(zhí)行剛剛的內(nèi)容，如此循環(huán)，直至我們可以找到一個序列和給出的單詞一致，即index的長度達(dá)到了單詞的長度。

讓我們來看下一道一個比較簡單的題目， 全排列

輸入：nums = [1,2,3]

輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

代碼如下：

class Solution:def permute(self, nums: List[int]) -> List[List[int]]:res = []track = []def backtrack():if len(track) == len(nums): #base caseres.append(track[:])returnfor i in range(0,len(nums)):if nums[i] in track:continuetrack.append(nums[i]) #選擇backtrack() #迭代track.pop()#撤銷選擇backtrack()return res

還是慣常的思路，確立一個Base case,然后進(jìn)行選擇，進(jìn)行迭代，撤銷選擇。

其實從回溯算法里面，我們也能發(fā)現(xiàn)一件事，那就是所謂“智能”的計算機(jī)，實際上是因為計算機(jī)擁有巨大的“計算能力"，它能不厭其煩的進(jìn)行大量的數(shù)據(jù)處理，并從這些數(shù)據(jù)中根據(jù)我們所確立的“basecase”進(jìn)行選擇。

如果你跟一個不知道計算機(jī)怎么運行的人演示這個全排列算法（如果你去演示一個N皇后，解數(shù)獨的例子可能更好），他們會糾結(jié)于為什么你跟電腦說：“給我一個數(shù)組[1,2,3]的全排列輸出?！彪娔X就會如實的做到，電腦他難道是因為知道全排列的含義而去思考嗎？實際上是你給他一個指令，讓他去遍歷這些數(shù)組組成的所有有用序列，然后返回而已。

不過，這樣也可以說明，電腦是可以擁有“學(xué)習(xí)能力”的，比如你給計算機(jī)一百萬個數(shù)據(jù)，讓他去處理這之間的關(guān)系（而不需要你告訴它關(guān)系是什么），然后你再丟給它一個不是數(shù)據(jù)里數(shù)字，他能返回給你一個“最接近結(jié)果”的一個值，當(dāng)然，這就是另一種事情了。

總結(jié)

以上是生活随笔為你收集整理的Backtrack 算法思路的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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