回溯法

算法

梗概

• 注重状态的搜索
• 穷举出多个解
  • 基于当前状态，有多个可能的解
  • 当前状态加上其中一个解等于下一个状态
  • 回溯法需要在当前穷举完毕时回溯到之间的某个状态，去穷举另外的一个解分支
• 对当前节点判断是否符合搜索条件

表现形式

• 通常需要使用到递归
  • 将状态传入递归函数
    • 通常是搜索路径
  • 记录找到的其中一个解，有以下两种方式：
    • 操作递归函数中共享的变量
    • 递归函数返回该分支递归搜索的结果
      • 通常需要满足最优子结构
• 通常伴随着剪枝操作

适用范围

从解空间搜索解的算法

举例

• child::n数组合

旅行售货员问题

深度搜索完一个分支之后, 记录下这个分支的价值
深度搜索下一个分支的时候, 时刻判断当前分支是否低于之前记录的分支价值, 直接舍弃当前分支, 以节省时间

n皇后问题

树节点路径

interface TREE_NODE {
    id: number,
    value: number,
    children: TREE_NODE[]
}
  
/**
 * Get all paths from root to a node with target value, and the path should not contain the node with expV
 */
function getPath(root: TREE_NODE, targetV: number, expV: number): number[][] {
    let rst: number[][] = []
    if (root.value === expV) { // 剪枝操作
        return rst
    }
    if (root.value === targetV) {
        rst.push([root.id])
        return rst
    }
    /* 深度遍历 */
    for (const child of root.children) {
        let subPath = getPath(child, targetV, expV)//递归回溯
        if (subPath.length) {
            for (const path of subPath) {
                rst.push([root.id, ...path])
            }
        }
    }
    return rst
}