算法之回溯算法

概述

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

概念

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

算法案例

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

代码示例

参考资料

总结

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