回溯法算法架構

回溯法：有通用解題法 之稱，可以系統的搜尋一個問題的所有解和任一解，是一個既帶有系統性，又帶有跳躍性的搜尋算法。

算法基本思想：

　　确定解空間後

　　從開始節點出發，以深度優先的方式搜尋整個解空間。

　　如果目前擴充結點不能再向縱深方向移動，目前節點為死節點。此時，應該往回移動至最近的一個活節點處。，并是這個或節點成為目前節點的擴充結點。

提高算法方式（剪枝函數）：

　　1 用限制函數在擴充結點出剪去不滿足限制的子樹

　　2 用限界函數剪去得不到最優解的子樹。

回溯法解題步驟：

　　1 定義問題的解空間

　　2 确定易于搜尋的解空間結構

　　3 以深度優先方式搜尋解空間，并在搜尋過程中用剪枝函數避免無效搜尋。

遞歸回溯：

void Backtrack(int t)
{
    if(t>n)
        Output(x);
    else
        for(int i=f(n,t);i<=(g,t);i++)
        {
            x[t] = h(i);
            if(Constraint(t) && Bound(t))
                Backtrack(t+1);
        }
}      

子集樹：

當所有的問題是從n個元素的集合S中找出滿足某種性質的子集時，相應的解空間樹稱為子集樹。

僞碼為：

void Backtrack(int t)
{
    if(t>n)
        Output(x);
    else
        for(int i=f(n,t);i<=(g,t);i++)
        {
            x[t] = h(i);
            if(Constraint(t) && Bound(t))
                Backtrack(t+1);
        }
}      

排列樹：

當所給的問題是确定n個元素滿足某種性質的排列時，相應的解空間樹稱為排列數。

void Backtrack(int t)
{
    if(t>n)
        Output(x);
    else
        for(int i=f(n,t);i<=(g,t);i++)
        {
            Swap(x[t],x[i]);
            if(Constraint(t) && Bound(t))
            {
                Backtrack(t+1);
            }
            Swap(x[t],x[i]);
        }
}      

作者：xingoo