如何使用100010解决复杂问题

回溯法

对于回溯法，网上有很多种解释，这里我依照自己的（死宅）观点做了以下三种通俗易懂的解释：

正经版解释：其实人生就像一颗充满了分支的n叉树，你的每一个选择都会使你走向不同的路线，获得不同的结局。如果能重来，我要选李白~呸！说错了，如果能重来，我们就能回溯到以前，选择到最美好的结局。游戏版解释：玩过互动电影游戏（如 行尸走肉）的都知道，你的每个选择都会影响游戏的结局，掌控他人的生死。每次选择错误导致主角或配角死亡，我们是不是回溯读档，希望得到一个更好的结局。PS：克莱曼婷天下无敌！动漫版解释：看过主角拥有死亡回归（疯狂暗示486）的都知道，主角的每个选择都能影响大局，可是486直接能回溯重选，这与我们今天要讲的回溯法极其相似。PS：爱蜜莉雅、雷姆我都要！专业名词解空间： 即 所有的可能情况概念

回溯算法：是类似于枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

它是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术称为 回溯法 ，而满足回溯条件的某个状态的点称为 “回溯点” （你也可以理解为 存档点 ）。

答案：明确函数功能：jump(m, n)为跳到(m, n)位置。寻找递归出口：不在边界之内 或 已走过。明确所有路径：右跳、左跳、下跳、上跳回溯还原现场：path–; // 回溯法关键步骤a[m][n] = 0;

//青蛙跳public class Sy1 { static int count = 0; // 跳法种类计数 static int x = 4, y = 4; // 目的坐标 static int step = 0; // 记录步数 // 地图，0代表没有走过，1 代表已经走过 static int[][] map = { { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 }, { 1, 1, 0, 1, 1 }, { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 } }; static int min = 25; // 用来记录最小步数 static int sx[] = new int[25], sy[] = new int[25]; // 记录坐标 // 求解总共跳法，并求出最短步数，方便下面列出路径 static void jump(int m, int n) { if (m = 5 || n = 5 || map[m][n] != 0) { // 该点在地图边界之内并且未走过 return; } map[m][n] = 1; // 走到此节点 step ; if (m == x && n == y) { // 如果到达目的地 if (step < min)// 更新最短步数 min = step; count ; } // 所有路径 jump(m 1, n); // 右跳 jump(m - 1, n); // 左跳 jump(m, n 1); // 下跳 jump(m, n - 1); // 上跳 step--; // 回溯法关键步骤 map[m][n] = 0; } // 列出最短步数的路径 static void find(int m, int n) { if (m = 5 || n = 5 || map[m][n] != 0) { // 该点在地图边界之内并且未走过 return; } // 记录坐标 sx[step] = m; sy[step] = n; // 走到此节点 map[m][n] = 1; step ; if (m == x && n == y && step == min) { // 到达目的且为最短路径 int p = min - 1; System.out.print("最短 path:" p "步"); for (int i = 0; i < min; i ) System.out.print("(" sx[i] "," sy[i] ")"); System.out.println(); } find(m 1, n); find(m - 1, n); find(m, n 1); find(m, n - 1); step--; map[m][n] = 0; } public static void main(String[] args) { jump(0, 0); step = 0; System.out.println("总共" count "种解法"); find(0, 0); } }

程序运行结果：

所以， 在点m存在的情况下，与点m列差为d的点，若行差也为±d，那么就在一条斜线上，不合法。

cols[N] != cols[m]（与第 m 列的棋子不在同一行）cols[N] != cols[m] – (N-m) （>=0 ,与第 m 列的棋子不在同一斜线上）cols[N] != cols[m] (N-m) （<=8-1,与第 m 列的棋子不在同一反斜线上）

我们规定当 row[i]=true 时，表示该列第 i 行不能放棋子。

总结：编写检测函数：正如上面的分析，每摆一个，将不合法的位置用数组标识，就不涉足了。当然，也可以写成函数，不过没有数组快。明确函数功能：put(n)为摆第n个皇后。寻找递归出口：不同行、不同斜线、不同反斜线。明确所有路径：八行。回溯还原现场：不需要还原，没有破坏现场，因为检测的时候提前用数组标识了，所以不合法的现场都没涉足。

这样我们就能写成下列程序段了：

// 八皇后class Sy6 { public static int num = 0; // 累计方案总数 public static final int MAXQUEEN = 8;// 皇后个数，同时也是棋盘行列总数 public static int[] cols = new int[MAXQUEEN]; // 定义cols数组，表示8列棋子摆放情况，数组元素存放行号 public Sy6() { // 核心函数 put(0); System.out.println(MAXQUEEN “皇后问题有” num “种摆放方法。”); } // 摆第n个皇后 public void put(int n) { // 遍历该列所有不合法的行，并用 rows 数组记录，不合法即 rows[i]=true boolean[] rows = new boolean[MAXQUEEN]; // boolean默认false for (int i = 0; i = 0) // 判断是否超界 // 行差为-d的斜线点，不合法 rows[cols[i] – d] = true; if (cols[i] d <= MAXQUEEN - 1)// 判断是否超界 // 行差为d的斜线点，不合法 rows[cols[i] d] = true; } // 所有路径：八行都能摆 for (int i = 0; i < MAXQUEEN; i ) { // 判断该行是否合法，如果不合法，那就继续下一轮 // 递归出口 if (rows[i]) continue; // 设置当前列合法棋子所在行数 cols[n] = i; // 当前列不为最后一列时 if (n < MAXQUEEN - 1) { // 摆放下一个 put(n 1); } else { // 累计方案个数 num ; } } } public static void main(String args[]) { Sy6 queen = new Sy6(); }}

程序运行结果：