2023年8月2日发(作者：)

回溯法的解题步骤与例⼦解析 回溯法有“通⽤解题法”之称。⽤它可以系统地搜索问题的所有解。回溯法是⼀个既带有系统性⼜带有跳跃性的搜索算法。 在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某⼀结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。若⽤回溯法求问题的所有解时，要回溯到根，且根结点的所有可⾏的⼦树都要已被搜索遍才结束。 ⽽若使⽤回溯法求任⼀个解时，只要搜索到问题的⼀个解就可以结束。

1.回溯法的解题步骤(1)针对所给问题，定义问题的解空间；(2)确定易于搜索的解空间结构；(3)以深度优先⽅式搜索解空间，并在搜索过程中⽤剪枝函数避免⽆效搜索。

2.⼦集树与排列树下⾯的两棵解空间树是回溯法解题时常遇到的两类典型的解空间树。(1)当所给问题是从n个元素的集合S中找出S满⾜某种性质的⼦集时，相应的解空间树称为⼦集树。例如从n个物品的0-1背包问题(如下图)所相应的解空间树是⼀棵⼦集树，这类⼦集树通常有2^n个叶结点，其结点总个数为2^(n+1)-1。遍历⼦集树的算法需Ω(2^n)计算时间。(2)当所给问题是确定n个元素满⾜某种性质的排列时，相应的解空间树称为排列树。例如旅⾏售货员问题(如下图)的解空间树是⼀棵排列树，这类排列树通常有n!个叶结点。遍历⼦集树的算法需Ω(n!)计算时间。⽤回溯法搜索⼦集树的⼀般算法可描述为： /** * output(x) 记录或输出得到的可⾏解x * constraint(t) 当前结点的约束函数 * bount(t) 当前结点的限界函数 * @param t t为当前解空间的层数 */ void backtrack(int t){ if(t >= n) output(x); else for (int i = 0; i <= 1; i++) { x[t] = i; if(constraint(t) && bount(t)) backtrack(t+1); } }⽤回溯法搜索排列树的⼀般算法可描述为：

/** * output(x) 记录或输出得到的可⾏解x * constraint(t) 当前结点的约束函数 * bount(t) 当前结点的限界函数 * @param t t为当前解空间的层数 */ void backtrack(int t){ if(t >= n) output(x); else for (int i = t; i <= n; i++) { swap(x[t], x[i]); if(constraint(t) && bount(t)) backtrack(t+1); swap(x[t], x[i]); } }3.回溯法的应⽤例⼦(a)⼦集树（为了便于描述算法，下列⽅法使⽤了较多的全局变量）I.输出集合S中所有的⼦集，即limit为all；II.输出集合S中限定元素数量的⼦集，即limit为num；III.输出集合S中元素奇偶性相同的⼦集，即limit为sp。public class Subset {

private static int[] s = {1,2,3,4,5,6,7,8}; private static int n = ; private static int[] x = new int[n];

/** * 输出集合的⼦集 * @param limit 决定选出特定条件的⼦集 * @param limit 决定选出特定条件的⼦集 * 注：all为所有⼦集,num为限定元素数量的⼦集, * sp为限定元素奇偶性相同，且和⼩于8。 */ public static void all_subset(String limit){ switch(limit){ case "all":backtrack(0);break; case "num":backtrack1(0);break; case "sp":backtrack2(0);break; } }

/** * 回溯法求集合的所有⼦集，依次递归 * 注：是否回溯的条件为精髓 * @param t */ private static void backtrack(int t){ if(t >= n) output(x); else for (int i = 0; i <= 1; i++) { x[t] = i; backtrack(t+1); }

}

/** * 回溯法求集合的所有(元素个数⼩于4)的⼦集，依次递归 * @param t */ private static void backtrack1(int t){ if(t >= n) output(x); else for (int i = 0; i <= 1; i++) { x[t] = i; if(count(x, t) < 4) backtrack1(t+1); }

} /** * (剪枝) * 限制条件：⼦集元素⼩于4,判断0~t之间已被选中的元素个数， * 因为此时t之后的元素还未被递归,即决定之后的元素 * 是否应该被递归调⽤ * @param x * @param t * @return */ private static int count(int[] x, int t) { int num = 0; for (int i = 0; i <= t; i++) { if(x[i] == 1){ num++; } } return num; } /** * 回溯法求集合中元素奇偶性相同，且和⼩于8的⼦集,依次递归 * 回溯法求集合中元素奇偶性相同，且和⼩于8的⼦集,依次递归 * @param t */ private static void backtrack2(int t){ if(t >= n) output(x); else for (int i = 0; i <= 1; i++) { x[t] = i; if(legal(x, t)) backtrack2(t+1); }

}

/** * 对⼦集中元素奇偶性进⾏判断，还需元素的数组和⼩于8 * @param x * @param t * @return */ private static boolean legal(int[] x, int t) { boolean bRet = true; //判断是否需要剪枝 int part = 0; //奇偶性判断的基准

for (int i = 0; i <= t; i++) { //选择第⼀个元素作为奇偶性判断的基准 if(x[i] == 1){ part = i; break; } }

for (int i = 0; i <= t; i++) { if(x[i] == 1){ bRet &= ((s[part] - s[i]) % 2 == 0); }

} int sum = 0; for(int i = 0; i <= t; i++){ if(x[i] == 1) sum += s[i]; } bRet &= (sum < 8);

return bRet; } /** * ⼦集输出函数 * @param x */ private static void output(int[] x) { for (int i = 0; i < ; i++) { if(x[i] == 1){ (s[i]); } } n();

}}(b) 排列树（为了便于描述算法，下列⽅法使⽤了较多的全局变量）I.输出集合S中所有的排列，即limit为all；II.输出集合S中元素奇偶性相间的排列，即limit为sp。public class Permutation { private static int[] s = {1,2,3,4,5,6,7,8}; private static int n = ; private static int[] x = new int[n];

/** * 输出集合的排列 * @param limit 决定选出特定条件的⼦集 * 注：all为所有排列,sp为限定元素奇偶性相间。 */ public static void all_permutation(String limit){ switch(limit){ case "all":backtrack(0);break; case "sp":backtrack1(0);break; } }

/** * 回溯法求集合的所有排列，依次递归 * 注：是否回溯的条件为精髓 * @param t */ private static void backtrack(int t){ if(t >= n) output(s); else for (int i = t; i < n; i++) { swap(i, t, s); backtrack(t+1); swap(i, t, s); }

} /** * 回溯法求集合中元素奇偶性相间的排列,依次递归 * @param t */ private static void backtrack1(int t){ if(t >= n) output(s); else for (int i = t; i < n; i++) { swap(i, t, s); if(legal(x, t)) backtrack1(t+1); swap(i, t, s); }

}

/** * 对⼦集中元素奇偶性进⾏判断 * 对⼦集中元素奇偶性进⾏判断 * @param x * @param t * @return */ private static boolean legal(int[] x, int t) { boolean bRet = true; //判断是否需要剪枝

//奇偶相间,即每隔⼀个数判断奇偶相同 for (int i = 0; i < t - 2; i++) { bRet &= ((s[i+2] - s[i]) % 2 == 0); }

return bRet; } /** * 元素交换 * @param i * @param j */ private static void swap(int i, int j,int[] s) { int tmp = s[i]; s[i] = s[j]; s[j] = tmp; }

/** * ⼦集输出函数 * @param x */ private static void output(int[] s) { for (int i = 0; i < ; i++) { (s[i]); } n();

}}参考⽂献：1. 《算法设计与分析》