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. 可求搜索問題和優(yōu)化問題，搜索問題可定義如下。
   一個搜索問題π有是立即Dπ，低于π中的任務(wù)實例I，有一個有窮的解集合Sπ[I]。
   如果存在算法A，對于任何實例I屬于Dπ，A都停止，并且如果Sπ[I] = 空集，則回答無解，否則給出Sπ[I]中的一個解，那么稱A解搜索問題π
2. 搜索空間是一棵樹，每個節(jié)點對飲了部分向量，瞞住約束條件的葉子節(jié)點對應(yīng)了相應(yīng)的解，但是不一定是最優(yōu)解。
3. 搜索過程一般采用深度優(yōu)先，廣度優(yōu)先，函數(shù)有限或者深寬結(jié)合等策略，去裁剪分支，以便于優(yōu)化。
4. 判斷條件：滿足約束條件則可以擴張解向量，不滿足約束條件回溯到該節(jié)點的父節(jié)點。

When 什么時候做

要是回溯算法得到正確的應(yīng)用，必須滿足多米諾性質(zhì)

多米諾性質(zhì)

已有x1, x2...xk的k維向量
對于P來說x1, x2...xk滿足條件，那么就可以推斷出x1, x2...xk+1也滿足條件。（十分形象的比喻）
反之，如果不滿足條件，那么x1, x2...xk+1也不滿足條件

How 怎樣做

1. 定義搜索問題的解向量和每個分量的取值范圍。
2. 確定子結(jié)點的排列規(guī)則。
3. 判斷是否滿足多米諾性質(zhì)。
4. 確定使用的搜索策略。
5. 確定每個節(jié)點能夠分支的約束條件。
6. 確定存儲搜索路徑的數(shù)據(jù)結(jié)構(gòu)。

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 為什么這么做

在高維度的計算中，夾雜這大量數(shù)據(jù)。我們通過分支優(yōu)化可以大大減少數(shù)據(jù)計算量。分支界限優(yōu)化就要確定相應(yīng)的代價函數(shù)來優(yōu)化。