4

初心者のプログラマーとして、私は最近、Robert Sedgewick /KevinWayneによる「Algorithms-ForthEdition」という本を購入しました。各章の終わりにある演習に本当に感謝しています。しかし、解決策が見つからないために私を夢中にさせている演習が1つあります（非常に単純に見えます）。

n回の試行で正確にk回成功する確率を見つけるこの再帰的アルゴリズムを使用する必要があります。ここで、pは1つのイベントの成功の確率です。与えられたアルゴリズムは、再帰的二項分布フォーラムに基づいています。

public static double binomial(int n, int k, double p) {
    if (n == 0 && k == 0)
        return 1.0;
    else if (n < 0 || k < 0)
        return 0.0;
    return (1 - p) * binomial(n - 1, k, p) + p * binomial(n - 1, k - 1, p);
}

この演習の目的は、計算された値を配列に保存することにより、このアルゴリズムを高速化することです。階乗を見つけるために反復法を使用する二項分布[p（x）= nCr * p ^ k *（1 --p）^（n --k）]を取得する別の方法を使用して、このアルゴリズムをすでにかなり高速にしました。ただし、このコンテキストで配列を使用して実行時間を改善する方法がわかりません。

どんな助けでも大歓迎です！

...そして誰かが尋ねる前に、これは宿題ではありません！

4

3 に答える 3

5

この本は、メモ化と呼ばれる特定のプログラミング手法を教えようとしています。これは、動的プログラミングとして知られる、より広範な手法の一種です。もちろん、実生活では、閉じた形式の解を知っている方がはるかに優れていますが、この演習を解くという文脈ではそうではありません。

とにかく、アイデアは、2D 配列を 4 番目のパラメーターとして渡し、NaN最初に s を入力し、何かを計算する前に、指定されたnとの組み合わせの解決策があるかどうかを確認することです。kある場合は返却してください。存在しない場合は、再帰的に計算し、配列に格納してから返します。

于 2012-04-27T19:55:04.547 に答える
3

ここでの再帰アルゴリズムは、特定の条件を何度も呼び出すことになります。例えば：

3, 3
  2, 3
    1, 3
      0, 3
      0, 2
    1, 2
      0, 2
      0, 1
  2, 2
    1, 2
      0, 2
      0, 1
    1, 1
      0, 1
      0, 0

たとえば、(1, 2) がどのような値になったかを記憶し、それらのパラメーターで再度呼び出されたときにすぐにそれを返すことで、より効率的にすることができます。Guava の を使用すると、次のTableようになります。

public static double binomial(int n, int k, double p, Table<Integer, Integer, Double> memo) {
    if(memo.contains(n, k))
        return memo.get(n, k);

    double result;
    if (n == 0 && k == 0)
        result = 1.0;
    else if (n < 0 || k < 0)
        result = 0.0;
    else 
        result = (1 - p) * binomial(n - 1, k, p) + p * binomial(n - 1, k - 1, p);

    memo.put(n, k, result);
    return result;
}
于 2012-04-27T20:01:27.113 に答える
1

少し遅れましたが、ここで完全な解決策を探している人のために、以下は私のものです。最初に、動的プログラミング、メモ化、集計の意味を理解するために、https ://stackoverflow.com/a/6165124/4636721 の回答を読むことを他の人に提案します。

とにかく私の解決策については基本的に私たちは与えられた方法を持っています:

// Not efficient at all
private static double binomial(int N, int k, double p)
{
    if (N == 0 && k == 0)
    {
        return 1.0;
    }
    else if ((N < 0) || (k < 0))
    {
        return 0.0;
    }
    else
    {
        return (1.0 - p) * binomial(N - 1, k, p) + p * binomial(N - 1, k - 1, p);
    }
}

はい、これは本当に遅いです...再帰呼び出しの数はちょっと大きいです（約〜N ^ 2）

はい、基本的にはメモ化アプローチを使用できます。これは、基本的に他の人がすでに計算した値を基本的にキャッシュすることを述べているためです。一部の人々にとって、メモ化は再帰戦略を維持し、必要な値が計算されたかどうかを確認することを意味します。プログラムが計算してキャッシュする必要がない場合、実装は非常に簡単です。

private static double binomialTopDown(int N, int k, double p)
{
    double[][] cache = new double[N + 1][k + 1];

    for (int i = 0; i < (N + 1); i++)
    {
         Arrays.fill(cache[i], Double.NaN);
    }

    return binomialTopDown(N, k, p, cache);
}

// More efficient
private static double binomialTopDown(int N, int k, double p, double[][] cache)
{
    if ((N == 0) && (k == 0))
    {
        return 1.0;
    }
    else if ((N < 0) || (k < 0))
    {
        return 0.0;
    }
    else if (Double.isNaN(cache[N][k]))
    {
        cache[N][k] = (1.0 - p) * binomialTopDown(N - 1, k, p, cache) + p * binomialTopDown(N - 1, k - 1, p, cache);
    }

    return cache[N][k];
}

秘訣は、実際にはボトムアップ アプローチ (集計とも呼ばれる) を使用して、より効率的な方法で計算を順序付けることです。これは通常、上記のアルゴリズムの反復バージョンを使用して実現されます。

// Much more efficient
private static double binomialBottomUp(int N, int k, double p)
{
    /*
    double[][] cache = new double[N + 1][k + 1];

    cache[0][0] = 1.0;

    for (int i = 1; i <= N; i++)
    {
        cache[i][0] = Math.pow(1.0 - p, i);

        for (int j = 1; j <= k; j++)
        {
            cache[i][j] =  p * cache[i - 1][j - 1] + (1.0 - p) * cache[i - 1][j];
        }
    }

    return cache[N][k];
    */

    // Optimization using less memory, swapping two arrays
    double[][] cache = new double[2][k + 1];
    double[] previous = cache[0];
    double[] current = cache[1];
    double[] temp;

    previous[0] = 1.0;

    for (int i = 1; i <= N; i++)
    {
        current[0] = Math.pow(1.0 - p, i);

        for (int j = 1; j <= k; j++)
        {
            current[j] =  p * previous[j - 1] + (1.0 - p) * previous[j];
        }

        temp = current;
        current = previous;
        previous = temp;
    }

    return previous[k];
}

これは、ボトムアップ アプローチで動的計画法を使用する最も効率的な方法です。

お役に立てれば。

于 2016-03-30T06:34:30.623 に答える