Exhaustive Search and Backtracking

Exhaustive Search -穷举搜索

穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从众找出那些符合要求的候选解作为问题的解。

递归格式

Sample

Solution

自相似 : 对应digits下的每个数都是进制数码与上一级digits的各结果数拼接的结果 (就怎么suo呢，见下例digits=3的结果，是不是0,1与digits=2的结果全连接的结果)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
 //Lecture8 Exhaustive Search 2

void binaryAllSearchHelper (int digits,string str) {

    if (digits==0) {
        cout << str << endl;
    } else {
        binaryAllSearchHelper(digits-1,str+"0");
        binaryAllSearchHelper(digits-1,str+"1");
    }

}

void binaryAllSearch (int digits) {
    binaryAllSearchHelper(digits,"");
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
 //Lecture8 Exhaustive Search 2
 
 void binaryAllSearchHelper (int digits,string str) {

    if (digits==0) {
        cout << str << endl;
    } else {

        for(int i=0;i<10;i++) {
        binaryAllSearchHelper(digits-1,str+integerToString(i));
        }
    }

}

void binaryAllSearch (int digits) {
    binaryAllSearchHelper(digits,"");
}

决策树

BackTracking

回溯格式

Sample

Solution

与上面类似，仍然需要将每次骰子的结果进行全连接，但是由于使用vector容器作追踪，因此每次add后同一级其他全连接受影响，因此每个点连接完成后，需要弹出尾部元素。 —回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//Lecture8 BackTracking Dice

void diceSumHelper(int dice, int desierSum, Vector<int>& chose) {
//    cout << recursionIndent() << "dicesum(" << dice << ", "<<desierSum << ", "<< chose << ")" << endl;
    if(dice==0){
        if(desierSum == 0) {
            cout << chose << endl;
        }
    } else {
        for(int i=1;i<=6;i++) {
            chose.add(i);
            diceSumHelper(dice-1,desierSum-i,chose);
            chose.removeBack();
        }
    }
}

void diceSum(int dice, int desierSum) {
    Vector <int> v;
    diceSumHelper(dice,desierSum,v);
}