Backtracking 第二讲

还记得上一节所讲的回溯法投色子吗?

浪费了很多算力,产生了很多不必要的结果

那我们应该怎样改进呢?

优化

剪枝

**原理:**如果在某一时刻我们确信从此开始将无法继续,或许我会立刻撤回并且停止.

所以我们只需要在之前的选择中做出一些限制,使得之后的选择更加有利.

else if (desiredSum >= dice * 1 && desiredSum <= dice * 6) {.....}

这就被称之为"剪枝""!

---

回溯法的整体策略就是:

• 若面临选择,则处理其中一个选择,若处理后仍有选择,则回到之前的选择点继续处理,直到所有选择都处理完毕.
• 你进行选择,然后谈起其后每一种可能的发展,随后再撤销选择.
• 选择,探索,撤销选择每一种可能性

例子

问题: Permute Vector(排列向量)

• 编写一个名为 permute 的函数，该函数接受一个字符串的向量作为参数，并输出该向量中所有可能的字符串重排列。输出的排列顺序可以是任意的。

**示例：**如果 v 包含 { "a", "b", "c", "d" }，你的函数应输出这些排列：

思路:

• 我们可以先将字符串向量中的每个字符串看作是一个字符,然后将其排列组合成新的字符串.
• 我们可以用一个循环来遍历向量中的每个字符串,然后将其与其他字符串组合成新的字符串,并将其加入到结果集中.
• 我们可以用一个递归函数来实现这个过程.

void permuteHelper(Vector<string>& v, Vector<string>& chosen){
    if (v.isEmpty()){
        cout << chosen << endl;
    }else{
        for (int i = 0; i < v.size(); i++)
        {
            string s = v[i];
            chosen.add(v[i]);
            v.remove(i);

            permuteHelper(v,chosen);

            chosen.remove(chosen.size()-1);
            v.insert(i,s);

        }
    }
}

void permute(Vector<string>& v)
{
    Vector<string> chosen;
    permuteHelper(v, chosen);

}

这其实也是一种树状结构,我们可以用递归来实现.

回退出去以后进入 for 的下一个遍历,我们将当前的字符串加入到 chosen 中,然后将其从 v 中移除,然后递归调用 permuteHelper,直到 v 为空,此时输出 chosen.

然后我们将当前的字符串从 chosen 中移除,然后将其重新插入到 v 的相应位置,继续下一个遍历.

这样我们就实现了排列组合的过程.