5

我正在尝试为随机数生成器编写停车场测试的实现。以下是我从中获取有关测试信息的来源：英特尔数学库文档和本文的第 4 页以及此处列出的概率密度的 phi 函数。

我用 C# 编写了测试的实现。它使用一个 100x100 的网格，其值最初设置为 null。然后我使用随机数生成器为 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));
    }

编辑 - 我原来的实现的问题是

  • 我正在绘制正方形而不是圆盘
  • 我只在整数值处绘制点。我应该改用十进制值。
  • 由于上述两个，我需要更改我的距离检查

感谢 Chris Sinclair 和 mine z 帮助解决这个问题。最终代码发布在下面。

4

1 回答 1

4

我将对此进行尝试，诚然，我没有尝试过任何这样的测试，所以如果我离题了，请原谅我。不过总的来说，.NETRandom实现非常好，而且我从来没有遇到过问题，所以我不会怀疑这一点，尤其是因为您正确地重用了同一个实例而不是创建新实例。

从parking.pdf 和英特尔文档中读取，似乎他们正在使用光盘，并计算到它们的中心点的距离。您的实现使用正方形（点之间距离为 1 的数组），因此忽略对角线。

来自pdf：

如果使用磁盘，粒子之间的距离 r = p(x(i) - z)2 + (y(i) - z)2 需要小于或等于 1。使用圆盘还是正方形有关系吗？通过将边长为 1.0 的正方形所占的面积与直径为 1.0 的圆盘的面积进行比较，可以得出停放哪个几何图形的重要性的指示。圆盘与正方形的面积比为 π/4。因此，可以预期在相同的尝试次数下，可以在一个盒子中放置比正方形更多的磁盘。

和英特尔文档：

测试假设下一个随机点 (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 次测试，并将结果分别平均为 3521.29 和 3526.74。不确定这是否意味着还有更多的东西，但这也许只是表示 .NET 和 Fortran 之间的舍入或浮点精度差异。

于 2012-11-12T02:40:13.723 回答