回溯演算法講解--適用於leetcode絕大多數回溯題目
什麼是回溯演算法?
回溯法是一種系統搜尋 問題解空間 的方法。為了實現回溯,需要給問題定義一個解空間 。
說到底它是一種搜尋演算法 。只是這裡的搜尋是在一個叫做解空間 的地方搜尋。
而往往所謂的dfs,bfs都是在圖或者樹這種資料結構上的搜尋。
根據定義來看,要實現回溯,需要兩點1搜尋 ,2解空間
先看什麼是解空間 。
就是形如陣列的一個向量[a1,a2,....,an]。這個向量的每個元素都是問題的部分解,只有當這個陣列的每一個元素都填滿 (得到全部解)的時候,才表明這個問題得到了解答。
再看搜尋 。
最簡單的就是for迴圈,上面的向量有n個維度,因此就是n個for迴圈。
形如:
for(求a1位置上的解) for(求a2位置上的解) for(求a3位置上的解) ...... ...... for(求an位置上的解)
但是如果n是100?n是100000?那麼如何回溯?
當然也可以寫n個for迴圈,但是這樣的程式會慘不忍睹。。。而且似乎10000個(不過往往回溯的時間複雜度太大,一般n不會這麼大)for迴圈也很難寫出來。。。
因此我們需要一種全新的書寫回溯的方法。形如:
void backtrack(int i,int n,other parameters) { if( i == n) { //get one answer record answer; return; } //下面的意思是求解空間第i個位置上的下一個解 for(next ans in position i of solution space) { backtrack(i+1,n,other parameters); } }
就是這麼簡單!!!
上面的模板適用於所有"解空間確定"的回溯法的問題!!!
上面的i代表解空間的第i個位置,往往從0開始,而n則代表解空間的大小。每一次的backtrack(i,n,other)呼叫,代表求解空間 第i個位置上的解。而當i=n時,代表解空間上的所有位置的解都已經求出。
有了上述模板 ,我們就解決了搜尋 的問題。
因此幾乎 所有回溯的問題的難度都在於如何定義解空間 。
下面通過題目,帶入模板,然後再看我的解答,來感知一下如何定義解空間。
全排列https://segmentfault.com/a/11...
即對沒有重複數字的陣列a=[a1,a2,a3,...an]求全排列。
解空間定義為s=[s1,s2,s3,....sn]與數字長度相同。s的每一個元素s【i】(i >= 0&&i < n),都為陣列a中的任意元素a【j】(j >= 0&&j < n),不過要保證任意的s【i】不相等。
這裡唯一複雜的地方是需要用一個boolean【】陣列來表明哪些數已經用過,這樣才能保證任意的s【i】不相等。
因此我們看到,回溯本身是很簡單的,單純的模板套用,難的在於需要根據回溯條件來定義各種別的變數,以及最後結果的記錄。
探測路徑https://leetcode-cn.com/probl... (這個下面給出ac 程式碼)
這個題很難,但是掌握瞭如何定義解空間之後再做這個題就會感覺是小兒科了。
這裡的解空間s = [s1,s2,s3,....sn]中的每一個元素s【i】代表格子的座標(x,y),因此從邏輯上 來看,s應該是一個類型別的陣列。不過,這個題求的是數目,而不是最後的確切路徑,因此解空間在這裡並沒有記錄。
java ac程式碼:
class Solution { int ans; public int uniquePathsIII(int[][] grid) { if(grid.length == 0)return 0; int num = 0; int x = 0,y = 0; for(int i = 0;i < grid.length;i++) for(int j = 0;j < grid[0].length;j++){ if(grid[i][j] == 1||grid[i][j] == 0)num++; if(grid[i][j] == 1){x = i;y = j;} } backtrack(0,num,x,y,grid,new boolean[grid.length][grid[0].length]); return ans; } void backtrack(int i,int n,int x,int y,int[][]grid,boolean[][]flag) { if(!(x >= 0 && x < grid.length && y >= 0 && y < grid[0].length)||flag[x][y]||grid[x][y] == -1) return; if(i == n && grid[x][y] == 2) { ans++; return; } flag[x][y] = true; backtrack(i+1,n,x+1,y,grid,flag); backtrack(i+1,n,x-1,y,grid,flag); backtrack(i+1,n,x,y+1,grid,flag); backtrack(i+1,n,x,y-1,grid,flag); flag[x][y] = false; } }
上面這個題的解空間應該有N+1個才對,但是為了方便書寫,我只求出前n個位置的解,然後保證最後一個位置是終點即可。