În imaginea de mai sus, puteți vedea o grilă de coordonate care conține câteva puncte verzi aleatorii. Fiecare punct are o șansă pseudoaleatorie de 1/10 să fie verde. Ceea ce caut sunt grupuri de aceste puncte verzi pe o rază de ~ 8 (ignorați masca interioară afișată). Altfel spus, caut zone cu densitate mare improbabile din punct de vedere statistic ale acestor puncte verzi.
În centrul acestei probleme se află Java RNG găsit în java.util.Random
(sursa aici). Codul pentru a determina dacă un punct este verde se rezumă la această funcție hash. Intrările sunt unele constante, $k$, și coordonatele punctului, $x$ și $y$.
sămânță lungă = ((k + (lung) (x * x * 4987142) + (lung) (x * 5947611) + (lung) (y * y) * 4392871L + (lung) (y * 389711) ^ 987234911L) ^ 0x5DEECE66DL) & ((1L << 48) - 1);
int biți, val;
do
{
sămânță = (sămânță * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
biți = (int)((ulong)seed >> 17);
val = biți % 10;
} while (biți - val + 9 < 0);
return val == 0;
A fost cercetări minore asupra acestei probleme în trecut, dar nu sunt suficient de informat pentru a contribui în continuare. Ceea ce s-a găsit a fost că potenţial clustere cu dimensiuni mici de 2x2 și 3x3 creează un model atunci când se compară cu diferite $k$ valorile.
Acest lucru poate oferi indicii cu privire la coordonatele unei căutări ar trebui să se concentreze mai mult pe calcul, având în vedere un anumit $k$, dar nu sunt convins.
De exemplu, iată o hartă termică a dimensiunilor clusterului pentru un anumit $k$. Puteți găsi mai multe informații despre cum au fost derivate aceste imagini Aici.
Începând de acum, verific cu forță brută numărul de cluster al fiecărei coordonate și omit o coordonată dacă clusterul este prea mic pentru ca următorul să aibă un cluster de dimensiune suficientă, ceea ce este majoritatea pentru că caut statistici. valori aberante.
Ceea ce sper este că există un model exploatabil în acest algoritm, este practic să inversați acest hash într-un fel sau există optimizări majore de făcut în metoda mea actuală.
Poate că o posibilă cale de înaintare ar fi să vedem dacă modelul de zăbrele continuă să persistă pentru grupuri din ce în ce mai mari, dar o altă imagine din acea postare pare să indice că s-ar pierde în zgomot.