文章目錄

• • 1 回溯算法介紹
  • 2 回溯算法應(yīng)用實例

1 回溯算法介紹

回溯的基本原理：
在問題的解空間中，按深度優(yōu)先遍歷策略，從根節(jié)點出發(fā)搜索解空間樹。算法搜索至解空間的任意一個節(jié)點時，先判斷該節(jié)點是否包含問題的解。如果確定不包含，跳過對以該節(jié)點為根的子樹的搜索，逐層向其祖先節(jié)點回溯，否則進入該子樹，繼續(xù)深度優(yōu)先搜索。

回溯法解問題的所有解時，必須回溯到根節(jié)點，且根節(jié)點的所有子樹都被搜索后才結(jié)束。回
溯法解問題的一個解時，只要搜索到問題的一個解就可結(jié)束。

回溯的基本步驟：

定義問題的解空間。

確定易于搜索的解空間結(jié)構(gòu)。

以深度優(yōu)先搜索的策略搜索解空間，并在搜索過程中盡可能避免無效搜索。

---

2 回溯算法應(yīng)用實例

題目如下：
請設(shè)計一個函數(shù)，用來判斷在一個矩陣中是否存在一條包含某字符串所有字符的路徑。路徑可以
從矩陣中任意一格開始，每一步可以在矩陣中向左、右、上、下移動一格。如果一條路徑經(jīng)過了
矩陣的某一格，那么該路徑不能再次進入該格子。

例如在下面的 3×4 的矩陣中包含一條字符串
“bfce”的路徑（路徑中的字母用下劃線標出）。但矩陣中不包含字符串“abfb”的路徑，因為
字符串的第一個字符 b 占據(jù)了矩陣中的第一行第二個格子之后，路徑不能再次進入這個格子。
A B T G
C F C S
J D E H

解題思路：
首先，在矩陣中任選一個格子作為路徑的起點。如果路徑上的第 i 個字符不是待搜索的目標字符 ch，那么這個格子不可能處在路徑上的第 i 個位置。如果路徑上的第 i 個字符正好是 ch，那么
往相鄰的格子尋找路徑上的第 i+1 個字符。除在矩陣邊界上的格子之外，其他格子都有 4 個相鄰
的格子。重復這個過程直到路徑上的所有字符都在矩陣中找到相應(yīng)的位置。

由于路徑不能重復進入矩陣的格子，還需要定義和字符矩陣大小一樣的布爾值矩陣，用來標識
路徑是否已經(jīng)進入每個格子。 當矩陣中坐標為（row, col）的格子和路徑字符串中相應(yīng)的字符一樣時，從 4 個相鄰的格子(row,col-1),(row-1,col),(row,col+1)以及(row+1,col)中去定位路徑字符串中下一個字符, 如果 4 個相鄰的格子都沒有匹配字符串中下一個的字符，表明當前路徑字符串中字符在矩陣中的定位不正確，我們需要回到前一個，然后重新定位。

代碼實現(xiàn)如下：

#include <stdio.h> #include <string>using namespace std;bool hasPathCore(const char* matrix, int rows, int cols, int row, int col,const char* str, int& pathLength, bool* visited); /***************************************** 功能： 查找矩陣中是否含有 str 指定的字串 參數(shù)說明： matrix 輸入矩陣 rows 矩陣行數(shù) cols 矩陣列數(shù) str 要搜索的字符串 返回值： 是否找到 true 是，false 否 *******************************************/ bool hasPath(const char* matrix, int rows, int cols, const char* str) {if (matrix == nullptr || rows < 1 || cols < 1 || str == nullptr)return false;bool* visited = new bool[rows * cols];memset(visited, 0, rows * cols);int pathLength = 0;//遍歷矩陣中每個點，做為起點開始進行搜索for (int row = 0; row < rows; ++row){for (int col = 0; col < cols; ++col){if (hasPathCore(matrix, rows, cols, row, col, str,pathLength, visited)){delete[] visited;return true;}}}delete[] visited;return false; }/*探測下一個字符是否存在*/ bool hasPathCore(const char* matrix, int rows, int cols, int row,int col, const char* str, int& pathLength, bool* visited) {if (str[pathLength] == '\0')return true;bool hasPath = false;if (row >= 0 && row < rows && col >= 0 && col < cols&& matrix[row * cols + col] == str[pathLength]&& !visited[row * cols + col]){++pathLength;visited[row * cols + col] = true;hasPath = hasPathCore(matrix, rows, cols, row, col - 1,str, pathLength, visited)|| hasPathCore(matrix, rows, cols, row - 1, col,str, pathLength, visited)|| hasPathCore(matrix, rows, cols, row, col + 1,str, pathLength, visited)|| hasPathCore(matrix, rows, cols, row + 1, col,str, pathLength, visited);if (!hasPath){--pathLength;visited[row * cols + col] = false;}}return hasPath; } /*單元測試代碼*/ void Test(const char* testName, const char* matrix, int rows, int cols,const char* str, bool expected) {if (testName != nullptr)printf("%s begins: ", testName);if (hasPath(matrix, rows, cols, str) == expected)printf("Passed.\n");elseprintf("FAILED.\n"); }//ABTG //CFCS //JDEH //BFCE void Test1() {const char* matrix = "ABTGCFCSJDEH";const char* str = "BFCE";Test("功能測試 1", (const char*)matrix, 3, 4, str, true); }//ABCE //SFCS //ADEE //SEE void Test2() {const char* matrix = "ABCESFCSADEE";const char* str = "SEE";Test("功能測試 2", (const char*)matrix, 3, 4, str, true); }//ABTG //CFCS //JDEH //ABFB void Test3() {const char* matrix = "ABTGCFCSJDEH";const char* str = "ABFB";Test("功能測試 3", (const char*)matrix, 3, 4, str, false); }//ABCEHJIG //SFCSLOPQ //ADEEMNOE //ADIDEJFM //VCEIFGGS //SLHECCEIDEJFGGFIE void Test4() {const char* matrix = "ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS";const char* str = "SLHECCEIDEJFGGFIE";Test("功能測試 4", (const char*)matrix, 5, 8, str, true); }//ABCEHJIG //SFCSLOPQ //ADEEMNOE //ADIDEJFM //VCEIFGGS //SGGFIECVAASABCEHJIGQEM void Test5() {const char* matrix = "ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS";const char* str = "SGGFIECVAASABCEHJIGQEM";Test("功能測試 5", (const char*)matrix, 5, 8, str, true); }//ABCEHJIG //SFCSLOPQ //ADEEMNOE //ADIDEJFM //VCEIFGGS //SGGFIECVAASABCEEJIGOEM void Test6() {const char* matrix = "ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS";const char* str = "SGGFIECVAASABCEEJIGOEM";Test("功能測試 6", (const char*)matrix, 5, 8, str, false); }//ABCEHJIG //SFCSLOPQ //ADEEMNOE //ADIDEJFM //VCEIFGGS //SGGFIECVAASABCEHJIGQEMS void Test7() {const char* matrix = "ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS";const char* str = "SGGFIECVAASABCEHJIGQEMS";Test("功能測試 7", (const char*)matrix, 5, 8, str, false); }//AAAA //AAAA //AAAA //AAAAAAAAAAAA void Test8() {const char* matrix = "AAAAAAAAAAAA";const char* str = "AAAAAAAAAAAA";Test("邊界值測試 8", (const char*)matrix, 3, 4, str, true); }//AAAA //AAAA //AAAA //AAAAAAAAAAAAA void Test9() {const char* matrix = "AAAAAAAAAAAA";const char* str = "AAAAAAAAAAAAA";Test("邊界值測試 9", (const char*)matrix, 3, 4, str, false); }//A //A void Test10() {const char* matrix = "A";const char* str = "A";Test("邊界值測試 10", (const char*)matrix, 1, 1, str, true); }//A //B void Test11() {const char* matrix = "A";const char* str = "B";Test("邊界值測試 11", (const char*)matrix, 1, 1, str, false); }void Test12() {Test("特殊情況測試 12", nullptr, 0, 0, nullptr, false); }int main(int argc, char* argv[]) {Test1();Test2();Test3();Test4();Test5();Test6();Test7();Test8();Test9();Test10();Test11();Test12();system("pause");return 0; }

也可以借助棧實現(xiàn)，如下為實現(xiàn)的很垃圾的代碼：

typedef struct _Point {int x;int y; }Point;bool IsPointMatch(const char* martrix, int row, int col, int x, int y, const char* str, int index, bool* visit) {if ((martrix == NULL) || (str == NULL) || (visit == NULL)) return false;if ((x < 0) || (x >= row)) return false;if ((y < 0) || (y >= col)) return false;if ((martrix[col * x + y] == str[index]) && !visit[col * x + y]){return true;}return false; }bool TryGetPahtByStack(const char* martrix, int row, int col, int x, int y, const char* str, bool* visit) {stack<Point> pointStack;int index = 0;Point point = { x, y };Point nextPoint = { -1, -1 };if (str[index] != martrix[col * x + y]){return false;}else{pointStack.push(point);index++;visit[col * x + y] = true;}while (!pointStack.empty()){point = pointStack.top();//cout << point.x << ", " << point.y << endl;int temp_x = 0, temp_y = 0;if (str[index] == '\0'){return true;}temp_x = point.x + 1;temp_y = point.y;if (IsPointMatch(martrix, row, col, temp_x, temp_y, str, index, visit)){point.x = temp_x;point.y = temp_y;nextPoint.x = -1;pointStack.push(point);index++;visit[col * point.x + point.y] = true;continue;}temp_x = point.x - 1;temp_y = point.y;if (IsPointMatch(martrix, row, col, temp_x, temp_y, str, index, visit)){point.x = temp_x;point.y = temp_y;nextPoint.x = -1;pointStack.push(point);index++;visit[col * point.x + point.y] = true;continue;}temp_x = point.x;temp_y = point.y + 1;if (IsPointMatch(martrix, row, col, temp_x, temp_y, str, index, visit)){point.x = temp_x;point.y = temp_y;nextPoint.x = -1;pointStack.push(point);index++;visit[col * point.x + point.y] = true;continue;}temp_x = point.x;temp_y = point.y - 1;if (IsPointMatch(martrix, row, col, temp_x, temp_y, str, index, visit)){point.x = temp_x;point.y = temp_y;nextPoint.x = -1;pointStack.push(point);index++;visit[col * point.x + point.y] = true;continue;}if ((nextPoint.x >= 0) && (nextPoint.x < row) && (nextPoint.y >= 0) && (nextPoint.y < col)){visit[nextPoint.x * col + nextPoint.y] = false;}nextPoint = pointStack.top();pointStack.pop();index--;}memset(visit, 0, row * col);return false; }

---

參考資料：

C/C++從入門到精通-高級程序員之路【奇牛學院】

總結(jié)

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

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