回溯算法

Posted on | In |

回溯算法

  1. 概念：回溯算法实际上是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现不满足求解条件时，就回溯返回，尝试别的路径。许多复杂的，规模较大的问题都可以使用回溯法。
  2. 基本思想：在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根节点触发深度探索解空间树。当搜索到某一节点时，要先判断该节点是否包含问题的解，如果包含，就从该节点触发极速探索；如果不包含，则逐层向其祖先节点回溯。
  3. 使用回溯法求解所有问题，要回溯到根，且根节点的所有可行子树都要被搜索遍历才结束。使用回溯法求解一个问题，只要搜索到问题的一个解就可以结束。

回溯算法框架：

设问题的解是一个n维向量(a1, a2, …, an)，约束条件是ai(i=1,2,3,…,n)之间满足某种条件，即为f(ai)。

  1. 非递归框架：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    int a[n], i;
    i = 1;
    while(i>0(有路可走)  and  (未达目标)){ //还未回溯到头
        if(i > n){
            搜索到一个解，输出；
        }
        else {
            a[i]第一个可能的值；
            while(a[i]在不满足约束条件且在搜索空间内){
                a[i]下一个可能的值；
            }
            if(a[i]在搜索空间内){
                标识占用资源；
                i = i+1； //扩展下一节点
            }
            else{
                清理所占空间状态； //回溯
                i=i-1;
            }
        }
    }

  2. 递归框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int a[n];
i=1;
try(int i){
    if(i > n) 输出结果；
    else{
        for(j = 下界; j<=上界;j=j+1){
            if(fun(j)){
                a[i] = j;
                ...
                try(i+1);
                清理工作;
            }
        }
    }
}

LeetCode题解

784. Letter Case Permutation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<string> letterCasePermutation(string S) {
        vector<string> ans;
        backTracking(S, ans, 0);
        return ans;
    }
    
    void backTracking(string& s, vector<string>& ans, int i){
        ans.push_back(s);
        while(i < s.size()){
            if(!isdigit(s[i])) { //is char
                s[i] = toggle(s[i]); //转变大小写
                backTracking(s, ans, i+1); //增加一个解空间子树
                s[i] = toggle(s[i]); //返回原来子树
            }
            i++;
        }
    }
    
    char toggle(char c){
        return isupper(c)? tolower(c) : toupper(c);
    }
};