算法之回溯算法

概述

这篇文章介绍了回溯算法的概念、使用场景，并给出了一些示例代码。

概念

回溯算法的本质是深度优先遍历，不断从节点中尝试搜索找到问题的解，如果在搜索过程中发现不满足求解条件，则 “回溯” 返回，尝试其他路径继续搜索解决。这种走不通就后退尝试其他路径的方法就是回溯法，许多复杂的，规模较大的问题都可以使用回溯法，所以回溯法有 “通用解题方法” 的美称。

算法案例

• 八皇后问题（Eight Queens）：是回溯算法的典型案例，问题为在 8*8 的国际象棋上摆放 8 个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
• 0-1 背包问题（Knapsack problem）：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使物品的总价格最高。
• 数独问题：在 9*9 的矩阵中，每一行，每一列，每个九宫格都是 1-9 这九个数字且不能重复。

代码示例

参考资料

• 回溯算法 - 路漫漫我不畏 - 博客园: https://www.cnblogs.com/huwt/p/10749234.html
• 小白带你学–回溯算法 - 简书: https://www.jianshu.com/p/dd3c3f3e84c0

总结

回溯法是深度优先搜索，需要进行全局搜索，复杂度相对较高。回溯法在遇到得不出解的时候会回溯，而不像暴力枚举法遍历所有项，因此效率有所提升。