Алгоритм для идентификации уникального свободного полиомино (или полиноминового хеша)

Короче: Как хэш свободного полиомино?

Это можно было бы обобщить на: Как эффективно хешировать произвольный набор двумерных целочисленных координат, где множество содержит уникальные пары неотрицательных целых чисел, а множество считается уникальным тогда и только тогда, когда нет перевода, вращения, или флип может сопоставить его идентично другому набору?

Для нетерпеливых читателей обратите внимание, что я полностью понимаю подход грубой силы. Я ищу лучший способ - или очень убедительное доказательство того, что другого пути не существует.

Я работаю над некоторыми разными алгоритмами для генерации случайных polyominos. Я хочу проверить их вывод, чтобы определить, насколько они случайны, т.е. Некоторые экземпляры заданного порядка генерируются чаще, чем другие. Визуально очень легко идентифицировать разные ориентации свободного полиомино, например, следующая иллюстрация в Википедии показывает все 8 ориентаций пентино "F" (Источник):

Как бы поставить номер на этом полиомино, т.е. хэш свободного полиомино? Я не хочу зависеть от преполированного списка "названных" полиоминосов. Во всяком случае, имена с широким согласием существуют только для заказов 4 и 5.

Это не обязательно равносильно перечислению всех свободных (или односторонних или фиксированных) многочленов данного порядка. Я хочу только подсчитать количество раз, когда отображается данная конфигурация. Если генерирующий алгоритм никогда не создает определенного полиомино, он просто не будет считаться.

Основная логика подсчета:

testcount = 10000 // Arbitrary
order = 6         // Create hexominos in this test
hashcounts = new hashtable
for i = 1 to testcount
    poly = GenerateRandomPolyomino(order)
    hash = PolyHash(poly)
    if hashcounts.contains(hash) then  
        hashcounts[hash]++
    else
        hashcounts[hash] = 1

Я ищу эффективный алгоритм PolyHash. Входные полиомины просто определяются как набор координат. Одна ориентация T tetronimo может быть, например:

[[1,0], [0,1], [1,1], [2,1]]:

 |012
-+---
0| X
1|XXX

Можно предположить, что этот входной полиомино уже будет нормализован, чтобы быть выровненным относительно осей X и Y и иметь только положительные координаты. Формально каждый набор:

Будет иметь по крайней мере 1 координату, где значение x равно 0
Будет иметь по крайней мере 1 координату, где значение y равно 0
Не будет координат, где x < 0 или y < 0

Я действительно ищу новые алгоритмы, которые избегают увеличения числа целых операций, требуемых общим подходом грубой силы, описанным ниже.

Грубая сила

Предлагается решение грубой силы здесь и здесь хэширования каждого набора как целого числа без знака с использованием каждой координаты в качестве двоичного флага и принятия минимального хэша всех возможных поворотов (и в моем случае переворачивает), где каждый поворот/флип также должен быть переведен в начало координат. Это дает в общей сложности 23 заданных операции для каждого набора входных данных, чтобы получить "свободный" хеш:

Повернуть (6x)
Flip (1x)
Перевести (7x)
Hash (8x)
Найти минимальные вычисленные хэши (1x)

Если последовательность операций для получения каждого хэша:

Hash
Повернуть, Перевести, Хэш
Повернуть, Перевести, Хэш
Повернуть, Перевести, Хэш
Flip, Translate, Hash
Повернуть, Перевести, Хэш
Повернуть, Перевести, Хэш
Повернуть, Перевести, Хэш

Ответы

Ответ 1

Ну, я придумал совершенно другой подход. (Также спасибо corsiKa за некоторые полезные идеи!) Вместо того, чтобы хешировать/кодировать квадраты, кодировать путь вокруг них. Путь состоит из последовательности "поворотов" (включая поворот) для выполнения перед каждым сегментом. Я думаю, что алгоритм для получения пути от координат квадратов выходит за рамки этого вопроса.

Это делает что-то очень важное: оно уничтожает всю информацию о местоположении и ориентации, которой мы не нуждаемся. Также очень легко получить путь к перевернутому объекту: вы делаете это просто путем изменения порядка элементов. Хранение компактно, потому что для каждого элемента требуется всего 2 бита.

Это вводит одно дополнительное ограничение: полиомино не должно иметь полностью закрытых отверстий. (Формально это должно быть просто связанное.) Большинство обсуждений полиоминосов считают дыру существовать, даже если она запечатана только двумя касающимися углами, поскольку это предотвращает черепицу с любым другим нетривиальным полиомином. Отслеживание краев не затруднено троганием углов (как в одиночном heptomino с отверстием), но он не может прыгать из одного внешнего цикла в внутренний, как в полном кольцеобразном октомино:

Это также создает еще одну проблему: поиск минимального порядка кодированного контура пути. Это связано с тем, что любое вращение пути (в смысле вращения строки) является допустимым кодированием. Чтобы всегда получать ту же самую кодировку, мы должны найти минимальное (или максимальное) вращение инструкций пути. К счастью, эта проблема уже решена: см., Например, http://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation.

Пример:

Если мы произвольно назначим следующие операции перемещениям:

Без поворота: 1
Поверните направо: 2
Поверните налево: 3

Здесь F pentomino прослеживается по часовой стрелке:

Произвольное начальное кодирование для F pentomino (начиная с нижнего правого угла):

2,2,3,1,2,2,3,2,2,3,2,1

Результирующее минимальное вращение кодирования

1,2,2,3,1,2,2,3,2,2,3,2

С 12 элементами этот цикл может быть упакован в 24 бита, если для каждой команды используются два бита или только 19 бит, если команды закодированы как три параметра. Даже при использовании двухбитовой кодировки элемента можно легко вписать это в одно целое без знака 32 бит 0x6B6BAE:

   1- 2- 2- 3- 1- 2- 2- 3- 2- 2- 3- 2
= 01-10-10-11-01-10-10-11-10-10-11-10
= 00000000011010110110101110101110
= 0x006B6BAE

Кодирование base-3 с началом цикла в наиболее значимых степенях 3 равно 0x5795F:

    1*3^11 + 2*3^10 + 2*3^9 + 3*3^8 + 1*3^7 + 2*3^6 
  + 2*3^5  + 3*3^4  + 2*3^3 + 2*3^2 + 3*3^1 + 2*3^0
= 0x0005795F

Максимальное количество вершин в пути вокруг полиомино порядка n составляет 2n + 2. Для 2-битного кодирования количество бит в два раза превышает количество перемещений, поэтому максимальные бит - это 4n + 4. Для кодировки base-3 это:

Где "виселицы" - это функция потолка. Соответственно, любой полиомино до порядка 9 может быть закодирован в одно 32-битное целое число. Зная это, вы можете выбрать свою структуру данных, специфичную для вашей платформы, для быстрого сравнения хэшей, учитывая максимальный порядок многоминосов, которые вы будете хешировать.

Ответ 2

Вы можете уменьшить его до 8 операций хэширования без необходимости перевернуть, повернуть или перевести.

Обратите внимание, что этот алгоритм предполагает, что вы работаете с координатами относительно себя. То есть это не в дикой природе.

Вместо применения операций, которые переворачивают, вращают и переводят, вместо этого просто меняйте порядок, в котором вы хеш.

Например, возьмем F pent выше. В простом примере предположим, что операция хэша была примерно такой:

int hashPolySingle(Poly p)
    int hash = 0
    for x = 0 to p.width
        fory = 0 to p.height
            hash = hash * 31 + p.contains(x,y) ? 1 : 0
    hashPolySingle = hash

int hashPoly(Poly p)
    int hash = hashPolySingle(p)
    p.rotateClockwise() // assume it translates inside
    hash = hash * 31 + hashPolySingle(p)
    // keep rotating for all 4 oritentations
    p.flip()
    // hash those 4

Вместо применения функции ко всем 8 различным ориентациям poly я применил бы 8 различных хеш-функций к 1 poly.

int hashPolySingle(Poly p, bool flip, int corner)
    int hash = 0
    int xstart, xstop, ystart, ystop
    bool yfirst
    switch(corner)
        case 1: xstart = 0
                xstop = p.width
                ystart = 0
                ystop = p.height
                yfirst = false
                break
        case 2: xstart = p.width
                xstop = 0
                ystart = 0
                ystop = p.height
                yfirst = true
                break
        case 3: xstart = p.width
                xstop = 0
                ystart = p.height
                ystop = 0
                yfirst = false
                break
        case 4: xstart = 0
                xstop = p.width
                ystart = p.height
                ystop = 0
                yfirst = true
                break
        default: error()
    if(flip) swap(xstart, xstop)
    if(flip) swap(ystart, ystop)

    if(yfirst)
        for y = ystart to ystop
            for x = xstart to xstop
                hash = hash * 31 + p.contains(x,y) ? 1 : 0
    else
        for x = xstart to xstop
            for y = ystart to ystop
                hash = hash * 31 + p.contains(x,y) ? 1 : 0
    hashPolySingle = hash

который затем вызывается 8 различными способами. Вы также можете инкапсулировать hashPolySingle в цикл за углом и вокруг флип или нет. Все равно.

int hashPoly(Poly p)
    // approach from each of the 4 corners
    int hash = hashPolySingle(p, false, 1)
    hash = hash * 31 + hashPolySingle(p, false, 2)
    hash = hash * 31 + hashPolySingle(p, false, 3)
    hash = hash * 31 + hashPolySingle(p, false, 4)
    // flip it
    hash = hash * 31 + hashPolySingle(p, true, 1)
    hash = hash * 31 + hashPolySingle(p, true, 2)
    hash = hash * 31 + hashPolySingle(p, true, 3)
    hash = hash * 31 + hashPolySingle(p, true, 4)
    hashPoly = hash

Таким образом, вы неявно поворачиваете поли в каждом направлении, но на самом деле вы не выполняете поворот и перевод. Он выполняет 8 хэшей, которые кажутся совершенно необходимыми, чтобы точно хешировать все 8 ориентаций, но не пропускает никаких проходов над поли, которые на самом деле не делают хэши. Это кажется мне самым элегантным решением.

Обратите внимание, что может быть использован более эффективный алгоритм hashPolySingle(). Шахта использует алгоритм декартового исчерпания, который имеет порядок O(n^2). В худшем случае это L-образная форма, которая приведет к квадрату размера N/2 * (N-1)/2 только для элементов N или эффективности 1:(N-1)/4 по сравнению с I-формой, которая была бы 1:1. Также может быть, что встроенный инвариант, наложенный архитектурой, фактически сделает его менее эффективным, чем наивный алгоритм.

Мое подозрение заключается в том, что вышеупомянутое беспокойство можно смягчить, моделируя декартовское истощение, преобразовывая множество узлов в двунаправленный граф, который может быть пройден, заставляя узлы поражаться в том же порядке, что и мой более наивный алгоритм хэширования, игнорируя пустые пространства. Это приведет к сокращению алгоритма до O(n), поскольку график должен быть построен в O(n) времени. Поскольку я этого не делал, я не могу сказать точно, поэтому я говорю это только о подозрении, но должен быть способ сделать это.

Ответ 3

Здесь мой DFS (поиск по глубине первого) объяснил:

Начните с самой верхней ячейки (самое левое - как тай-брейк). Отметьте его как посетили. Каждый раз, когда вы посещаете камеру, проверяйте все четыре направления для невидимых соседей. Всегда проверяйте четыре направления в этом порядке: вверх, влево, вниз, вправо.

Пример

В этом примере сбой вверх и слева не удался, но нажатие преуспевает. До сих пор наш выход был 001, и мы рекурсивно искали ячейку "вниз".

Мы помечаем нашу новую текущую ячейку как посещенную (и мы закончим поиск исходной ячейки, когда мы закончим поиск этой ячейки). Здесь up = 0, left = 1.

Мы ищем самую левую ячейку, и нет невидимых соседей (up = 0, left = 0, down = 0, right = 0). Наш общий объем производства до сих пор составляет 001010000.

Продолжаем поиск второй ячейки. down = 0, right = 1. Мы ищем ячейку справа.

up = 0, left = 0, down = 1. Поиск в нижней ячейке: все 0s. Общий выход до 001010000010010000. Затем мы возвращаемся из нижней ячейки...

right = 0, return. вернуть. (Теперь мы находимся в начальной ячейке.) Right = 0. Готово!

Таким образом, общий выход равен 20 (N * 4) бит: 00101000001001000000.

Улучшение кодирования

Но мы можем сэкономить несколько бит.

Последняя посещаемая ячейка всегда будет кодировать 0000 для четырех направлений. Итак, не кодируйте последнюю посещенную ячейку, чтобы сохранить 4 бита.

Еще одно улучшение: если вы достигли ячейки, двигаясь влево, не проверяйте правильность этих ячеек. Итак, нам нужно всего 3 бита на ячейку, кроме 4 бит для первой ячейки, и 0 для последней ячейки.

Первая ячейка никогда не будет иметь вверх или левый сосед, поэтому опустите эти биты. Таким образом, первая ячейка принимает 2 бита.

Таким образом, с этими улучшениями мы используем только N * 3-4 бита (например, 5 ячеек → 11 бит, 9 ячеек → 23 бита).

Если вы действительно этого хотите, вы можете сжать немного больше, отметив, что точно N-1 бит будет "1".

Caveat

Да, вам нужно закодировать все 8 поворотов/флип из полиомино и выбрать наименьшее, чтобы получить каноническое кодирование.

Я подозреваю, что это все равно будет быстрее, чем общий подход. Кроме того, отверстия в полиомине не должны быть проблемой.

Ответ 4

Недавно я работал над той же проблемой. Я решил проблему довольно просто (1) генерируют уникальный идентификатор для полиомино, так что каждый идентичный poly имеет одинаковый UID. Например, найдите ограничивающий прямоугольник, нормализовать угол ограничивающей рамки и собрать набор непустых ячеек. (2) генерируют все возможные перестановки, вращая (и переворачивая, если необходимо) полиомино, и ищите дубликаты.

Преимущество этого грубого подхода, кроме его простоты, заключается в том, что оно все еще работает, если polys различаются каким-либо другим способом, например, если некоторые из них окрашены или пронумерованы.

Ответ 5

Вы можете настроить что-то вроде trie, чтобы однозначно идентифицировать (а не просто хеш) ваш полиомино. Возьмите свой нормализованный полиомино и настройте двоичное дерево поиска, где корневые ветки на том, имеет ли (0,0), заданный пиксель, следующий уровень веткится на то, имеет ли (0,1) заданный пиксель и т.д. Когда вы смотрите на полиномино, просто нормализуйте его, а затем идите по дереву. Если вы найдете его в trie, то все готово. Если нет, присвойте этому многочлену уникальный идентификатор (просто увеличьте счетчик), сгенерируйте все 8 возможных поворотов и сальто, затем добавьте эти 8 в trie.

Во время промаха вам придется генерировать все повороты и отражения. Но при ударе trie он должен стоить меньше (O (k ^ 2) для k-полиоминов).

Чтобы сделать поиск более эффективным, вы можете использовать несколько бит за раз и использовать более широкое дерево вместо двоичного дерева.

Ответ 6

Действительная хеш-функция, если вы действительно боитесь хеш-коллизий, состоит в том, чтобы сделать хэш-функцию x + order * y для координат, а затем петлю через все координаты части, добавив (order ^ i) * hash (координировать [i]) с куском хэша. Таким образом, вы можете гарантировать, что вы не получите никаких хеш-коллизий.