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

アルゴリズムがたどるパスが決定木のトラバーサルであると考える場合、解が存在する場合はツリーのリーフ ノードであり、複数の解がある場合はそれらを表す複数のリーフ ノードがあります。

バックトラックとは、ある時点でアルゴリズムが現在のツリーのブランチで解が見つからないことを検出し、1 つまたは複数のノードに戻って他のブランチを続行することを意味します。

これは、すべてのノードにアクセスする必要があるという意味ではありません。たとえば、現在のブランチが実際にリーフに到達する前に追跡する価値がないことをアルゴリズムが検出した場合、そのブランチの残りのすべてのノードにアクセスすることを回避します。

したがって、すべてのバックトラッキング アルゴリズムがブルート フォースであるとは限りません。

そのようなアルゴリズムがどれだけの不必要な作業を回避できるかは、問題に非常に固有のものであり、一般的に答えることはできません。一般的な答えは、バックトラックは必ずしも徹底的な検索/試行に基づいていないということです.

于 2015-10-24T13:27:45.053 に答える