從電影《蝴蝶效應(yīng)》中學(xué)習(xí)回溯算法的核心思想
點(diǎn)擊上方“視學(xué)算法”，選擇加"星標(biāo)"或“置頂”
重磅干貨，第一時(shí)間送達(dá)
關(guān)注我們丨文末贈(zèng)書(shū)
深度優(yōu)先搜索算法利用的是回溯算法思想。這個(gè)算法思想非常簡(jiǎn)單，但應(yīng)用卻 非常廣泛。它除用來(lái)指導(dǎo)像深度優(yōu)先搜索這種經(jīng)典的算法設(shè)計(jì)之外，還可以用在很多實(shí)際的軟件開(kāi)發(fā)場(chǎng)景中，如正則表達(dá)式匹配、編譯原理中的語(yǔ)法分析等。除此之外，很多經(jīng)典的數(shù)學(xué)問(wèn)題也可以用回溯算法解決，如數(shù)獨(dú)、八皇后、0-1背包、圖的著色、旅行商、求全排列等。在本文，我們就來(lái)學(xué)習(xí)一下回溯算法思想。
— 01 —
在我們的一生中，會(huì)遇到很多重要的“岔路口”。在人生的岔路口，每個(gè)選擇都會(huì)影響我們今后的人生。有的人在每個(gè)“岔路口”都能做出正確的選擇，生活、事業(yè)可能達(dá)到了一個(gè)很高的高度；而有的人一路選錯(cuò)，最后可能碌碌無(wú)為。如果人生可以量化，那么如何才能在人生的岔路口做出正確的選擇，讓自己的人生“最優(yōu)”呢？我們可以借助貪心算法，在每次面對(duì)人生岔路口的時(shí)候，都做出當(dāng)下看起來(lái)最優(yōu)的選擇，期望這一組局部最優(yōu)選擇可以使得我們的人生達(dá)到全局“最優(yōu)”。
但是，貪心算法并不一定能得到最優(yōu)解。那么，有沒(méi)有其他辦法能得到最優(yōu)解呢？2004年，著名的電影《蝴蝶效應(yīng)》上映，該部電影講的就是主人公為了達(dá)到自己的目標(biāo)，一直通過(guò)回溯的方法，回到童年，在關(guān)鍵的人生岔路口，重新做選擇。當(dāng)然，這只是科幻電影，我們的人生是無(wú)法倒退的，但這其中蘊(yùn)含的思想其實(shí)就是回溯算法。回溯算法一般用到與“搜索”有關(guān)的問(wèn)題上。不過(guò)這里說(shuō)的搜索，并不是狹義地指圖的搜索，而是在一組可能的解中搜索滿(mǎn)足期望的解。回溯的處理思想有點(diǎn)類(lèi)似枚舉（或窮舉）。
枚舉所有的解，找出其中滿(mǎn)足期望的解。為了有規(guī)律地枚舉所有可能的解，避免遺漏和重復(fù)，我們把問(wèn)題求解的過(guò)程分為多個(gè)階段。每個(gè)階段都會(huì)面對(duì)一個(gè)“岔路口”，我們先隨意選一條路走，當(dāng)發(fā)現(xiàn)這條路走不通的時(shí)候（不符合期望的解），就回退到上一個(gè)“岔路口”，另選一種走法繼續(xù)走。
八皇后問(wèn)題的遞歸代碼實(shí)現(xiàn)如下所示:
int[] result = new int[8];//下標(biāo)表示行，值表示皇后存儲(chǔ)在哪一列public void cal8queens(int row) { //調(diào)用方式：cal8queens(0);if (row == 8) { //8個(gè)棋子都放置好了，輸出結(jié)果printQueens(result);return; //8行棋子都放好了，已經(jīng)沒(méi)法再往下遞歸了，因此返回}for (int column = 0; column < 8; ++column) { //每一行都有8種放法if (isOk(row, column)) { //有些放法不滿(mǎn)足要求result[row] = column; //第row行的棋子放到了column列cal8queens(row+1); //考察下一行}}}//判斷row行、column列放置是否合適private boolean isOk(int row, int column) {int leftup = column - 1, rightup = column + 1;for (int i = row-1; i >= 0; --i) { //逐行往上考察每一行if (result[i] == column) return false; //第i行、第column列有棋子if (leftup >= 0) { //考察左上對(duì)角線：第i行、第leftup列有棋子嗎？if (result[i] == leftup) return false;}if (rightup < 8) { //考察右上對(duì)角線：第i行、第rightup列有棋子嗎？if (result[i] == rightup) return false;}--leftup; ++rightup;}return true;}private void printQueens(int[] result) { //輸出一個(gè)二維矩陣for (int row = 0; row < 8; ++row) {for (int column = 0; column < 8; ++column) {if (result[row] == column) System.out.print("Q ");else System.out.print("* ");}System.out.println();}System.out.println();}
0-1 背包問(wèn)題
public int maxW = Integer.MIN_VALUE; //存儲(chǔ)背包中物品總重量的最大值//cw表示當(dāng)前已經(jīng)裝進(jìn)去的物品的重量和；i表示考察到哪個(gè)物品了//w表示背包可以承載的最大重量；items表示每個(gè)物品的重量；n表示物品個(gè)數(shù)//假設(shè)背包可承受重量為100，物品個(gè)數(shù)為10，物品重量存儲(chǔ)在數(shù)組a中，//那么可以這樣調(diào)用函數(shù)：f(0, 0, a, 10, 100)public void f(int i, int cw, int[] items, int n, int w) {// cw==w表示裝滿(mǎn)了；i==n表示已經(jīng)考察完所有的物品if (cw == w || i == n) {if (cw > maxW) maxW = cw;return;}f(i+1, cw, items, n, w);if (cw + items[i] <= w) { //沒(méi)有超過(guò)背包可以承載的最大重量f(i+1,cw + items[i], items, n, w);}}
正則表達(dá)式匹配問(wèn)題
public class Pattern {private boolean matched = false;private char[] pattern; //正則表達(dá)式private int plen; //正則表達(dá)式的長(zhǎng)度public Pattern(char[] pattern, int plen) {this.pattern = pattern;this.plen = plen;}public boolean match(char[] text, int tlen) { //文本串及其長(zhǎng)度matched = falsermatch(0, 0, text, tlen);return matched;}private void rmatch(int ti, int pj, char[] text, int tlen) {if (matched) return; //如果已經(jīng)匹配，就不要繼續(xù)遞歸了if (pj == plen) { //正則表達(dá)式到結(jié)尾了if (ti == tlen) matched = true; //文本串也到結(jié)尾了return;}if (pattern[pj] == '*') { //*匹配任意個(gè)字符for (int k = 0; k <= tlen-ti; ++k) {rmatch(ti+k, pj+1, text, tlen);}} else if (pattern[pj] == '?') { //?匹配0個(gè)或者1個(gè)字符rmatch(ti, pj+1, text, tlen);rmatch(ti+1, pj+1, text, tlen);} else if (ti < tlen && pattern[pj] == text[ti]) { //純字符匹配才行rmatch(ti+1, pj+1, text, tlen);}}}
內(nèi)容小結(jié)
點(diǎn)擊上圖，即可購(gòu)買(mǎi)《數(shù)據(jù)結(jié)構(gòu)與算法之美》！
本書(shū)結(jié)合實(shí)際應(yīng)用場(chǎng)景講解數(shù)據(jù)結(jié)構(gòu)和算法，涵蓋常用、?？嫉臄?shù)據(jù)結(jié)構(gòu)和算法的原理講解、代碼實(shí)現(xiàn)和應(yīng)用場(chǎng)景等。
本書(shū)分為11章。第1章介紹復(fù)雜度分析方法。第2章介紹數(shù)組、鏈表、棧和隊(duì)列這些基礎(chǔ)的線性表數(shù)據(jù)結(jié)構(gòu)。第3章介紹遞歸編程技巧、8種經(jīng)典排序、二分查找及二分查找的變體問(wèn)題。第4章介紹哈希表、位圖、哈希算法和布隆過(guò)濾器。第5章介紹樹(shù)相關(guān)的數(shù)據(jù)結(jié)構(gòu)，包括二叉樹(shù)、二叉查找樹(shù)、平衡二叉查找樹(shù)、遞歸樹(shù)和B+樹(shù)。第6章介紹堆，以及堆的各種應(yīng)用，包括堆排序、優(yōu)先級(jí)隊(duì)列、求TopK、求中位數(shù)和求百分位數(shù)。第7章介紹跳表、并查集、線段樹(shù)和樹(shù)狀數(shù)組這些比較高級(jí)的數(shù)據(jù)結(jié)構(gòu)。第8章介紹字符串匹配算法，包括BF算法、RK算法、BM算法、KMP算法、Trie樹(shù)和AC自動(dòng)機(jī)。第9章介紹圖及相關(guān)算法，包括深度優(yōu)先搜索、廣度優(yōu)先搜索、拓?fù)渑判?、Dijkstra算法、Floyd算法、A*算法、最小生成樹(shù)算法、最大流算法和最大二分匹配等。第10章介紹4種算法思想，包括貪心、分治、回溯和動(dòng)態(tài)規(guī)劃。第11章介紹4個(gè)經(jīng)典項(xiàng)目中的數(shù)據(jù)結(jié)構(gòu)和算法的應(yīng)用，包括Redis、搜索引擎、鑒權(quán)限流和短網(wǎng)址服務(wù)。
另外，附錄A為書(shū)中的思考題的解答。盡管本書(shū)的大部分代碼采用Java語(yǔ)言編寫(xiě)，但本書(shū)講解的知識(shí)與具體編程語(yǔ)言無(wú)關(guān)，因此，本書(shū)不但適合各種類(lèi)型的研發(fā)工程師，而且可以作為高校計(jì)算機(jī)相關(guān)專(zhuān)業(yè)師生的學(xué)習(xí)用書(shū)和培訓(xùn)學(xué)校的教材。
歡迎加入本書(shū)讀書(shū)會(huì)社群，打卡學(xué)習(xí)
點(diǎn)個(gè)在看 paper不斷！