1

次の制約を満たすn個のランダムな実数値P[0]、P [1]、...、P[n-1]を生成する必要があります。

Pmin[0] <= P[0] <= Pmax[0]
Pmin[1] <= P[1] <= Pmax[1]
...
Pmin[n-1] <= P[n-1] <= Pmax[n-1]

P[0] + P[1] + ... + P[n-1] = S

これを効率的に行う方法はありますか？

4

2 に答える 2

1

一般に、指定された範囲から一様にランダムに要素を選択する場合、この問題を解決することはできません。

例 1: Pmin[i] = 0、Pmax[i] = 1 とします。n = 10、S = 100 とします。この場合、可能な最大和は 10 であるため、解はありません。

例 2: Pmin[i] = 0 および Pmax[i] = 1 とします。n = 10 および S = 10 とします。この場合、厳密に 1 つの解があります。P[i] = 1 を選択します。

結果のシーケンスが可能な解のセットからランダムに一様に選択されるようなアルゴリズムを書くことができます。これは、P[i] が Pmin[i] と Pmax[i] の間で一様に分布しているということとはまったく異なります。

基本的な考え方は、次のように、各段階で範囲をさらに制限することです。

  1. 範囲の始まりは、次の 2 つの量のうち大きい方でなければなりません: Pmin[i]、または S - Smax[i] - P、ここで、Smax[i] は合計 Pmax[i+1] + ... + Pmax[n] および P は合計 P[0] + ... + P[i] です。これにより、最終的に機能するのに十分な大きさの数値を選択することが保証されます。
  2. 範囲の終わりは、次の 2 つの量のうち小さい方でなければなりません: Pmax[i]、または S - Smin[i] - P、ここで、Smin[i] は合計 Pmin[i+1] + ... + Pmin[n] と P は以前と同じです。これにより、最終的に機能するのに十分小さい数値を選択することが保証されます。

各 P[i] を選択するときにこれらのルールに従うことができれば、解決策があり、ランダムに 1 つ見つけることができます。そうでなければ、解決策はありません。

実際にこの選択ソリューションをランダムに作成するには、インデックスをシャッフルし、このアルゴリズムを実行してから、適切な順序になるようにシーケンスを再配置するのがおそらく最善であることに注意してください。O(n) でシャッフルし、このアルゴリズムを実行して (ソリューションをボトムアップで構築できるため、ここでは動的プログラミングをお勧めします)、結果のシーケンスを「アンシャッフル」してシーケンスを吐き出すことができます。

于 2013-02-07T17:03:47.000 に答える
0 
For every i, assign P[i] := Pmin[i]
Compute the sum
If sum>S, then stop (it's impossible)
For every i:
    If P[i]+S-sum <= Pmax[i]
        P[i] = P[i]+S-sum
        Stop (it's done :-)
    sum = sum+Pmax[i]-P[i]
    P[i] = Pmax[i]
    Go for next i
Stop (it's impossible)

おっと、すみません、あなたはランダムに言いました...それはそれほど些細なことではありません。私はそれについて考えてみましょう...

前のアルゴリズムを実行して、開始点を取得します。次に、上下の総マージンを計算します。上記のマージンは、すべての i の個々のマージン Pmax[i]-P[i] の合計です。以下のマージンは、すべての i の個々のマージン P[i]-Pmin[i] の合計です。

ランダムな順序で1 つを除くすべての要素をトラバースし、各要素を 1 回だけ訪れます。それらのすべてについて：

  • 上のマージンと下のマージンを更新して、現在の要素の寄与分を差し引いてください。
  • 次のことを考慮して、現在の値の最小値と最大値を確立します。
    • それらは区間 [Pmin[i], Pmax[i]] 内にある必要があり、かつ
    • これらの最小値と最大値は P[i] に十分近いため、後で他の要素を変更すると、P[i] をこの最小値または最大値に変更することを補うことができます (これは上下のマージンが示すものです)。
    • P[i] を計算された間隔 [最小、最大] のランダムな値に変更し、合計とマージンを更新します (ここでマージンをどのように更新する必要があるかは 100% わかりません...)

次に、合計 S に合わせて残りの要素を調整します。

ランダムな順序での走査については、Knuth shufflesを参照してください。

于 2013-02-07T16:42:16.317 に答える