版本 dbb201e9c63b640c03b833f628e77bd371570af3
Changes from dbb201e9c63b640c03b833f628e77bd371570af3 to current
Week 5: Backtracking
================
介紹
------------------------------
Backtracking是一種窮舉搜尋的演算法，目標是找尋所有可能的答案，可分為兩個概念，分別是enumerate(枚舉)與pruning(剪枝)
(1)enumerate(枚舉):每一步列出所有可能的下一步一一測試
(2)pruning(剪枝):遇到不符合條件的下一步便省略，不再繼續枚舉
何時使用
------------------------------
1.需要搜尋所有可能答案的時候
2.需要暴力破解的時候
如何使用
------------------------------
1.列舉所有可能下一步的答案
2.設立答案的停損點
3.如果需要的話，把關注的解儲存下來
4.遇到不可能的條件不再繼續搜尋或過濾不可能的條件
pseudo code
------------------------------
```c++
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個數並由小到大排列
圖片:
: <br />
程式碼:
```c++
#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;
}
```
