1

このコードを使用して、Fisher-Yates のランダム化アルゴリズムのバリエーションを使用してベクトルのランダム順列を生成しています (最初の要素から最後の要素に移動しますが、その逆ではありません)。boost::random::mt11213bプログラムの開始時にシードされるプログラムで RNG をグローバルに使用しているgenerator.seed(time(NULL));ため、ここではラッパーシングルトンを使用RandomNumberしています。

boost::random::uniform_int_distribution<unsigned long> 
    distribution(0, vec.size()-1);

for (unsigned long i=0;i<vec.size();i++)
    std::swap(vec[i], vec[distribution(RandomNumber::getInstance().generator)]);

いくつかの実験により、このアルゴリズムに問題がある可能性があると確信するようになりました。これは私がしたことです

  1. 長さ 100 の整数のベクトルを作成しました
  2. 最初の 75 個の要素と0最後の 25 個の要素を1
  3. 配列をシャッフルしました。
  4. リストから最初の 5 つの要素を取得し、それらを合計しました。

この手順を数千回繰り返しました（手動ではなくループを使用して:)）毎回、新しいベクトルから始めました。次に、合計の算術平均を計算したところ0.98、期待値の代わりに結果が得られました1.25。

面白いことに、順序付けされたアルゴリズムではなく、同じアルゴリズムで 1 回シャッフルされたベクトルから始めると、結果は次のよう1.22に増加し、反復ごとにベクトルを破棄せずに、もう一度シャッフルするだけで、結果は1.25期待値です。

何が問題なのかわからない。アルゴリズムは健全に見えます。私が考えることができる唯一の問題は、シード段階と

boost::random::uniform_int_distribution<unsigned long> 
    distribution(0, vec.size()-1);

ベクトルがシャッフルされる前に毎回呼び出される行 (おそらく、プログラムで一度だけ呼び出す必要がありますが、それはあまり意味がありません)

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

4

2 に答える 2

3

原因を推測する必要がある場合は、ループの前後で毎回配布サイズを変更する必要はありません。Art ofComputerProgrammingアルゴリズムはこちらです。

最大n個の要素をシャッフルしたら、最初のnに再度触れたくありません。疑似乱数を繰り返し適用しても、ランダム性が低下するため、ランダム性が低下します。

于 2012-04-23T19:25:14.427 に答える
2

いいえ、あなたのアルゴリズムは間違っています。4 つの数値のベクトルを使用した単純なケースを考えてみましょう。アルゴリズムは次の偏った結果を返します。

result      probability * 256
{1,2,3,4}   10
{1,2,4,3}   10
{1,3,2,4}   10
{1,3,4,2}   14
{1,4,2,3}   11
{1,4,3,2}   9
{2,1,3,4}   10
{2,1,4,3}   15
{2,3,1,4}   14
{2,3,4,1}   14
{2,4,1,3}   11
{2,4,3,1}   11
{3,1,2,4}   11
{3,1,4,2}   11
{3,2,1,4}   9
{3,2,4,1}   11
{3,4,1,2}   11
{3,4,2,1}   10
{4,1,2,3}   8
{4,1,3,2}   9
{4,2,1,3}   9
{4,2,3,1}   8
{4,3,1,2}   10
{4,3,2,1}   10

一方、標準のフィッシャー・イェーツ アルゴリズムでは、すべての結果に対して均一な確率が得られます。

ベクトルをシャッフルしたい場合は、std::random_shuffle直接使用します (コード例については、std::random_shuffle の RNG として boost::random を使用するを参照してください)。

于 2012-04-23T19:32:23.153 に答える