Backtracking

Week 5: Backtracking

Week 5: Backtracking

介紹

Backtracking是一種窮舉搜尋的演算法，目標是找尋所有可能的答案，可分為兩個概念，分別是enumerate(枚舉)與pruning(剪枝)
(1)enumerate(枚舉):每一步列出所有可能的下一步一一測試
(2)pruning(剪枝):遇到不符合條件的下一步便省略，不再繼續枚舉

何時使用

1.需要搜尋所有可能答案的時候
2.需要暴力破解的時候

如何使用

1.列舉所有可能下一步的答案
2.設立答案的停損點
3.如果需要的話，把關注的解儲存下來
4.遇到不可能的條件不再繼續搜尋或過濾不可能的條件

pseudo code

int solution[MAX_DIMENSION];
void Backtracking(int dimension)
{
    if(solution is well-generated)
    {
        process solution
        return;
    }
    for( x = each value of current dimention )
    {
        if( condition )
        {
            solution[dimension] = x;
            backtracking(dimension+1);
        }
    }
}

範例

題目:選出{1,2,3,4,5}中的3個數並由小到大排列

圖片:

程式碼:

#include<cstring>
#include<cstdio>
int number[5];
int answer[5];
void backtracking(int ans_index,int num_index)
{
    if(ans_index==3)  //2.設立答案的停損點
    {
        for(int i=0;i<ans_index;i++)
            printf("%d ",answer[i]);
        printf("\n");
    }
    else  //1.列舉所有可能下一步的答案
    {
        answer[ans_index]=number[num_index];
        backtracking(ans_index+1,num_index+1);  //選擇該num_index 繼續下一個ans_index
        if((5-num_index-1)>=(3-ans_index))  //檢驗是否可以不選擇num_index(過濾不可能的條件) 
            backtracking(ans_index,num_index+1);  //不選擇num_index 同個ans_index選下一個num_index
    }
    return;
}
int main(void)
{
    for(int i=0;i<5;i++)
        number[i]=i+1;
    backtracking(0,0);
    return 0;
}