“`” 找到所有选择，走不通则回溯
假定问题的解是一个向量(a1,a2,a3,…,an)，其中的每个元素ai都是问题的一个元素
步骤：
建立一个问题的部分解v=(a1,a2,…,ak)
若这个部分解是可行解，则继续，若不是可行解，删除ak，加入ak情况的另一种可能
若ak的可能已经遍历完，回溯并寻找ak-1的下一个可能
<strong>算法改进：搜索剪枝</strong>
<strong>剪枝</strong>（pruning）可以帮助我们减少搜索空间，更快的找到解
剪枝的思想就是就是通过某种判断，避免一些不必要的遍历过程，就是如果发现此分支不可能找到最优解，就立刻回溯
剪枝的策略需要具体问题具体分析，这里不细讲
回溯法框架：
递归法
<pre><code>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])</code></pre>
迭代法
<pre><code>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++</code></pre>
<pre><code> "“`
Was this helpful?
0 /
0