回溯算法🐸
回溯算法（backtracking algorithm）是一种通过穷举来解决问题的方法，它的核心思想是从一个初始状态出发，暴力搜索所有可能的解决方案，当遇到正确的解则将其记录，直到找到解或者尝试了所有可能的选择都无法找到解为止
主体思想框架：尝试、回退、剪枝*
代码框架：
/*回溯算法框架*/
/*
state代表了探索问题过程中的可能解，choice是接下来面临的选择，例如二叉树的左子树还是右子树
*/
void backtrack(State * state,vector<Choice *> &choices,vector<State *> &res){
//判断是否为解
if (isSolution(state)) {
//记录解
recordSolution(state, res);
//不再继续探索(可能)
return ;
}
//遍历所有选择
for(Choice choice : choices) {
//剪枝：判断语句是否合法
if(isValid(state,choice)){
//如果合法
//尝试：做出选择，更新状态
makeChoice(state,choice);//将choice记录在state中
backtrack(state, choices, res);
//回退：撤销选择，恢复到之前的状态
undoChoice(state,choice);
}
}
}
常用术语
| 名词 | 定义 | 例题三 |
|---|---|---|
| 解（solution） | 解是满足问题特定条件的答案，可能有一个或多个 | 根节点到节点 7 的满足约束条件的所有路径 |
| 约束条件（constraint） | 约束条件是问题中限制解的可行性的条件，通常用于剪枝 | 路径中不包含节点 3 |
| 状态（state） | 状态表示问题在某一时刻的情况，包括已经做出的选择 | 当前已访问的节点路径，即 path 节点列表 |
| 尝试（attempt） | 尝试是根据可用选择来探索解空间的过程，包括做出选择，更新状态，检查是否为解 | 递归访问左（右）子节点，将节点添加进 path ，判断节点的值是否为 7 |
| 回退（backtracking） | 回退指遇到不满足约束条件的状态时，撤销前面做出的选择，回到上一个状态 | 当越过叶节点、结束节点访问、遇到值为 3 的节点时终止搜索，函数返回 |
| 剪枝（pruning） | 剪枝是根据问题特性和约束条件避免无意义的搜索路径的方法，可提高搜索效率 | 当遇到值为 3 的节点时，则不再继续搜索 |
优点与局限性
优点是可以找到所有可能的方案 然而，在处理大规模问题或者复杂问题时，运行效率可能难以接受 优化的方法：剪枝、启发式搜索
