回溯=试探=穷举算法

回溯法：试探，从一条路往前走，能进则进，不能则退回上一步，换一条路；

• 穷举问题的通用算法
• 深度优先向下构造，约束函数控制，遍历完毕后无解或输出解后，都回溯

算法

生成一棵代表解空间的树：深度优先探索（深度优先的过程是蕴含回溯的）；递归

• 穷举后筛选：穷举，约束函数剪枝
• 或条件生成：条件加在递归的参数里，当条件完全传递时（仅生成符合条件的下一步），剪枝过程被完全优化掉
• 回溯，试探，穷举一类问题的算法的优化点在于
  1. 传递尽可能多的条件
  2. 优化约束函数：使用更精简数据结构保存现有当前状态，更高效的判断算法

例子

• n皇后问题：位操作算法可非常高效的完全传递条件
• 迷宫问题：非递归实现可用栈。栈是实现回溯的好工具