|
回溯是一類算法模式，它通過嘗試不同的解決方案，直到找到“有效”的解決方案。 通常能夠使用回溯技術(shù)解決的問題具有以下共同特性：這些問題只能通過嘗試每個可能的方案來解決，并且每個方案只嘗試一次。 針對這類問題，一個”傻瓜式“的辦法是嘗試所有方案并輸出符合給定問題條件的方案。 一般來說，這種辦法的效率不高，有些情形下，可能無法在時間和資源限制下找到解答。 而回溯技術(shù)以增量方式工作，是對上面”傻瓜式解決方案“的優(yōu)化。 下面我們用一個經(jīng)典問題來說明： 國際象棋中的馬的遍歷（Knight's Tour）問題 馬被放置在國際象棋棋盤的某個格子內(nèi)，并按照國際象棋的規(guī)則移動，必須完全訪問棋盤中的每個方塊格子正好一次。 根據(jù)國際象棋中馬的移動規(guī)則，它從當(dāng)前位置最多可以移動到八個位置，見下圖。 因此，現(xiàn)在我們要找到一種方案，使得馬可以依照移動規(guī)則，遍歷上述棋盤中的每個格子，而且不能有重復(fù)，也不能有遺漏。 以下是有8 x 8個格子的棋盤。從任意一個格子開始，馬依照連線移動，這樣馬的足跡正好覆蓋棋盤上的所有格子一次。 我們先來看看采用傻瓜式方案——稱為樸素（Naive）算法來解決這個問題的思路，然后再看看如何運用回溯算法來改進它。 算法思路 樸素算法的思路 樸素算法是依次嘗試所有的走法，然后從中找到可以滿足約束條件的方案。算法描述如下： 1）如果還有沒有嘗試過的遍歷方案，就執(zhí)行下面第2）步 否則，輸出此問題沒有解答 2）找到下一個遍歷方案 3）如果這個方案可以覆蓋所有棋盤上的方格，那么輸出該方案的遍歷路徑，結(jié)束； 否則，回到1） 回溯方法的思路 回溯方法以增量方式工作以解決問題，它的基本思路如下： 通常情況下，我們從一個空的解決方案向量中開始逐個添加條目（條目的含義因問題而異。比如對于馬的棋盤遍歷問題，一個條目就是在棋盤上馬的一次移動）。 當(dāng)我們添加一個條目時，我們檢查添加的當(dāng)前項目是否違反了問題約束條件，如果違反了某個約束條件，那么我們刪除該條目并嘗試其他替代方案。 如果沒有其他替代方案可以解決問題，那么我們將返回上一階段并刪除上一階段添加的條目。 如果我們回到初始階段，那么我們說沒有解決方案存在。 如果添加條目并不違反約束條件，那么我們將通過遞歸逐個添加條目。 如果最后能成功得到完全的解決方案向量，那么我們將輸出對應(yīng)的解決方案。 馬的棋盤遍歷問題的回溯算法 我們用一個8X8的二維數(shù)組表示解，它將記錄馬在棋盤上依次移動的次序。 二位數(shù)組的每個元素對應(yīng)棋盤上的一個方格。每個元素是一個數(shù)字，它表示了馬的移動次序。 下面的圖記錄了一個解，也就是馬依照 0->1->2->...->63的次序可以正好訪問所有格子，并且每個格子只訪問一次。 以下是馬的遍歷問題的回溯算法： 如果訪問了所有方塊都已被訪問到，打印輸出對應(yīng)的解決方案，否則 a）將找到下一個可以移動目的地并將它添加到求解數(shù)組并遞歸檢查本次移動是否會找到合適的解決方案。（依照國際象棋的規(guī)則，馬可以最多可以移動到八個位置，我們需要從8個目的地中選擇一個） b）如果在上述步驟中選擇的移動沒有導(dǎo)致找到合適的解決方案，那么從解決方案數(shù)組中刪除此次移動并嘗試其他的移動目的地。 c）如果沒有找到其他合適的目的地，則返回false（返回false將在遞歸中刪除以前添加的條目。如果為false返回給最初的初始調(diào)用，那么就表示該問題“沒有解決方案存在”） 代碼實現(xiàn) 以下是馬的遍歷問題的c/C++代碼實現(xiàn)。 它以二維矩陣形式打印出一種可能的解決方案。 基本上，輸出是一個 8 * 8矩陣，數(shù)字從0到63，這些數(shù)字顯示了馬在棋盤上的遍歷步數(shù)。 #include<stdio.h> #define N 8 int solveKTUtil(int x, int y, int movei, int sol[N][N], int xMove[], int yMove[]); //看看棋盤位置[i,j]是否可用 bool isSafe(int x, int y, int sol[N][N]) { return ( x >= 0 && x < N && y >= 0 && y < N && sol[x][y] == -1); } //打印出結(jié)果 void printSolution(int sol[N][N]) { for (int x = 0; x < N; x++) { for (int y = 0; y < N; y++) printf(' %2d ', sol[x][y]); printf('\n'); } } //該函數(shù)使用回溯方法解決馬的遍歷問題。 //如果返回false,表示無解 //否則返回true并打印出結(jié)果 bool solveKT() { int sol[N][N]; //初始化解的向量 for (int x = 0; x < N; x++) for (int y = 0; y < N; y++) sol[x][y] = -1; //按照國際象棋規(guī)則，定義馬的8個合法的移動位置 // xMove[] 和yMove[]分別定義x和y的移動方向 int xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 }; int yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 }; //從棋盤的[0][0]位置開始 sol[0][0] = 0; //從0，0開始運行函數(shù)solveKTUtil()找答案 if (solveKTUtil(0, 0, 1, sol, xMove, yMove) == false) { printf('Solution does not exist'); return false; } else printSolution(sol); return true; } //函數(shù)solveKTUtil用來尋找目標(biāo)方案 int solveKTUtil(int x, int y, int movei, int sol[N][N], int xMove[N], int yMove[N]) { int k, next_x, next_y; if (movei == N*N) return true; //從當(dāng)前位置x,y開始嘗試所有的8個移動位置 for (k = 0; k < 8; k++) { next_x = x + xMove[k]; next_y = y + yMove[k]; if (isSafe(next_x, next_y, sol)) { sol[next_x][next_y] = movei; if (solveKTUtil(next_x, next_y, movei+1, sol, xMove, yMove) == true) return true; else sol[next_x][next_y] = -1;// backtracking } } return false; } //主程序 int main() { solveKT(); return 0; } |
|
|
