5

budget配列n内のすべての要素が同じ分布を持ち、合計が になり、配列内budgetの各要素が少なくともmin

O(予算) で実行されるアルゴリズムがあります。

private int[] distribute(int budget, int n, int min) {
  int[] subBudgets = new int[n];
  for (int i = 0; i < n; i++) {
    subBudgets[i] = min;
  }
  budget -= n * min;
  while (budget > 0) {
    subBudgets[random.nextInt(n)]++;
    budget--;
  }
  return subBudgets;
}

ただし、budget増えると非常に高価になる可能性があります。O(n) またはそれ以上で動作するアルゴリズムはありますか?

4

4 に答える 4

4

最初にn乱数を生成x[i]し、それらを合計してから合計で割るbudgetと、 が得られkます。次に、k*x[i]各配列要素に割り当てます。シンプルでO(n)です。

各要素に少なくとも値が必要な場合は、上記のアルゴリズムを開始する前に、minすべての要素を埋めてmin(または使用してk*x[i] + min) 下請けすることで、上記のアルゴリズムを変更できます。n*minbudget

整数を扱う必要がある場合は、実数値kと丸めを使用して問題に取り組むことができますk*x[i]。次に、丸め誤差の累積を追跡し、単位全体に達した場合は、計算値から累積誤差を加算または減算する必要があります。また、残りの値を最後の要素に割り当てて、全体に到達する必要がありbudgetます。

PS: このアルゴリズムは、純粋関数型言語の easy で使用できることに注意してください。これが、メンバーごとに乱数を生成し、後で何らかの処理を行うこのアルゴリズムのファミリー全体が好きな理由です。Erlang での実装例:

-module(budget).

-export([distribute/2, distribute/3]).

distribute(Budget, N) ->
  distribute(Budget, N, 0).

distribute(Budget, N, Min) when
    is_integer(Budget), is_integer(N), N > 0,
    is_integer(Min), Min >= 0, Budget >= N*Min ->
  Xs = [random:uniform() || _ <- lists:seq(1,N) ],
  Rest = Budget - N*Min,
  K = Rest / lists:sum(Xs),
  F = fun(X, {Bgt, Err, Acc}) ->
      Y = X*K + Err,
      Z = round(Y),
      {Bgt - Z, Y - Z, [Z + Min | Acc]}
  end,
  {Bgt, _, T} = lists:foldl(F, {Rest, 0.0, []}, tl(Xs)),
  [Bgt + Min | T].

C++ の同じアルゴリズム (?? わかりません。)

private int[] distribute(int budget, int n, int min) {
  int[] subBudgets = new int[n];
  double[] rands = new double[n];
  double k, err = 0, sum = 0;
  budget -= n * min;
  for (int i = 0; i < n; i++) {
    rands[i] = random.nextDouble();
    sum += rands[i];
  }
  k = (double)budget/sum;
  for (int i = 1; i < n; i++) {
    double y = k*rands[i] + err;
    int z = floor(y+0.5);
    subBudgets[i] = min + z;
    budget -= z;
    err = y - z;
  }
  subBudgets[0] = min + budget;
  return subBudgets;
}
于 2013-10-22T22:59:18.243 に答える
1

@Hynek -Pichi- Vychodil のアイデアと私のオリジナルのアルゴリズムを統合して、O(n) で実行され、すべての丸め誤差が配列に均一に分散される次のアルゴリズムを思いつきました。

private int[] distribute(int budget, int n, int min) {
  int[] subBudgets = new int[n];
  for (int i = 0; i < n; i++) {
    subBudgets[i] = min;
  }
  budget -= n * min;
  if (budget > 3 * n) {
    double[] rands = new double[n];
    double sum = 0;
    for (int i = 0; i < n; i++) {
      rands[i] = random.nextDouble();
      sum += rands[i];
    }
    for (int i =0; i < n; i++) {
      double additionalBudget = budget / sum * rands[i];
      subBudgets[i] += additionalBudget;
      budget -= additionalBudget;
    }
  }
  while (budget > 0) {
    subBudgets[random.nextInt(n)]++;
    budget--;
  }
  return subBudgets;
}
于 2013-10-23T18:33:35.170 に答える
1

多項分布からのサンプリング

min各サブバジェットに与えられた後に残ったドルを現在分配している方法には、固定数budgetのランダムな「試行」を実行することが含まれます。各試行では、カテゴリの 1 つをランダムに選択しn、各カテゴリが何回あるかを知りたいと考えています。が選択されます。これは、次のパラメーターを持つ多項分布によってモデル化されます。

  • 試行回数 ( nWP ページで呼び出されます):budget
  • カテゴリの数 ( kWP ページで呼び出されます):n
  • iに対する各試行のカテゴリの確率1 <= i <= n:1/n

現在行っている方法は、試行回数がカテゴリ数とほぼ同じかそれ以下の場合に適しています。ただし、予算が大きい場合は、この分布からサンプリングするより効率的な方法が他にもあります。私が知っている最も簡単な方法は、kカテゴリをグループ化することにより、カテゴリを含む多項分布を二項分布に繰り返し分解できることに注意することです。各kカテゴリに直接いくつの選択があるかではなく、これを一連の質問として表現します。 「最初のカテゴリーと他のカテゴリーの間で予算をどのように分割するk-1か?」次に、「残りを 2 番目のカテゴリと他のカテゴリに分割する方法はk-2?」などを尋ねます。

したがって、最上位の二項式には、カテゴリ (サブバジェット) 1 とその他すべてがあります。n = budgetパラメータと二項分布から 1 つのサンプルを取得して、サブ予算 1 に投入するドルの数を決定します(これを行う方法については、こちらp = 1/nで説明しています)。これにより、いくつかの数値が生成されます。サブバジェット 2 に入るドルの数を見つけるには、残りのお金の二項分布から 1 つのサンプルを取得します。つまり、パラメーターとを使用します。サブバジェット 2 の金額 x[2] を取得した後、サブバジェット 3 はパラメーターおよび などを使用して検出されます。0 <= x[1] <= nn = budget - x[1]p = 1/(n-1)n = budget - x[1] - x[2]p = 1/(n-2)

于 2013-10-22T22:47:25.047 に答える