版本 05e55c282cea7a444df2040a6b741dab7e106b58

Backtracking

Week 5L Backtracking

Week 5L 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);
        }
    }
}

範例code

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

圖片:

code:

#include<cstring>
#include<cstdio>
int number[5];
int answer[5];
void backtracking(int ans_index,int num_index
{
    if(ans_index==3)
    {
        for(int i=0;i<ans_index;i++)
            printf("%d ",answer[i]);
        printf("\n");
    }
    else
    {
        answer[ans_index]=number[num_index];
        backtracking(ans_index+1,num_index+1);
        if((5-num_index-1)>=(3-ans_index))
            backtracking(ans_index,num_index+1);
    }
    return;
}
int main(void)
{
    for(int i=0;i<5;i++)
        number[i]=i+1;
    backtracking(0,0);
    return 0;
}