什么是回溯法 （Backtracking）？

Answer 1

找到所有选择，走不通则回溯

假定问题的解是一个向量(a1,a2,a3,...,an)，其中的每个元素ai都是问题的一个元素

步骤：

建立一个问题的部分解v=(a1,a2,...,ak)

若这个部分解是可行解，则继续，若不是可行解，删除ak，加入ak情况的另一种可能

若ak的可能已经遍历完，回溯并寻找ak-1的下一个可能

 

算法改进：搜索剪枝

剪枝（pruning）可以帮助我们减少搜索空间，更快的找到解

剪枝的思想就是就是通过某种判断，避免一些不必要的遍历过程，就是如果发现此分支不可能找到最优解，就立刻回溯

剪枝的策略需要具体问题具体分析，这里不细讲

回溯法框架：

递归法

Backtrack(k,X[1...K-1])
    if(k>n) output(X[1...N])
    else
        for each element x in S(k):
               if(constraint(x,X[1...k-1]))
                    X[k]=x
                    backtrack(k+1,X[1...k])

迭代法

IterativeBacktrack()
    k=1
    while k>0
        while set S(k) is not empty
            get a new element x from set S(k)
            if(constraint(x,X[1,k-1]))
                X[k]=x
                if(solution(X)) output(X)
                else k++