搜索与回溯是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。
如迷宫问题：进入迷宫后，先随意选择一个前进方向，一步步向前试探前进,如果碰到死胡同，说明前进方向已无路可走，这时，首先看其它方向是否还有路可走，如果有路可走，则沿该方向再向前试探；如果已无路可走，则返回一步，再看其它方向是否还有路可走；如果有路可走，则沿该方向再向前试探。按此原则不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。
搜索伪代码/公式 基本上所有的搜索与回溯都是这个公式的变种
void Search(int k) { for (i=1;i<=算符种数;i++) if (满足条件) { 保存结果 if (到目的地) 输出解; else Search(k+1); 恢复：保存结果之前的状态{回溯一步} } }【问题1】八皇后问题
题目 八皇后问题：要在国际象棋棋盘中放八个皇后，使任意两个皇后都不能互相吃。（提示：皇后能吃同一行、同一列、同一对角线的任意棋子。）
分析 放置第ｉ个(行)皇后的算法为： int search(i)； { int j; for (第i个皇后的位置j=1;j<=8;j++ ) //在本行的8列中去试 if (本行本列允许放置皇后) { 放置第i个皇后； 对放置皇后的位置进行标记； if (i==8) 输出 //已经放完个皇后 else search(i+1)； //放置第i+1个皇后 对放置皇后的位置释放标记，尝试下一个位置是否可行； } }
参考代码
public class EightQueue { /** * 存放每一行，皇后的位置，a[1]=6，代表第一行的皇后放在位置6 * */ int[] a = new int[9]; /** * 每一列，是否被放置了皇后 * */ int[] b = new int[9]; /** * 左对角线是否放置了皇后 * */ int[] c = new int[17]; /** * 右对角线是否放置了皇后 * */ int[] d = new int[17]; /** * 解法的个数 * */ int num = 0; public void search(int n) { // 算符种类 for (int i=1; i<=8; i++) { // 判断是否可以放棋子 if(b[i]==0 && c[n+i]==0 && d[n-i+8]==0) { // 保存条件 a[n] = i; b[i] = 1; c[n+i] = 1; d[n-i+8] = 1; // 目的地 if (n == 8) { print(a); num ++; } else { search(n + 1); } // 回溯 b[i] = 0; c[n+i] = 0; d[n-i+8] = 0; } } } public void print(int[] a) { for (int i=1; i<a.length; i++) { System.out.print(a[i] + " "); } System.out.println(""); } public static void main(String[] args) { EightQueue e = new EightQueue(); e.search(1); System.out.println("解法个数 " + e.num);//92个解 } }【问题2】自然数分解
任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和
当n=7共14种拆分方法： 7=1+1+1+1+1+1+1 7=1+1+1+1+1+2 7=1+1+1+1+3 7=1+1+1+2+2 7=1+1+1+4 7=1+1+2+3 7=1+1+5 7=1+2+2+2 7=1+2+4 7=1+3+3 7=1+6 7=2+2+3 7=2+5 7=3+4 total=14
【代码实现】
/** * @author 谢世杰 */ public class SplitData { int[] a; int goal; /** * 任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和 * 算符种类：要分割的自然数n * 结果数组：a[n],存储这分割的结果 * */ void search(int n, int t) { // 算符种类，从1开始，一直到n for (int i=a[t-1]; i<=n; i++) { // 满足条件,把分解的数字存入数组并在n基础上减去 // 当前数i要大于等于前1位数，且不过n if(i < goal) { a[t] = i; n -= i; if (n == 0) { print(t); } else { search(n, t+1); } n += i; } } } public void print(int t) { System.out.println("结果为："); for (int i=1; i <= t; i++) { System.out.print(a[i] + " "); } System.out.println(""); } public static void main(String[] args) { SplitData s = new SplitData(); // 想要分解的自然数 int n = 7; s.a = new int[n+1]; for (int i=0; i<s.a.length; i++) { s.a[i] = 1; } s.goal = n; s.search(n,1); } }