5. 回溯与分支

What is backtracking algorithm?

Backtraking is a general algorithm for finding all (or some) solutions to some computational problems, notably(尤其是) constraint satisfaction problems, that incrementally builds candidates (申请者)to the solutions, and abandons each partial candidate("backtracks") as soon as it determines that the candidate cannot passibly be completed to a valid solution.
This is a search algorithm in graph and tree.

Feature

1. 可求搜索问题和优化问题，搜索问题可定义如下。
   一个搜索问题π有是立即Dπ，低于π中的任务实例I，有一个有穷的解集合Sπ[I]。
   如果存在算法A，对于任何实例I属于Dπ，A都停止，并且如果Sπ[I] = 空集，则回答无解，否则给出Sπ[I]中的一个解，那么称A解搜索问题π
2. 搜索空间是一棵树，每个节点对饮了部分向量，瞒住约束条件的叶子节点对应了相应的解，但是不一定是最优解。
3. 搜索过程一般采用深度优先，广度优先，函数有限或者深宽结合等策略，去裁剪分支，以便于优化。
4. 判断条件：满足约束条件则可以扩张解向量，不满足约束条件回溯到该节点的父节点。

When 什么时候做

要是回溯算法得到正确的应用，必须满足多米诺性质

多米诺性质

已有x1, x2...xk的k维向量
对于P来说x1, x2...xk满足条件，那么就可以推断出x1, x2...xk+1也满足条件。（十分形象的比喻）
反之，如果不满足条件，那么x1, x2...xk+1也不满足条件

How 怎样做

1. 定义搜索问题的解向量和每个分量的取值范围。
2. 确定子结点的排列规则。
3. 判断是否满足多米诺性质。
4. 确定使用的搜索策略。
5. 确定每个节点能够分支的约束条件。
6. 确定存储搜索路径的数据结构。

Sample

reback(k)
if  k > n then < x1, x2,...,xn>是解
else while Sk != null
    xk = Sk 中的最小值
    Sk = Sk - {xk}
    计算Sk+1
    reback(k+1)
    
reBacktraking(n)
for i to n
    计算xk
S1 = x1
reback(1)

backtraking(n)
k = 1
计算sk
while sk != null
    xk = Sk的最小值
    Sk = Sk - xk
    if k < n
        k++
        计算Sk
    else 
        <x1,x2,...xn>就是解

Why 为什么这么做

在高维度的计算中，夹杂这大量数据。我们通过分支优化可以大大减少数据计算量。分支界限优化就要确定相应的代价函数来优化。