上一遍文章我们过了一次广度优先算法, 算是比较好理解的, 因为模式比较固定, 使用队列再进行 while() 循环, 既可以满足大部分时候的需求这一次我们来开始学习 / 复习一下我们的深度优先算法深度优先算法其实在很多地方都可以应用到, 其实在我的看法, 只要搜索集合相对固定, 并且使用到递归的算法都可以算是深度优先而且在学习完回溯算法的很多题目之后, 大家也可以更直观的体验到, 很多时候回溯也是暴力搜索的一种程序上的实现而已所以,
1. 回溯
2. 深度优先
3. 暴力搜索
这三种算法, 名字虽然不同, 但是都在某些情况下是有很大的共同成分的大家在看完题目之后可以好好感受一下
那么进入正题
1. 理解递归
如果是计算机专业的同学可能可以忽略这一小节
[图片上传失败...(image-1a1a5f-1518421713974)]
其实递归的方法和一般的方法有什么区别呢? 答案是完全没有, 递归的方法和一般的方法完全没有区别一个标准的方法 / 函数, 都是需要在方法 / 函数栈里面进行调用和返回的举个栗子
- static void a() {
- b();
- }
- static void b() {
- c();
- }
- static void c() {
- System.out.println("methods")
- }
- public static void main(String[] args) {
- a();
- }
下面这段代码在方法栈中的执行过程如下两图所示
方法执行
方法结束
如上图所示, 所有的方法在执行结束之后都会返回, return, 这个 return, 代表的是 return 到该方法的调用者, 也就是执行该方法的方法内, 也就是上一层中
理解了这个, 递归也就很好理解, 同样是使用方法 / 函数栈, 只不过是调用的方法是相同的方法而已
2. 理解回溯
理解回溯, 我们先从一个例题来看一下
我们有一个集合 / 列表, 含有若干整数(不含有重复), 例如:{1,2,3} 求该集合的全排列
- {1,2,3}
- {1,3,2}
- {2,1,3}
- {2,3,1}
- {3,1,2}
- {3,2,1}
从直观的感觉来说, 第一眼遇到这个题目, 我们可以这么去抽象的构思:
我们按照步骤 / 状态来抽象的话, 我们每一刻都有一个可用集合, 一个答案集合每一步都需要从可用集合里面抽取一个元素加入到答案集合在答案集合满了 (或者是可用集合空了) 的时候, 代表我们获取了一个答案, 这时需要向后, 往可用集合内部退回元素再重新做抽取的步骤, 往答案集合中放置元素
1 开头的集合答案
可以看出来, 我们每次获取答案都要向上退后一步, 回到之前的状态, 选取不同的元素放入结果集合这个过程其实就是我们之前所讲的回溯至于怎么样遍历集合, 根据题目的要求我们可以有不同的策略, 一般的回溯算法都是涉及列表的遍历, for 循环足矣
我们来看看代码
- public List < List > getPermutation(List < Integer > list) {
- List result = new ArrayList < >();
- permutateHelper(result, new ArrayList < >(), list, new HashSet < Integer > ());
- return result;
- }
- private void permutateHelper(List result, List < Integer > temp, List < Integer > list, HashSet < Integer > visited) {
- // 如果 temp,temp 答案集合满了, 我们加入到最终的结果集合内
- if (temp.size() == list.size()) {
- result.add(new ArrayList(temp));
- } else {
- // 直接使用 for 循环进行对原集合的遍历
- for (int i = 0; i < list.size(); i++) {
- // 如果没有 visit 过, 进行递归
- if (!visited.contains(list.get(i))) {
- int current = list.get(i);
- temp.add(current);
- visited.add(current);
- // 进入下一层递归
- permutateHelper(result, temp, list, visited);
- visited.remove(current);
- // 这里需要直接 remove 掉最后一个元素, 因为我们的全部的下一层递归已经结束, 所以可以把该层的数字删掉, 进入 for 循环的下一个遍历的开始了这里这个 remove 的动作就是我们所谓的回溯
- temp.remove(temp.size() - 1);
- }
- }
- }
- }
从以上代码我们可以看出, 回溯算法其实就是普通的递归, 但是加上了对集合遍历 (for 循环) 的过程, 大家可以体会一下一个小小的区别假如在以上的代码中, 我们的 temp 不删除最后一个元素, 改成这样:
- private void permutateHelper(List result, List < Integer > temp, List < Integer > list, HashSet < Integer > visited) {
- if (temp.size() == list.size()) {
- result.add(new ArrayList(temp));
- } else {
- for (int i = 0; i < list.size(); i++) {
- if (!visited.contains(list.get(i))) {
- int current = list.get(i);
- temp.add(current);
- visited.add(current);
- // 进入下一层递归, 不删除最后一个元素, 每次都创建一个新的 temp 列表
- permutateHelper(result, new ArrayList < >(temp), list, visited);
- visited.remove(current);
- }
- }
- }
- }
简单的一行的修改, 最后的答案也是对的(先不说这个修改浪费了多少空间), 可是却完全的改变了我们要的回溯的本质, 没有向前退的这个动作, 这个程序就变成了单纯的递归, 暴力搜索了
关于排列组合的题目, 还有更加难的, 比如集合中有重复元素怎么办, 如果不只是求全排列, 而是求子集呢?
有兴趣的同学可以看看 leetcode 上的题目:
- Permutation II
- Subset
相信大家对所谓的回溯已经有点理解了我们再来一个难一点点的题目
3. 电话键盘
例题来自 leetcode 的一道关于电话键盘的题目
Screen Shot 2018-02-12 at 3.14.47 PM.png
这个题目就是说, 在手机上按几个数字键, 对应可能产生的所有可能的字母的集合比如在手机上按 23, 就是从 {a,b,c} 和{d,e,f}中各取一个放入答案集合中
这题和上一题的区别是, 搜索集合不再是一个固定的大集合了, 而是若干的小集合, 每个数字对应一个小集合, 满足搜索结果的答案的标准也不一样, 不再是以集合的元素数量为标准, 而是以我们的输入数字的数量为标准
我们直接看代码
- public List<String> letterCombinations(String digits) {
- if (digits == null || digits.length() == 0) {
- return new ArrayList<>();
- }
- /// 先初始化手机按键的数字和字母的关系
- String[] one = { "" };
- String[] two = { "a", "b", "c" };
- String[] three = { "d", "e", "f" };
- String[] four = { "g", "h", "i" };
- String[] five = { "j", "k", "l" };
- String[] six = { "m", "n", "o" };
- String[] seven = { "p", "q", "r", "s" };
- String[] eight = { "t", "u", "v" };
- String[] nine = { "w", "x", "y", "z" };
- String[] zero = { "" };
- HashMap<Integer, String[]> map = new HashMap<>();
- map.put(0, zero);
- map.put(1, one);
- map.put(2, two);
- map.put(3, three);
- map.put(4, four);
- map.put(5, five);
- map.put(6, six);
- map.put(7, seven);
- map.put(8, eight);
- map.put(9, nine);
- ArrayList<String> result = new ArrayList<>();
- int[] allNum = new int[digits.length()];
- for (int i = 0; i < digits.length(); i++) {
- allNum[i] = Integer.parseInt(digits.substring(i, i + 1));
- }
- phoneNumberHelper(result, new StringBuilder(), 0, allNum, map);
- return result;
- }
- private void phoneNumberHelper(ArrayList<String> result, StringBuilder current, int index, int[] allNum,
- HashMap<Integer, String[]> com) {
- // 如果找到一个排列, 加入答案中
- if (index == allNum.length) {
- result.add(current.toString());
- return;
- } else {
- // 使用 for 循环, 遍历当前该数字的字母集合
- String[] possibilities = com.get(allNum[index]);
- for (int i = 0; i < possibilities.length; i++) {
- phoneNumberHelper(result, current.append(possibilities[i]), index + 1, allNum, com);
- // 一定要把 StringBuilder 的最后一位删除掉
- current.deleteCharAt(current.length()-1);
- }
- }
- }
可以看出, 回溯的题目并不难, 在理解了排列组合题目之后, 理解这个就简单一些了我们对比一下和排列组合题目的不同
搜索集合在每一个状态都不一样, 排列组合在每个步骤都是相同的搜索集合, 电话按键根据按下的数字不一样, 对应的字母不一样
对于回溯算法的精髓, 大家通过对两个题目的练习可以发现, 就在于那个 remove 的动作, 假如上面这个算法我改成这样, 不使用 StringBuilder, 而直接使用 Sting.
- public List<String> letterCombinations(String digits) {
- if (digits == null || digits.length() == 0) {
- return new ArrayList<>();
- }
- String[] one = { "" };
- String[] two = { "a", "b", "c" };
- String[] three = { "d", "e", "f" };
- String[] four = { "g", "h", "i" };
- String[] five = { "j", "k", "l" };
- String[] six = { "m", "n", "o" };
- String[] seven = { "p", "q", "r", "s" };
- String[] eight = { "t", "u", "v" };
- String[] nine = { "w", "x", "y", "z" };
- String[] zero = { "" };
- HashMap<Integer, String[]> map = new HashMap<>();
- map.put(0, zero);
- map.put(1, one);
- map.put(2, two);
- map.put(3, three);
- map.put(4, four);
- map.put(5, five);
- map.put(6, six);
- map.put(7, seven);
- map.put(8, eight);
- map.put(9, nine);
- ArrayList<String> result = new ArrayList<>();
- int[] allNum = new int[digits.length()];
- for (int i = 0; i < digits.length(); i++) {
- allNum[i] = Integer.parseInt(digits.substring(i, i + 1));
- }
- phoneNumberHelper(result, "", 0, allNum, map);
- return result;
- }
- private void phoneNumberHelper(ArrayList<String> result, String current, int index, int[] allNum,
- HashMap<Integer, String[]> com) {
- if (index == allNum.length) {
- result.add(current);
- return;
- } else {
- String[] possibilities = com.get(allNum[index]);
- for (int i = 0; i < possibilities.length; i++) {
- // 不使用 StringBuilder, 直接使用 String 连接一个 String, 这个做法其实和 new String()是一样的创建了一个新的 String,
- phoneNumberHelper(result, current + possibilities[i], index + 1, allNum, com);
- }
- }
- }
算法大部分都是相同的, 但是直接直接使用 String 连接一个 String, 这个做法其实和 new String()是一样的创建了一个新的 String, 和我们的排列组合里面的 new ArrayList<>(temp)这段代码一样, 虽然最终结果没错, 但是却丧失了回溯算法的本质和优势, 浪费了空间一行之差
4.N 皇后问题
这一篇的最后一个问题, 当然非 N 皇后问题莫属, 题目太经典, 我就不浪费篇幅再写一次算法了我这次就着重分析一下这个怎么把这个问题抽象成回溯问题怎么把这个问题模型化, 通俗点说, 怎么把这个问题和排列组合问题找到相同的地方, 方便大家理解
我们每一次在棋盘上放棋子, 其实就是从原集合, 往答案集合中加入元素的一个动作和排列组合问题不同的是, 往答案集合里面加入元素这个动作不是每次都是合法的, 而排列组合是无论怎么加都对
举个栗子
u=4191624954,1499040036&fm=27&gp=0.jpg
在放置第五个棋子的时候, 我们在遍历的过程中需要判断第五个可以合法的放置在哪个位置, 第一行? 不行, 因为第一个棋子也在第一行第二第三第四同理都通不过我们的检查所以在 for 循环中要对之前已经放置的棋子做比较, 看看能不能放置到我们想放置的位置, 如果不行, 那么我们需要回退到上一层
所以 N 皇后问题最后的难点就在于, 怎么表示放置棋子的位置? 怎么做所谓的合法检查? 这些大家可以自己思考一下再用 java 实现一下
当我以前在复习 N 皇后问题的时候, 我有那么一刹那和排列组合问题做了个比较, 顿时恍然大悟原来原理是相同的
这次的回溯算法的分析就到此位置, 下一次我会做一个更全面的深度优先的算法分析
祝大家新年快乐!!
u=3534538955,3983762870&fm=27&gp=0.jpg
来源: http://www.jianshu.com/p/d48ed65b7a3a