Neden rasgele sayı üreteçleri için park etme testinin uygulanmam kötü sonuçlara yol açıyor?

Question

Rasgele sayı üreteçleri için otopark testinin bir uygulamasını yazmaya çalışıyorum. Test hakkında bilgilerimi aldığım kaynaklar: Intel math library documentation ve Page 4 of this paper ve here listelenen olasılık yoğunluğu için phi işleviyle birlikte.

C# 'daki testin bir uygulamasını yazdım. Değerleri başlangıçta boş olarak ayarlanmış bir 100x100 ızgara kullanır. Daha sonra x ve y için rasgele tamsayılar üretmek için rasgele sayı üretecini kullanıyorum. Şebeke ve komşuların indeksi boşsa, bu dizin 1'e ayarlanır. Aksi halde, bir "çökme" olduğu için hiçbir şey olmuyor.

C# System.Random üreteci kullanarak koştum. Sonuçların doğru olduğuna inanmıyorum çünkü her zaman park ettiğim 3079'a yakın noktaya ulaşıyorum, ki ortalama 500'e yakın olmam gerekiyor. Ayrıca 2.21829146215425E-90 bir p-değeri verir.

Kodum aşağıda. Bu konuda herhangi bir tecrübesi olan var mı, yoksa uygulamamda yanlış yaptığım bir şeyi herkes görebilir mi? Herhangi bir yardım büyük takdir edilecektir.

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)); 
    } 

düzenleme - Ben bunun yerine sadece tamsayı değerleri noktaları çizilen

disklerin kareler planları yaptığı

• benim orijinal uygulanması ile ilgili sorunlar vardı. Bunun yerine ondalık değerler kullanmalıydım. Yukarıdaki ikisinin bir sonucu olarak
, bu bulmaktan yardım Chris Sinclair ve maden z benim mesafesi, kontrol edildiğinde

Teşekkür değiştirmek gerekiyordu. Son kod aşağıda yer almaktadır.

Answer 1

Bu konuda bir bıçak kullanacağım, ve kuşkusuz ki, böyle bir testi denemedim, o yüzden yola çıksam beni affet. Ancak, genel olarak, .NET Random uygulaması oldukça iyi ve onunla hiçbir zaman sorunları olmadı, bu yüzden özellikle başlangıçta yeni bir tane oluşturmak yerine aynı örneği yeniden kullandığınızdan şüphelenmem.

Park.pdf'den ve Intel belgelerinden okunduğunda, disk kullanıyor ve orta noktalardan uzaklığı hesaplıyor gibi görünüyor. Uygulamanız kareleri kullanıyor (noktalar arasındaki 1 mesafe dizisi) ve böylece diyagonalleri göz ardı ediyor. PDF

: diskler kullanılıyormuşçasına

, parçacıklar arasındaki mesafe = s r (x (i) - Z) 2 + (y (i) - Z) 2 gerekir birinden küçük veya eşit olmak. Birinin disk mi yoksa kare mi olduğunu fark eder mi? Geometrik şeklin park edildiği öneminin bir göstergesi, tarafından, bir kenarın 1.0 karesi tarafından kaplanan alanın, 1. çaplı bir disk alanı ile karşılaştırılarak elde edilebilir. Alanların, diskin kareye oranı π/4'tür. Bu nedenle, aynı sayıda denemede karelerden daha fazla diskin kutuya yerleştirilmesi beklenebilir.

Ve Intel doc: Her önceki başarıyla “park edilmiş” noktasından uzakta yeterli eğer

testi başarıyla (x, y) “park edilmiş” bir sonraki rastgele noktayı varsayar. (| - |, | y1 - y2 | x2 x1)> 1.

ben tt olduğunu tahmin ediyorum noktalarında (x1, y1) ve (x2, y2) arasındaki yeterli mesafe dk/4 diskten kare oranına ve kaç tane diskin karelere sığabileceği arasındaki farklar farklı bir sayı görmeniz nedeni olabilir. (Şu anda 3523 ve 3070 ile π/4. 3523 * π/4 = 2767 arasında doğrudan bir ilişki göremiyorum, fakat yakın bir ilişki varsa, eminim ki basit bir çarpımdan biraz daha karmaşıktır.

Harika bir cevap değil, en iyi tahminim.

DÜZENLEME: İlginç bir şekilde, 1 birim çapa sahip diskleri kullanarak hızlı bir uygulama yaptım ve 4000 park etrafında sonuçlar elde ettim. (? Ya da belki .NET en Random testini geçemezse): benim olasılıkla çok basit bir uygulama kullanarak

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)); 
} 

yüzden belki kavrayabilir benim eğitimsiz kendini daha bu biraz daha fazlası var Neyse, işte benim disk uygulaması var π/4 oranı yaklaşık 3142 verir. Biraz daha yakın, ama çok yanlış görünüyor.

DÜZENLEME: Mike z işaretli gibi, doğrudan mesafeyi kullanarak yaptığım test yanlış.

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

güzel 3450 etrafına çok daha yakın bir sonuç, verimleri: unuttuğum test parametrelerinin göre, sadece benim Distance çek değiştirme X ve Y mesafesi 1'den büyük olup olmadığını kontrol eder kapat. Eğer "//" kutunun "kutusunun içinde" olduğundan emin olun, 10 den fazla denemenin ortalaması 3531 olur!

Yani, "çalışma" kod kesindir benim:

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)); 
} 

DÜZENLEME: 100 kez iki kez testi yaptı ve sırasıyla 3521.29 ve 3526.74 sonuçları ortalama. Bunun hala bunun için biraz daha fazla bir şey ifade ettiğinden emin değilsiniz, fakat belki de bu yalnızca .NET ve Fortran arasındaki yuvarlama veya kayan nokta hassaslık farklarının göstergesidir.