4

私はちょっとしたレクリエーションホリデーコンピューティングをやっています。私のミニプロジェクトは、イタリアの「トンボリ」ゲームのシミュレーションでした。重要な構成要素は、次のプロセスのシミュレーションでした。

ゲームは、1から90までの番号が付けられた90個のビー玉のバッグを持った男性によって制御されます。彼は、プレーヤーにビー玉の番号を呼び出すたびに、バッグからランダムにビー玉を1つずつ引き出します。

少し考えた後、このビルディングブロック用に次のコードを作成しました。

// NBR marbles, numbered 1...NBR are in a bag. Simulate randomly
//  pulling them from the bag, one by one, until the bag is empty
void bag( int random_sequence[NBR] )
{
    int i;

    // Store each marble as it is pulled out
    int *store = random_sequence;

    // Array of marbles still in the bag
    int not_yet_pulled[NBR];
    for( i=0; i<NBR; i++ )
        not_yet_pulled[i] = i+1;    // eg NBR=90; 1,2,3 ... 90

    // Loop pulling marbles from the bag, one each time through
    for( i=NBR; i>=1; i-- )
    {
        int x = rand();
        int idx = x%i;  // eg i=90 idx is random in range 0..89
                        // eg i=89 idx is random in range 0..88
                        //            ...
                        // eg i=1  idx is random in range 0..0
                        //    (so we could optimize when i=1 but not worth the bother)
        *store++  = not_yet_pulled[idx];

        // Replace the marble just drawn (so it cannot be pulled again)
        //     with the last marble in the bag. So;
        //     1) there is now one less marble in the bag
        //     2) only marbles not yet pulled are still in the bag
        // If we happened to pull the last marble in the *current subarray*, this is
        //    not required but does no harm.
        not_yet_pulled[idx] = not_yet_pulled[i-1];
    }
}

乱数を使用したゲームシミュレーションには、いたるところに微妙な点や罠があることを知っています。そのため、コードにはかなり満足していますが、自信は100％弱です。だから私の質問は;

1）私のコードに何か問題がありますか？

2）[1）の答えが「いいえ」の場合]私は無意識のうちに標準のシャッフルアルゴリズムを使用していますか？

3）[2）の答えが「いいえ」の場合]私のアルゴリズムは標準的な代替アルゴリズムとどのように比較されますか？

編集 答えてくれたすべての人に感謝します。フィッシャー-イェーツアルゴリズムを再発見し、それが問題の核心になっていることを明らかにしたので、エイダンカリーの答えを受け入れるつもりです。もちろん、事前に調査を行うことで時間と労力を節約できたのも当然です。しかし一方で、それは楽しい趣味のプロジェクトでした。シミュレーションの残りの部分は日常的なものでした。これは最も興味深い部分でした。私は自分で行かなくても、楽しみを奪っていただろう。さらに、私はバッグからビー玉を取り出す男性をシミュレートしようとしていましたが、状況がカードのシャッフルとまったく同じであることに気付いたのは、作品のかなり遅い段階でした。

もう1つの興味深い点は、Kenによって特定された小さな欠陥があることです。この欠陥は、頻繁に繰り返されるパターンrand（）％Nは、0..N-1の範囲から乱数を選択するための実際には良い方法ではないことを指摘しています。

最後に、私のバージョンのフィッシャー-イェーツには、シャッフルという優れた特性を備えたエレガントなトリックが欠けています。その結果、私のアルゴリズムは、同じようにランダムですが逆のシャッフルになります。

4

8 に答える 8

11

フィッシャー-イェーツ-クヌースシャッフルを使用します。

public static void shuffle(int[] array) 
{
    Random rng = new Random();       // java.util.Random.
    // n is the number of items left to shuffle
    for (int n = array.length; n > 1; n--) 
    {
        // Pick a random element to move to the end
        int k = rng.nextInt(n);  // 0 <= k <= n - 1.
        // Simple swap of variables
        int tmp = array[k];
        array[k] = array[n - 1];
        array[n - 1] = tmp;
    }
}

あなたのコードはうまくいくようですが、よくわかりません。標準のアルゴリズムよりも難読化されています。

于 2009-12-28T23:00:07.523 に答える
7

フィッシャー-イェーツシャッフルアルゴリズムを使用しています。

于 2009-12-28T22:58:43.797 に答える
7 
int idx = x%i;  // eg i=90 idx is random in range 0..89

その範囲内ですが、90（またはNBR）がmax（rand（））を除算しない限り、均等に分散されません。2ビットコンピュータを使用している場合、それはおそらく真実ではありません。ここで、たとえば、idxは89よりも0になる可能性がわずかに高くなります。

于 2009-12-28T23:13:48.043 に答える
2

rand() % i（パフォーマンスを犠牲にして）より良いほぼ均一な分布を持つ代替案はです(int) ((rand() / (double) (RAND_MAX+1)) * i)。

または、メルセンヌツイスターなどのうまく機能することが知られている疑似乱数生成アルゴリズムを使用します。

于 2009-12-28T23:57:19.453 に答える
2

アルゴリズムを分析して、それらが本当にランダムであるかどうかを確認することは非常に困難です。
大学レベルの数学を持っている人（またはアメリカ人が言うように、数学を専攻している人）を除けば、これはほとんどの人のスキルをはるかに超えて検証することさえできます。

したがって、すでに構築されているアルゴリズムを試して使用する必要があります。std :: random_shuffle（）
を見たことがありますか？

 void bag( int random_sequence[NBR] )
 {
     for(int i=0; i<NBR; ++i) 
     {    random_sequence[i] = i+1;
     }
     std::random_shuffle(random_sequence,random_sequence + NBR);
 }

std :: random_shuffle（）ページからの引用：

このアルゴリズムは、Knuthのセクション3.4.2で説明されています（DE Knuth、The Art of ComputerProgramming。Volume2：Seminumerical Algorithms、第2版。Addison-Wesley、1981）。Knuthは、Moses and Oakford（1963）とDurstenfeld（1964）の功績を認めています。Nがあることに注意してください！N個の要素のシーケンスを配置する方法。Random_shuffleは、均一に分散された結果を生成します。つまり、特定の順序付けの確率は1 / N！です。このコメントが重要である理由は、シーケンスのランダムなシャッフルを実装するように一見すると見えるが、実際にはN全体に均一な分布を生成しないアルゴリズムがいくつかあるためです。可能な注文。つまり、ランダムシャッフルを間違えるのは簡単です。

于 2009-12-28T23:03:00.600 に答える
1

ほんの2、3の文体のポイント：

  1. 指定された長さの配列を取得するという署名により、パラメーターが少なくともIDX要素を含むことがコンパイラーによって保証されているように見える場合があります。そうではありません。
  2. おそらく、2番目のforループのループインデックスにmarblesRemainingのようなよりわかりやすい名前を付けるので、それが何であるかが明確になり、コメントで説明する必要はありません。また、最初のループでのまったく異なる使用法から分離します。
于 2009-12-28T23:12:47.780 に答える
1

乱数の生成についてはさておき、シャッフルアルゴリズムは正しいように見えます。

ただし、それを改善することはできます。少し考えれば、その場で数字をシャッフルできることがわかります。したがって、一時配列を割り当てる代わりに、出力バッファーを使用することができます。

于 2009-12-29T06:54:48.353 に答える
0

他の人がすでにコメントしているように、実績のあるシャッフルアルゴリズムを使用してください。

C /C++ライブラリが提供しているのは疑似乱数のみであることに注意してください。

ランダム化アルゴリズムの高い信頼性を必要とするシステムは、専用のハードウェアを使用して乱数を生成します。ハイエンドのポーカーサイトが良い例です。たとえば、乱数生成手法に関するPokerstarsの記事を参照してください。

Netscape暗号化の初期のバージョンは、疑似乱数ジェネレーターに現在の時刻がシードされているため、ハッカーが使用される「乱数」を予測できたために壊れていました。ウィキペディアでこの記事を参照してください。

于 2009-12-28T23:12:18.630 に答える