algorithm - 在编程术语中，什么是回溯解决方案？

Question

关于回溯解决方案的真正含义，我有几个问题。

1. 比方说，你在当前状态下有 n 个选项，进行回溯解决方案基本上意味着你尝试所有这些状态，然后做对于子问题也是如此(你可能有 n-1 个状态解决方案)，依此类推，然后返回最佳解决方案第 (n-1) 帧到第 n 帧。

参见下面的问题:给定一根长度为 n 的绳索，如何将绳索切成长度为 n[0]、n[1]、...、n[m-1] 的 m 部分，在为了得到 n[0]n[1] 的最大乘积 ... *n[m-1] 所以一根长度的绳子会被切成 2*3*3 到得到 18 的产品。,

public class RopeCuttingMaxProduct
{
    public static void main(String[] args)
    {
        System.out.println(fun(8));
    }

    static int fun(int n)
    {
        if(n == 1)
            return 1;

        int totalret = 0;
        for(int i = 1;i<n;i++)
        {
            /*At every frame, two options 1.to cut 2.to not cut
             *  1.If cutting, multiple ways to cut : Remember i+(n-i) == n
             *  2.If not cutting, just return n
             */
            /* Explore all possible solutions, from all possible paths 
             * and the subpaths that these lead to,
             * and their subpaths*/
            int reti = max(fun(n-i)*i,n);

            if(reti > totalret)
                totalret = reti;
        }
        return totalret;
    }

    static int max(int a, int b)
    {
        return a>b?a:b;
    }
}

1. 那么，所有回溯解决方案的时间复杂度都是指数级的吗？
2. 这听起来很像递归，我无法想象像这样通过任何其他递归实现。你能给我一个无需递归实现的回溯解决方案示例
3. 它与蛮力有何不同。这个问题的暴力解法是尝试所有可能的组合方式加起来达到n。我发现上述回溯解决方案的作用几乎相同。

Answer 1

如果你认为你的算法所采用的路径是决策树的遍历，那么解(如果存在)就是树的某个叶节点，或者如果有多个解，则有多个叶节点代表他们。

回溯只是意味着算法在某个时刻检测到在它当前所在的树的分支中找不到解决方案，然后向上移动一个或多个节点以继续其他分支。

这并不意味着所有的节点都需要被访问。例如，如果算法在实际到达叶子之前检测到当前分支不值得继续，那么它将避免访问该分支中的所有剩余节点。

因此，并非所有回溯算法都是蛮力算法。

这样的算法可以避免多少不必要的工作是非常具体的问题，不能笼统地回答。一般的答案是回溯不一定基于详尽的搜索/试验。