5

乱数発生器の駐車場テストの実装を書こうとしています。テストに関する情報を入手しているソースは次のとおりです。Intel数学ライブラリのドキュメントとこのペーパーの4ページ、およびここにリストされている確率密度のphi関数。

テストの実装をC＃で作成しました。値が最初にnullに設定されている100x100グリッドを使用します。次に、乱数ジェネレーターを使用して、xとyのランダムな整数を生成します。グリッドとそのネイバーのインデックスが空の場合、そのインデックスは1に設定されます。それ以外の場合、「クラッシュ」が発生したため、何も起こりません。

C＃System.Randomジェネレーターを使用して実行しました。私は常に3079ポイント近くに駐車しているので、結果が正しいとは思いません。これは、私が得ることになっている平均よりも約500ポイント少ないです。また、2.21829146215425E-90のp値が得られます。

私のコードは以下の通りです。誰かがこれについて何か経験がありますか、または誰かが私の実装で間違っているかもしれない何かを見ることができますか？どんな助けでも大歓迎です。

  private void RunParkingLotTest()
    {
        points = new int?[100,100];
        int parked = 0;

        for (int i = 0; i < 12000; i++)
        {
            int x = random.Next(100);
            int y = random.Next(100);

            if (IsSafeToPark(x, y))
            {
                points[x, y] = 1;
                parked++;
            }

        }
        Console.WriteLine("Parked: " + parked + "\nP value: " + PhiFunction((parked-3523)/21.9));
    }

    private bool IsSafeToPark(int x, int y)
    {
        return PointIsEmpty(x, y) 
            && LeftOfPointIsEmpty(x, y) 
            && RightOfPointIsEmpty(x, y) 
            && BelowPointIsEmpty(x, y) 
            && AbovePointIsEmpty(x, y);
    }

    private bool AbovePointIsEmpty(int x, int y)
    {
        if (y == 99)
        {
            return true;
        }
        else
            return points[x, y + 1] == null;
    }

    private bool BelowPointIsEmpty(int x, int y)
    {
        if (y == 0)
        {
            return true;
        }
        else
            return points[x, y - 1] == null;
    }

    private bool RightOfPointIsEmpty(int x, int y)
    {
        if (x == 99)
        {
            return true;
        }
        else
            return points[x + 1, y] == null;
    }

    private bool LeftOfPointIsEmpty(int x, int y)
    {
        if (x == 0)
        {
            return true;
        }
        else
            return points[x - 1, y] == null;
    }

    private bool PointIsEmpty(int x, int y)
    {
        return points[x, y] == null;
    }

    private double PhiFunction(double x)
    {
        //ϕ(x) = (2π)−½e−x2/2

        return ((1 / Math.Sqrt(2 * Math.PI)) * Math.Exp(-(Math.Pow(x, 2)) / 2));
    }

編集-私の元の実装の問題は

  • ディスクの代わりに正方形をプロットしていました
  • ポイントを整数値でプロットしただけです。代わりに10進数を使用する必要がありました。
  • 上記の2つの結果として、距離チェックを変更する必要がありました

これを理解するのを手伝ってくれたChrisSinclairとminezに感謝します。最終的なコードは以下に掲載されています。

4

1 に答える 1

4

私はこれを突き刺すつもりです、そして確かに、私はそのようなテストを試みたことがないので、私が遠く離れているならば私を許してください。ただし、一般的に、.NETのRandom実装は非常に優れており、問題が発生したことは一度もないので、特に、新しいインスタンスを作成する代わりに同じインスタンスを適切に再利用しているので、最初はそうは思わないでしょう。

Parking.pdfとIntelのドキュメントを読むと、彼らはディスクを使用しているようで、中心点からの距離を計算しています。実装では、正方形（スポット間の距離が1の配列）を使用しているため、対角線は無視されます。

PDFから：

ディスクが使用されている場合、粒子間の距離r = p（x（i）− z）2 +（y（i）− z）2は1以下である必要があります。ディスクを使用するか正方形を使用するかは重要ですか？側面1.0の正方形が占める面積を、直径1.0の円盤の面積と比較することにより、どの幾何学的図形が駐車されているかを示すことができます。ディスクと正方形の面積の比率はπ/4です。したがって、同じ試行回数で正方形よりも多くのディスクをボックスに配置できると予想されます。

そしてIntelのドキュメント：

テストでは、次のランダムなポイント（x、y）が、以前のすべての正常に「パーク」されたポイントから十分に離れている場合、正常に「パーク」されたと想定します。ポイント（x1、y1）と（x2、y2）の間の十分な距離は、min（| x1-x2 |、| y1-y2 |）>1です。

π/4のディスクと正方形の比率、およびディスクの数と正方形の数の違いが、異なる数が表示される理由である可能性があると思います。（今のところ、3523と3070とπ/4との直接的な関係はわかりません。3523*π/4 = 2767、これは近いですが、関係がある場合は、単純な乗算よりも少し複雑です。 ）。

良い答えではありませんが、私の推測です。

編集：興味深いことに、私は1ユニットの直径のディスクを使用して迅速な実装を行い、約4000の駐車結果を取得しました。ですから、これには、訓練を受けていない自分が理解できる以上のことがあるかもしれません（または、.NETRandomがテストに合格しなかったのでしょうか？）とにかく、これが私のディスク実装です。

List<Point> parkedCars = new List<Point>();
Random random = new Random();

void Main()
{
    int parked = 0;

    for (int i = 0; i < 12000; i++)
    {
        double x = random.NextDouble() * 100;
        double y = random.NextDouble() * 100;

        Point pointToPark = new Point(x, y);

        if (IsSafeToPark(pointToPark))
        {
            parkedCars.Add(pointToPark);
            parked++;
        }

    }
    Console.WriteLine("Parked: " + parked);
}

private bool IsSafeToPark(Point pointToPark)
{
    //make sure it's "inside" the box
    if (pointToPark.X < 0.5 || pointToPark.X > 99.5
        || pointToPark.Y < 0.5 || pointToPark.Y > 99.5)
        return false;

    if (parkedCars.Any(p => Distance(pointToPark, p) <= 1))
        return false;

    return true;
}

private double Distance(Point p1, Point p2)
{
    return Math.Sqrt((p1.X - p2.X) * (p1.X - p2.X) + (p1.Y - p2.Y) * (p1.Y - p2.Y));
}

おそらく単純すぎるπ/4比のアプリケーションを使用すると、約3142が得られます。少し近いですが、非常に正しくないようです。

編集：@mike zが指摘したように、直接距離を使用した私のテストは正しくありません。私が忘れていたテストのパラメーターによると、XとYの距離が1より大きいことをチェックするだけです。Distanceチェックを次のように変更します。

Math.Max(Math.Abs(p1.X - p2.X), Math.Abs(p1.Y - p2.Y))

かなり近い3450付近ではるかに近い結果が得られます。「//ボックスの「内側」にあることを確認してください」チェックを外すと、10回の試行で平均3531になります。

したがって、私の最後の「動作する」コードは次のとおりです。

public struct Point
{
    public double X,Y;

    public Point(double x, double y)
    {
        this.X = x;
        this.Y = y;
    }
}

List<Point> parkedCars = new List<Point>();
Random random = new Random();

void Main()
{
    int parked = 0;

    for (int i = 0; i < 12000; i++)
    {
        double x = random.NextDouble() * 100;
        double y = random.NextDouble() * 100;

        Point pointToPark = new Point(x, y);

        if (IsSafeToPark(pointToPark))
        {
            parkedCars.Add(pointToPark);
            parked++;
        }

    }

    Console.WriteLine("Parked: " + parked);
}

private bool IsSafeToPark(Point pointToPark)
{
    if (parkedCars.Any(p => Distance(pointToPark, p) <= 1))
        return false;

    return true;
}

private double Distance(Point p1, Point p2)
{
    return Math.Max(Math.Abs(p1.X - p2.X), Math.Abs(p1.Y - p2.Y));
}

編集：私はテストを100回2回実行し、結果をそれぞれ3521.29と3526.74に平均しました。これがまだ少しだけ多くのことを意味するかどうかはわかりませんが、おそらくこれは.NETとFortranの丸めまたは浮動小数点の精度の違いを示しているにすぎません。

于 2012-11-12T02:40:13.723 に答える