回溯算法高效需要注意这两点
回溯算法高效需要注意这两点
坚持原创,写好每一篇文章
算法的知识点
你学习算法的时候有没有感觉很难,为什么学习算法这么难,而你学软件开发的时候感觉很简答很有意思呢?算法不仅仅是算法本身,它包含了数学知识,包含了数据结构,像一些数组,栈,队列,矩阵,树,图等内容,包含了逻辑思维,可以说算法是计算机与数学之间联系起来的桥梁,我们计算机人士最重要的就是具有解决问题的能力,而算法正是让我们提升解决问题能力的重要手段
算法复杂度
算法复杂度从小到大排序
我们在进行编写算法的时候要考虑到算法的复杂度,不能让算法产生爆炸增量函数,向指数型的2的n次方,随着n的增大,复杂度就会呈现指数型增长,很有可能导致电脑死机。
回溯算法
下面说一下回溯算法,回溯是什么意思呢,回首往事,回顾的意思,回溯法也叫试探法,退一步海阔天空,它的基本思想是从一个初始点出发,从头尝试到达终点的路,如果不理想或走不通就退一步再选其他路尝试。就是遇事不慌,大不了换一条路。
要使用回溯算法,回溯算法中的几个特点需要你了解。
第一个就是解空间。什么是解空间,所谓解空间就是问题的所有的解组成的一个空间,这个空间越大越有利于我们找到最优解,所以我们需要设置一些约束条件来让空间变小,从而在回溯的时候尽快找到最优解。这些约束条件我们称为剪枝函数或者隐约束。
对回溯算法做了这么多介绍,很多人可能觉得还是很抽象,我们不妨举个例子,直观性教学一下。
算法题目来源
网络
算法题目描述
去买东西,每个人一个购物车,购物车容量都是一样的,谁装的东西最多谁赢,谁装的东西最值钱谁赢。
做题思路
我们怎么求解这个问题呢,这就是典型的零一背包问题,首先我们找到解空间,假设有n个物品,设置x是商品,解空间就是{x1,x2,…,xn},x的值可以是0也可以是1,0表示没有放进购物车,1表示放进了购物车,解空间我们就找到了,接下来找剪枝函数。
我们知道购物车的容量是有限的,我们不能超过购物车容量,这就形成了一个约束条件:所有商品容量之和不大于购物车总容量。 这只是其中一个约束条件,还有别的约束,你找到的约束条件越多,解空间也就会变得越小。
相关算法题型题目总结
这在这类题目的关键也就是我们上面说的两点,找到解空间,然后找到剪枝函数,解空间的大小和剪枝函数决定我们回溯算法是否高效。
总结
这篇文章我们简单讲解了回溯算法,了解到回溯算法需要让我们找到解空间和剪枝函数,这有利于回溯算法的提高。
相关文章
- 数据分析 VS 算法模型,如何高效分工合作?
- go实现常见排序算法
- 【说站】java泛型算法如何实现
- 【论文阅读笔记】Myers的O(ND)时间复杂度的高效的diff算法
- 京东商品接口加解密算法解析
- 【算法基础】数组反转
- 用对数器测试算法是否正确
- 【算法竞赛】Codeforces Round #841 (Div. 2) C, E
- 【视频】Copula算法原理和R语言股市收益率相依性可视化分析|附代码数据
- 监控软件中如何利用巴伐利亚算法实现高效使用
- 算法Linux CFS调度算法——简单高效的任务调度方案(linuxcfs调度)
- 利用Oracle实现高效递归算法(oracle递归算法)
- 利用Redis缓存实现高效算法处理(redis缓存算法)
- Oracle中玩转运算函数,轻松完成高效算法(oracle中运算函数)
- 哨兵Redis算法实现稳定高效数据访问(哨兵redis算法)
- Redis集群实现哈希算法的高效方案(redis集群哈希算法)
- 实践证明Oracle MRU算法的高效解决方案(oracle mru算法)
- php数据结构与算法(PHP描述)查找与二分法查找
- 基于稀疏图上的Johnson算法的详解
- 一种求正整数幂的高效算法详解
- JavaScript实现穷举排列(permutation)算法谜题解答
- PHP简单选择排序算法实例