和贪心算法相反的是

—回溯算法

回溯算法是一种通过不断"回溯"来寻找问题解决方案的方法，也可以说是一种"试错"的探索式算法。它搜索所有可能的解决方案，直到找到符合要求的方案或者遍历了所有可能的方案并未找到解决方案。

与贪心算法不同，贪心算法每次只考虑最优解，并相信当前最优解一定可以转化为全局最优解。然而，在某些情况下，贪心算法无法找到最优解，而回溯算法则能够找到所有解或者最优解。

一、回溯算法的特点

1. 深度遍历

回溯算法是一种基于深度遍历的算法。它先走一条路，如果发现此路不通或达不到最优解，就返回上一个岔路口做出另一选择继续走下去，直到达到目标或者无路可走。

2. 回溯

回溯算法的核心在于回溯。在搜索的过程中，当走到某一个位置，发现无法继续，就会退回到上一个位置，重新选择一条路继续搜索，直到找到最终的结果。

3. 搜索所有解或最优解

回溯算法会搜索所有可能的解决方案，或者搜索到一个最优解即结束。相对于贪心算法，回溯算法可能会更加耗时，但也能够找到更优的解决方案。

二、回溯算法的应用

回溯算法应用非常广泛，其中包含了很多经典问题，比如全排列问题、N皇后问题、0/1背包问题等等。这些问题都可以使用回溯算法来解决。

例如，N皇后问题就是一个无论如何都无法使用贪心算法解决的经典问题。而回溯算法能够搜索所有解空间，找到所有合法的解决方案。

三、回溯算法的优化

虽然回溯算法能够找到所有解或最优解，但是在实际应用中，搜索空间可能非常巨大，导致算法执行时间过长。因此，需要优化回溯算法。

1. 剪枝

通过剪枝，可以忽略掉一些不可能为最优解的方案，从而减少搜索空间，提高退回上一个岔路口时的速度。剪枝可以大大降低回溯算法的时间复杂度。

2. 启发式搜索

启发式搜索是一种利用启发式信息来指导搜索的算法。在回溯算法中，可以使用启发式搜索来通过先验知识来减少搜索空间。

四、总结

回溯算法和贪心算法都是搜索算法中的重要方法，各自有不同的特点和适用范围，需要针对具体问题来选择适合的解决方法。回溯算法通过枚举所有情况，可以找到所有解或最优解，但是时间复杂度较高。在实际应用中，可以通过剪枝和启发式搜索来优化回溯算法。