จะใช้ประโยชน์จาก RNG ของ Java เพื่อค้นหาคลัสเตอร์ได้อย่างไร

ในภาพด้านบน คุณจะเห็นตารางพิกัดที่มีจุดสีเขียวแบบสุ่ม แต่ละจุดมีโอกาสปลอมเป็นสีเขียว 1/10 สิ่งที่ฉันกำลังมองหาคือกลุ่มของจุดสีเขียวเหล่านี้ภายในรัศมี ~8 (ละเว้นหน้ากากด้านในที่แสดง) กล่าวอีกนัยหนึ่งว่าฉันกำลังมองหาพื้นที่ความหนาแน่นสูงที่ไม่น่าเป็นไปได้ทางสถิติของจุดสีเขียวเหล่านี้ หัวใจหลักของปัญหานี้คือ Java RNG ที่พบใน java.util.Random (แหล่งที่มาที่นี่). รหัสสำหรับกำหนดว่าจุดเป็นสีเขียวจะลดระดับลงมาจากฟังก์ชันแฮชนี้หรือไม่ อินพุตมีค่าคงที่ $k$และพิกัดของจุด $x$ และ $y$.

เมล็ดยาว = ((k + (ยาว) (x * x * 4987142) + (ยาว) (x * 5947611) + (ยาว) (y * y) * 4392871L + (ยาว) (y * 389711) ^ 987234911L) ^ 0x5DEECE66DL) & ((1L << 48) - 1);
int บิต วาล;
ทำ
{
    เมล็ด = (เมล็ด * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
    bits = (int)((อู่หลง)seed >> 17);
    val = บิต % 10;
} ในขณะที่ (บิต - วาล + 9 < 0);

คืนค่า == 0;

มีอยู่แล้ว การวิจัยเล็กน้อยเกี่ยวกับปัญหานี้ ในอดีต แต่ฉันไม่มีความรู้พอที่จะช่วยเหลือเพิ่มเติม สิ่งที่พบก็คือ ศักยภาพ คลัสเตอร์ที่มีขนาดเล็ก 2x2 และ 3x3 สร้างรูปแบบเมื่อเปรียบเทียบกับที่แตกต่างกัน $k$ ค่า

สิ่งนี้อาจให้เงื่อนงำว่าพิกัดใดที่การค้นหาควรเน้นการคำนวณมากกว่าที่กำหนด $k$แต่ฉันไม่มั่นใจ ต่อไปนี้เป็นแผนที่ความหนาแน่นของขนาดคลัสเตอร์สำหรับตัวอย่างหนึ่งๆ $k$. คุณสามารถค้นหาข้อมูลเพิ่มเติมเกี่ยวกับแหล่งที่มาของรูปภาพเหล่านี้ ที่นี่.

ณ ตอนนี้ ฉันเป็นเพียงกำลังดุร้ายตรวจสอบจำนวนคลัสเตอร์ของแต่ละพิกัด และข้ามพิกัดหากคลัสเตอร์ต่ำเกินไปสำหรับอันถัดไปที่จะมีคลัสเตอร์ที่มีขนาดเพียงพอ ซึ่งส่วนใหญ่เป็นเพราะฉันกำลังมองหาสถิติ ค่าผิดปกติ

สิ่งที่ฉันหวังคือมีรูปแบบที่ใช้ประโยชน์ได้ในอัลกอริทึมนี้ การย้อนกลับแฮชนี้สามารถทำได้จริงในทางใดทางหนึ่ง หรือมีการเพิ่มประสิทธิภาพที่สำคัญใน วิธีการปัจจุบันของฉัน.

บางทีแนวทางที่เป็นไปได้ในอนาคตคือการดูว่ารูปแบบขัดแตะยังคงมีอยู่สำหรับกลุ่มที่ใหญ่ขึ้นและใหญ่ขึ้นหรือไม่ แต่ภาพอื่นในโพสต์นั้นดูเหมือนจะบ่งบอกว่ามันจะหายไปจากสัญญาณรบกวน