貪心算法
回溯算法
分治算法
動(dòng)態(tài)規(guī)劃

回溯算法思想應(yīng)用廣泛，除了用來指導(dǎo)深度優(yōu)先搜索這種經(jīng)典算法設(shè)計(jì)之外，還可以用在如正則表達(dá)式匹配，編譯原理中的語法分析等。

除此之外，很多經(jīng)典的數(shù)學(xué)問題都可以用回溯算法解決，比如數(shù)獨(dú)，八皇后，0-1背包，圖的著色，旅行商問題，全排列等等。

一：如何理解“回溯算法”

回溯的處理思想，有些類似枚舉搜索。枚舉所有的解，找到滿足期望的解。為了有規(guī)律的枚舉所有可能的解，避免遺漏和重復(fù)，所以把問題求解的過程分為多個(gè)階段。每個(gè)階段都有多個(gè)選擇，先隨意選擇一個(gè)，當(dāng)發(fā)現(xiàn)走不通時(shí)，就退回到上一個(gè)岔路口，另選一種走法繼續(xù)走。
常用在“搜索”問題：在一組可能的解中，搜索滿足期望的解

二：例子

八皇后問題

有一個(gè)8X8的棋盤，希望往里放8個(gè)棋子，每個(gè)棋子所在的行，列，對角線都不能有另一個(gè)棋子。

第一幅圖滿足要求，第二幅度圖不滿足，八皇后問題就是期望找到所有滿足這種要求的的放棋子的方式。
我們把這個(gè)問題劃分成8個(gè)階段，依次將8個(gè)棋子放到第一行，第二行，第三行……第八行。

int[] result = new int[8];//全局或成員變量,下標(biāo)表示行,值表示queen存儲(chǔ)在哪一列 public void cal8queens(int row) { // 調(diào)用方式：cal8queens(0);if (row == 8) { // 8個(gè)棋子都放置好了，打印結(jié)果printQueens(result);return; // 8行棋子都放好了，已經(jīng)沒法再往下遞歸了，所以就return}for (int column = 0; column < 8; ++column) { // 每一行都有8中放法if (isOk(row, column)) { // 有些放法不滿足要求result[row] = column; // 第row行的棋子放到了column列cal8queens(row+1); // 考察下一行}} }private boolean isOk(int row, int column) {//判斷row行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) { // 考察左上對角線：第i行l(wèi)eftup列有棋子嗎？if (result[i] == leftup) return false;}if (rightup < 8) { // 考察右上對角線：第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背包

0-1背包是非常經(jīng)典的算法問題，很多場景都可以抽象炒年糕這個(gè)問題模型。這個(gè)問題的經(jīng)典解法是動(dòng)態(tài)規(guī)劃，不過還有一種簡單但沒有那么高效的解法，就是回溯算法。
0-1背包問題有很多變體，例如：有一個(gè)背包，背包總的承載重量是Wkg?，F(xiàn)在有n個(gè)物品的重量不等，并且不可分割。我們現(xiàn)在期望選擇幾件物品，裝載到背包中，在不超過所能裝載重量的前提下，如何讓背包中物品的總重量最大？
這個(gè)背包問題，在貪心算法中有提到，但在貪心算法中講的物品是可以分割的，可以將物品的一部分裝進(jìn)背包。此處的背包問題，物品是不可分割的，要么裝要么不裝，所以叫0-1背包問題。
對于每個(gè)物品來說，都有兩種選擇，裝進(jìn)背包或在著不裝進(jìn)背包。對于n個(gè)物品來說，中的裝法就有2^n種，去掉總重量超過過W kg的，從剩下的裝法中選擇中重量最接近W kg的。

可以用回溯的方法，不重復(fù)的找到2^n種裝法。把物品依次排列，整個(gè)問題就分解為了n個(gè)階段，每個(gè)階段對應(yīng)的一個(gè)物品怎么選擇。先對第一個(gè)物品進(jìn)行處理，選擇裝進(jìn)去或是不裝進(jì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) {if (cw == w || i == n) { // cw==w表示裝滿了;i==n表示已經(jīng)考察完所有的物品if (cw > maxW) maxW = cw;return;}f(i+1, cw, items, n, w);//不選擇當(dāng)前物品，直接考慮下一個(gè)（第 i+1 個(gè)），故 cw 不更新if (cw + items[i] <= w) {// 已經(jīng)超過可以背包承受的重量的時(shí)候，就不要再裝了f(i+1,cw + items[i], items, n, w);//表示選擇了當(dāng)前物品，故考慮下一個(gè)時(shí)，cw 通過入?yún)⒏聻?cw + items[i]} }

2 正則表達(dá)式

正則表達(dá)式里最重要的一種算法思想就是回溯。
正則表達(dá)式中，最重要的就是通配符，通配符結(jié)合在一起，可以表達(dá)非常豐富的語義。假設(shè)：正則表達(dá)式中只包含 “”和“？”這兩種通配符，并且對這兩種通配符的語義稍微做些改變。其中，“”匹配任意多個(gè)（大于等于0個(gè)）任意字符，“？”匹配零個(gè)或者一個(gè)任意字符?；谝陨媳尘凹僭O(shè)，看下如何用回溯算法，判斷一個(gè)給定的文本，能否跟給定的正則表達(dá)式匹配？
依次考察正則表達(dá)式中的每個(gè)字符，當(dāng)是非通配符時(shí)，就直接跟文本的字符進(jìn)行匹配，如果相同，則繼續(xù)往下處理；如果不同，則回溯。
如果遇到特殊字符的時(shí)候，就有多種處理方式，如“*”有多種匹配方案，可以匹配任意個(gè)文本串中的字符，我們就先隨意的選擇一種匹配方案，然后繼續(xù)考察剩下的字符。如果中途發(fā)現(xiàn)無法繼續(xù)匹配下去，就回到這個(gè)岔路口，重新選擇一種匹配方案，然后繼續(xù)匹配剩下的字符。

public class Pattern {private boolean matched = false;private char[] pattern; // 正則表達(dá)式private int plen; // 正則表達(dá)式長度public Pattern(char[] pattern, int plen) {this.pattern = pattern;this.plen = plen;}public boolean match(char[] text, int tlen) { // 文本串及長度matched = false;rmatch(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);}} }

回溯算法本質(zhì)上就是枚舉，優(yōu)點(diǎn)在于其類似于摸著石頭過河的查找策略，且可以通過剪枝少走冤枉路。它可能適合應(yīng)用于缺乏規(guī)律，或我們還不了解其規(guī)律的搜索場景中。

筆記整理來源： 王爭 數(shù)據(jù)結(jié)構(gòu)與算法之美

總結(jié)

以上是生活随笔為你收集整理的【数据结构与算法】【算法思想】回溯算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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