|
之前我們已經(jīng)討論了采用回溯（Backtracking)方法來解決國際象棋中馬的遍歷問題。 為了讓大家更加熟悉回溯方法，我們將在后面的課程中再分析幾個例子。 今天先看一個使用回溯方法解決老鼠走迷宮的問題。 下圖是一個迷宮，其中涂上灰色的方格，老鼠不能進入，請找出老鼠從起點到終點的線路。老鼠只能向兩個方向移動：向前和向下，在下面的例子中也就是只能向右或向下移動。（注意，這是迷宮問題的一個簡單版本。 而在更復(fù)雜的版本中，老鼠可以在4個方向上移動或甚至可以跳著走） 下圖表示一條從起點到終點的可行路徑。 算法思路 我們把老鼠迷宮問題做一個抽象。 假設(shè)迷宮是一個N*N的二維矩陣（矩陣簡稱為M），矩陣中的每個元素M[i][j](0≤i≤N-1,0≤j≤N-1)是一個單元格方塊。 其中最左上方的塊，即M[0][0]是老鼠出發(fā)的格子，而最右下的格子M[N-1][N-1]是它的出口。 問題就變成從格子M[0][0]開始，尋找到達(dá)M[N-1][N-1]的路徑。 在老鼠闖蕩迷宮矩陣的過程中，我們用0和1來表示老鼠是否可以進入某個方格。如果某方格M[i][j]被標(biāo)注為0，那么表示它是一個死胡同，老鼠無法進入該方格；而如果它被標(biāo)注為1，則表示老鼠可以進入它。 因此上面的例子對應(yīng)的抽象矩陣為： {1, 0, 0, 0} {1, 1, 0, 1} {0, 1, 0, 0} {1, 1, 1, 1} 樸素算法的思路 樸素算法生成從起點格子到終點格子的所有路徑，并逐個檢查每個路徑是否能滿足約束條件。 如有還有未經(jīng)驗證的路徑 { 生成下一條路徑 如果此路徑的所有方格都為1 { 輸出這條路徑; } } 樸素算法需要列舉所有可行的路徑，可能效率會不高，特別是迷宮比較大的時候。 回溯算法的思路 下面是回溯算法的解題思路。 從起點方格開始，如果當(dāng)前所在的方格已經(jīng)是終點方格 打印輸出找到的路徑矩陣，結(jié)束 否則 a）將當(dāng)前方格標(biāo)記為1 b）在水平方向向右移動一個方格并遞歸檢查是否該移動可以找到解 c）如果在上述步驟中選擇的移動沒有找到解 那么向下移動一個方格并并遞歸檢查此移動是否可以找到解 d）如果上述方法都不起作用，則將該方格標(biāo)記為0，表示需要回退（Backtracing）并返回false 代碼實現(xiàn) 以下是老鼠迷宮問題的c/C++代碼實現(xiàn)。 它以二維矩陣形式打印出一種可能的解決方案。 最后的輸出是一個矩陣，顯示為1的格子是老鼠經(jīng)過的格子。 #include <stdio.h> // 迷宮大小 #define N 4 bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N]); /* 該函數(shù)可以輸出找到的解矩陣[N][N] */ void printSolution(int sol[N][N]) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) printf(' %d ', sol[i][j]); printf('\n'); } } /* 該函數(shù)檢查坐標(biāo)(x,y)是否是一個有效的方格 */ bool isSafe(int maze[N][N], int x, int y) { // 如果（x,y）超出了迷宮的范圍返回false if (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1) return true; return false; } /* 使用回溯算法解決迷宮問題。主要思路： 使用solveMazeUtil（）來尋找路徑。 如果沒有找到可行的路徑，則返回false 否則返回true并打印出找到的路徑（采用1來表示） 請注意，可能有多個解決方案，這里只找出一個可行的解決方案 */ bool solveMaze(int maze[N][N]) { int sol[N][N] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (solveMazeUtil(maze, 0, 0, sol) == false) { printf('Solution doesn't exist'); return false; } printSolution(sol); return true; } /*采用遞歸函數(shù)來解決迷宮問題*/ bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N]) { //如果（x,y）正好是目標(biāo)方格，那么返回true if (x == N - 1 && y == N - 1) { sol[x][y] = 1; return true; } //檢查（x,y）是否是一個合法的方格 if (isSafe(maze, x, y) == true) { // mark x, y as part of solution path //把（x，y）標(biāo)記為路徑中的一個方格 sol[x][y] = 1; /*向x方向，也就是右邊移動*/ if (solveMazeUtil(maze, x + 1, y, sol) == true) return true; /* 如果向x方向移動，沒有找到合適的路徑，那么，改向y方向，也就是向下移動*/ if (solveMazeUtil(maze, x, y + 1, sol) == true) return true; /* 如果以上的移動步驟，無法找到路徑，那么，將（x,y）標(biāo)記為0*/ sol[x][y] = 0; return false; } return false; } // 主程序 int main() { int maze[N][N] = { { 1, 0, 0, 0 }, { 1, 1, 0, 1 }, { 0, 1, 0, 0 }, { 1, 1, 1, 1 } }; solveMaze(maze); return 0; } 輸出的樣子如下： 1 0 0 0 1 1 0 0 0 1 0 0 0 1 1 1 請你試著運行看看是否能得到正確的答案。 |
|
|
