На изображении выше вы можете видеть координатную сетку, содержащую несколько случайных зеленых точек. Каждая точка имеет псевдослучайный шанс 1/10 быть зеленым. То, что я ищу, - это кластеры этих зеленых точек в радиусе ~ 8 (игнорируйте показанную внутреннюю маску). Другими словами, я ищу статистически маловероятные области высокой плотности этих зеленых точек.
В основе этой проблемы лежит Java RNG, найденный в java.util. Случайный (источник здесь). Код для определения того, является ли точка зеленой, сводится к этой хэш-функции. Входы являются некоторыми постоянными, $к$, и координаты точки, $х$ и $у$.
длинное семя = ((k + (длинное) (x * x * 4987142) + (длинное) (x * 5947611) + (длинное) (y * y) * 4392871L + (длинное) (y * 389711) ^ 987234911L) ^ 0x5DEECE66DL) & ((1L << 48) - 1);
целые биты, знач.;
делать
{
seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
биты = (int)((ulong)seed >> 17);
знач = бит % 10;
} while (биты - val + 9 < 0);
вернуть значение == 0;
Там было небольшое исследование по этой проблеме в прошлом, но я недостаточно осведомлен, чтобы внести свой вклад. Было обнаружено, что потенциал кластеры с небольшими размерами 2х2 и 3х3 создают закономерность при сравнении с разными $к$ ценности.
Это может дать подсказки относительно того, в каких координатах при поиске следует сосредоточить больше вычислений при определенных условиях. $к$, но я не уверен.
В качестве примера, вот тепловая карта размеров кластера для конкретного $к$. Вы можете найти больше информации о том, как эти изображения были получены из здесь.
На данный момент я просто грубо проверяю количество кластеров каждой координаты и пропускаю координату, если кластер слишком мал для следующего, чтобы иметь кластер достаточного размера, что является большинством из них, потому что я ищу статистические выбросы.
На что я надеюсь, так это на то, что в этом алгоритме есть какой-то шаблон, который можно использовать, что практично каким-то образом реверсировать этот хэш, или что в нем есть серьезные оптимизации. мой текущий метод.
Возможно, возможным путем вперед было бы посмотреть, сохраняется ли решетчатый узор для все более и более крупных кластеров, но другое изображение в этом посте, похоже, указывает на то, что он просто потеряется в шуме.
