Trong hình trên, bạn có thể thấy một lưới tọa độ chứa một số điểm màu xanh lá cây ngẫu nhiên. Mỗi điểm có 1/10 cơ hội giả ngẫu nhiên có màu xanh lục. Những gì tôi đang tìm kiếm là các cụm điểm màu xanh lá cây này trong bán kính ~8 (bỏ qua mặt nạ bên trong được hiển thị). Nói cách khác, tôi đang tìm kiếm các khu vực mật độ cao không chắc chắn về mặt thống kê của những điểm màu xanh lá cây này.
Cốt lõi của vấn đề này là Java RNG được tìm thấy trong java.util.Random (nguồn ở đây). Mã để xác định xem một điểm có màu xanh lục hay không phụ thuộc vào hàm băm này. Các yếu tố đầu vào là một số không đổi, $k$, và tọa độ của điểm, $x$ và $y$.
hạt dài = ((k + (dài) (x * x * 4987142) + (dài) (x * 5947611) + (dài) (y * y) * 4392871L + (dài) (y * 389711) ^ 987234911L) ^ 0x5DEECE66DL) & ((1L << 48) - 1);
bit int, val;
làm
{
hạt giống = (hạt giống * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
bit = (int)((ulong)hạt >> 17);
val = bit % 10;
} while (bit - val + 9 < 0);
trả về giá trị == 0;
Đã có nghiên cứu nhỏ về vấn đề này trong quá khứ nhưng tôi không đủ hiểu biết để đóng góp thêm. Những gì đã được tìm thấy là tiềm năng các cụm có kích thước nhỏ 2x2 và 3x3 tạo ra một mẫu khi so sánh với các cụm khác nhau $k$ các giá trị.
Điều này có thể cung cấp manh mối về tọa độ mà một tìm kiếm sẽ tập trung tính toán nhiều hơn với một giá trị nhất định. $k$, nhưng tôi không bị thuyết phục.
Như một ví dụ, đây là một bản đồ nhiệt kích thước cụm cho một cụ thể $k$. Bạn có thể tìm thêm thông tin về cách những hình ảnh này được lấy từ đây.
Hiện tại, tôi chỉ đang kiểm tra số lượng cụm của từng tọa độ và bỏ qua tọa độ nếu cụm quá thấp để cụm tiếp theo có cụm đủ kích thước, hầu hết trong số đó là do tôi đang tìm kiếm thống kê ngoại lệ.
Điều tôi hy vọng là có một số mẫu có thể khai thác được trong thuật toán này, thực tế là có thể đảo ngược hàm băm này theo một cách nào đó hoặc có những tối ưu hóa chính cần có trong phương pháp hiện tại của tôi.
Có thể một con đường khả thi phía trước sẽ là xem liệu mô hình mạng tinh thể có tiếp tục tồn tại đối với các cụm ngày càng lớn hơn hay không, nhưng một hình ảnh khác trên bài đăng đó dường như chỉ ra rằng nó sẽ bị lẫn trong tiếng ồn.
