0

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

  1. 说，你有来自当前状态的 n 个选项，回溯解决方案基本上意味着你尝试所有这些状态，并对子问题做同样的事情（你可能有 n-1 个状态的解决方案），并且依此类推，然后返回从第 (n-1) 帧到第 n 帧的最佳解决方案。

请参阅下面的问题：给定长度为 n 的绳索，如何将绳索切成长度为 n[0]、n[1]、...、n[m-1] 的 m 个部分，以获得最大乘积of n[0] n[1] ... *n[m-1] Soa 长度的绳索将被切割成 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。我发现上述回溯解决方案的作用几乎相同。
4

1 回答 1

2

如果您认为您的算法所采用的路径是对决策树的遍历，那么解决方案（如果存在）是树的某个叶节点，或者如果有多个解决方案，那么就有多个叶节点代表它们。

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

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

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

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

于 2015-10-24T13:27:45.053 回答