|
回溯是一类算法模式，它通过尝试不同的解决方案，直到找到“有效”的解决方案。 通常能够使用回溯技术解决的问题具有以下共同特性：这些问题只能通过尝试每个可能的方案来解决，并且每个方案只尝试一次。 针对这类问题，一个”傻瓜式“的办法是尝试所有方案并输出符合给定问题条件的方案。 一般来说，这种办法的效率不高，有些情形下，可能无法在时间和资源限制下找到解答。 而回溯技术以增量方式工作，是对上面”傻瓜式解决方案“的优化。 下面我们用一个经典问题来说明： 国际象棋中的马的遍历（Knight's Tour）问题 马被放置在国际象棋棋盘的某个格子内，并按照国际象棋的规则移动，必须完全访问棋盘中的每个方块格子正好一次。 根据国际象棋中马的移动规则，它从当前位置最多可以移动到八个位置，见下图。 因此，现在我们要找到一种方案，使得马可以依照移动规则，遍历上述棋盘中的每个格子，而且不能有重复，也不能有遗漏。 以下是有8 x 8个格子的棋盘。从任意一个格子开始，马依照连线移动，这样马的足迹正好覆盖棋盘上的所有格子一次。 我们先来看看采用傻瓜式方案——称为朴素（Naive）算法来解决这个问题的思路，然后再看看如何运用回溯算法来改进它。 算法思路 朴素算法的思路 朴素算法是依次尝试所有的走法，然后从中找到可以满足约束条件的方案。算法描述如下： 1）如果还有没有尝试过的遍历方案，就执行下面第2）步 否则，输出此问题没有解答 2）找到下一个遍历方案 3）如果这个方案可以覆盖所有棋盘上的方格，那么输出该方案的遍历路径，结束； 否则，回到1） 回溯方法的思路 回溯方法以增量方式工作以解决问题，它的基本思路如下： 通常情况下，我们从一个空的解决方案向量中开始逐个添加条目（条目的含义因问题而异。比如对于马的棋盘遍历问题，一个条目就是在棋盘上马的一次移动）。 当我们添加一个条目时，我们检查添加的当前项目是否违反了问题约束条件，如果违反了某个约束条件，那么我们删除该条目并尝试其他替代方案。 如果没有其他替代方案可以解决问题，那么我们将返回上一阶段并删除上一阶段添加的条目。 如果我们回到初始阶段，那么我们说没有解决方案存在。 如果添加条目并不违反约束条件，那么我们将通过递归逐个添加条目。 如果最后能成功得到完全的解决方案向量，那么我们将输出对应的解决方案。 马的棋盘遍历问题的回溯算法 我们用一个8X8的二维数组表示解，它将记录马在棋盘上依次移动的次序。 二位数组的每个元素对应棋盘上的一个方格。每个元素是一个数字，它表示了马的移动次序。 下面的图记录了一个解，也就是马依照 0->1->2->...->63的次序可以正好访问所有格子，并且每个格子只访问一次。 以下是马的遍历问题的回溯算法： 如果访问了所有方块都已被访问到，打印输出对应的解决方案，否则 a）将找到下一个可以移动目的地并将它添加到求解数组并递归检查本次移动是否会找到合适的解决方案。（依照国际象棋的规则，马可以最多可以移动到八个位置，我们需要从8个目的地中选择一个） b）如果在上述步骤中选择的移动没有导致找到合适的解决方案，那么从解决方案数组中删除此次移动并尝试其他的移动目的地。 c）如果没有找到其他合适的目的地，则返回false（返回false将在递归中删除以前添加的条目。如果为false返回给最初的初始调用，那么就表示该问题“没有解决方案存在”） 代码实现 以下是马的遍历问题的c/C++代码实现。 它以二维矩阵形式打印出一种可能的解决方案。 基本上，输出是一个 8 * 8矩阵，数字从0到63，这些数字显示了马在棋盘上的遍历步数。 #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); } //打印出结果 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'); } } //该函数使用回溯方法解决马的遍历问题。 //如果返回false,表示无解 //否则返回true并打印出结果 bool solveKT() { int sol[N][N]; //初始化解的向量 for (int x = 0; x < N; x++) for (int y = 0; y < N; y++) sol[x][y] = -1; //按照国际象棋规则，定义马的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开始运行函数solveKTUtil()找答案 if (solveKTUtil(0, 0, 1, sol, xMove, yMove) == false) { printf('Solution does not exist'); return false; } else printSolution(sol); return true; } //函数solveKTUtil用来寻找目标方案 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; //从当前位置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; } |
|
|
