回溯算法高效需要注意这两点

回溯算法高效需要注意这两点

坚持原创，写好每一篇文章

算法的知识点

你学习算法的时候有没有感觉很难，为什么学习算法这么难，而你学软件开发的时候感觉很简答很有意思呢？算法不仅仅是算法本身，它包含了数学知识，包含了数据结构，像一些数组，栈，队列，矩阵，树，图等内容，包含了逻辑思维，可以说算法是计算机与数学之间联系起来的桥梁，我们计算机人士最重要的就是具有解决问题的能力，而算法正是让我们提升解决问题能力的重要手段

算法复杂度

算法复杂度从小到大排序

我们在进行编写算法的时候要考虑到算法的复杂度，不能让算法产生爆炸增量函数，向指数型的2的n次方，随着n的增大，复杂度就会呈现指数型增长，很有可能导致电脑死机。

回溯算法

下面说一下回溯算法，回溯是什么意思呢，回首往事，回顾的意思，回溯法也叫试探法，退一步海阔天空，它的基本思想是从一个初始点出发，从头尝试到达终点的路，如果不理想或走不通就退一步再选其他路尝试。就是遇事不慌，大不了换一条路。

要使用回溯算法，回溯算法中的几个特点需要你了解。

第一个就是解空间。什么是解空间，所谓解空间就是问题的所有的解组成的一个空间，这个空间越大越有利于我们找到最优解，所以我们需要设置一些约束条件来让空间变小，从而在回溯的时候尽快找到最优解。这些约束条件我们称为剪枝函数或者隐约束。

对回溯算法做了这么多介绍，很多人可能觉得还是很抽象，我们不妨举个例子，直观性教学一下。

算法题目来源

网络

算法题目描述

去买东西，每个人一个购物车，购物车容量都是一样的，谁装的东西最多谁赢，谁装的东西最值钱谁赢。

做题思路

我们怎么求解这个问题呢，这就是典型的零一背包问题，首先我们找到解空间，假设有n个物品，设置x是商品，解空间就是{x1,x2,…,xn},x的值可以是0也可以是1，0表示没有放进购物车，1表示放进了购物车，解空间我们就找到了，接下来找剪枝函数。

我们知道购物车的容量是有限的，我们不能超过购物车容量，这就形成了一个约束条件：所有商品容量之和不大于购物车总容量。 这只是其中一个约束条件，还有别的约束，你找到的约束条件越多，解空间也就会变得越小。

相关算法题型题目总结

这在这类题目的关键也就是我们上面说的两点，找到解空间，然后找到剪枝函数，解空间的大小和剪枝函数决定我们回溯算法是否高效。

总结

这篇文章我们简单讲解了回溯算法，了解到回溯算法需要让我们找到解空间和剪枝函数，这有利于回溯算法的提高。