回溯算法总结点睛 |
您所在的位置：网站首页 › 选择排序递归算法的优缺点 › 回溯算法总结点睛 |
回溯算法总结点睛
|
一、基本概念
1、什么是回溯法？
又称回溯搜索法，说白了就是一种搜索方式。 其实回溯是递归的副产品，只要有递归就会有回溯。 回溯函数也可以称之为递归函数。 2、回溯法的效率回溯法本质是穷举，因此并不高效 可以通过一些剪枝的操作稍微提高一些效率，但仍是比较低效的算法 3、回溯法解决的问题经常用来解决以下 5 种问题： * 1）组合问题：**不强调**元素的顺序，N个数里按照一定的规则找出K个数的集合 * 2）排列问题：**强调**元素的顺序，N个数按一定的规则全排列，求有多少排列方式 * 3）切割问题：一个字符串按照一定规则有几种切割方式 * 4）子集问题：一个N个数的集合中有多少个符合条件的子集 * 5）棋盘问题：N皇后，解数独 等等。 4、如何理解回溯法所有回溯法解决的问题，都可以抽象为树形结构。 因为递归法解决的都是在集合中 递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。 递归就要有终止条件，所以必然是一棵高度有限的N叉树。 5、回溯法模板 void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { 处理节点; backtracking(路径，选择列表); // 递归，也就是到下一层咯 回溯，撤销处理结果 } }回溯函数模板返回值以及参数 名字通常记为 backtracking返回值一般为void参数不像二叉树那样一次性基本就可以确定，因此一般是先写逻辑，然后需要什么参数就填什么参数回溯函数终止条件 什么时候达到了终止条件，树中就可以看出，一般来说搜到了叶子节点了，也就是找到了满足条件的一条答案，把这个答案存起来，并结束本层递归 if (终止条件) { 存放结果; return; }回溯搜索的遍历过程 回溯 ： 在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成了树的深度 不要想的太复杂了 ，其实嘛~ 可以剪枝的地方就是在递归中每一层的for循环所选择的起始位置，所以 如果 for 循环选择的起始位置之后的元素个数 已经不足 我们需要的元素的个数，那么就没必要搜索啦啦啦~~~，也就是控制一下 for 循环的遍历终止条件 * 已经选择的元素的个数 **path.size()** * 还需要的元素个数 **k - path.size()** * 在集合n中，从 **n - (k - path.size()) + 1** 位置开始 往后的遍历均为无效遍历，因此就剪掉他 * 剪枝后的最终版本 **for(int i = 1; i |
【本文地址】
今日新闻 |
推荐新闻 |