Идеи для эффективного способа хеширования состояния 15-головоломки

Я реализую решатель 15 головоломок с помощью Ant Colony Optimization и думаю о способе эффективного хеширования каждого состояния в число, поэтому я трачу наименьшее количество байтов.

Состояние представлено списком из 16 чисел от 0 до 15 (0 — дырка).

Нравиться:

[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0]

Поэтому я хочу создать уникальный номер для идентификации этого состояния. Я мог бы преобразовать все цифры в число с основанием 16, но я не думаю, что это очень эффективно. Есть идеи?

Спасибо


algorithm hash sliding-tile-puzzle
person Alfonso Pérez    schedule 23.12.2013    source источник
comment
Наконец, следуя идее delnan, я перешел на i*4 idx |= val << (i*4), который просто преобразует шестнадцатеричную строку в десятичное число.   -  person Alfonso Pérez    schedule 14.01.2014

Ответы (2)


arrow_upward
7
arrow_downward

Ваше состояние изоморфно перестановкам 16 элементов. 45-битного числа достаточно, чтобы перечислить их (log2 16!), но мы могли бы также округлить до 64-битного, если это выгодно. Задача сводится к нахождению эффективного преобразования из состояния в его позицию в перечислении состояний.

Зная, что каждое число в диапазоне 0..16 встречается только один раз, мы могли бы создать 16 переменных log2 16 = 4 бита каждая, где переменная ith обозначает, в какой позиции встречается число i. Это имеет некоторую избыточность: требуется log2 (16) * 16 бит, но это ровно 64 бита. Его можно реализовать довольно эффективно (непроверенный псевдокод):

state2number(state):
  idx = 0
  for i in [0;16):
    val = state[i]
    idx |= i << (val * 4)
  return idx

Я не знаю, это ли вы имели в виду, говоря «преобразовать все цифры в число с основанием 16». Он безумно эффективен, когда его разворачивают и иным образом микрооптимизируют, это всего несколько десятков циклов. Это занимает на два байта больше, чем необходимо, но 64-битная версия по-прежнему довольно эффективна с точки зрения пространства, и прямое использование ее в качестве индекса в каком-либо массиве невозможно ни для 64-битной, ни для 45-битной.

person Community    schedule 23.12.2013
comment
Спасибо! Я думаю, что это было бы for i in 0..15, но да, это сработало как шарм, еще раз спасибо! - person Alfonso Pérez; 24.12.2013
comment
@AlfonsoPérez Я привык к полуоткрытым диапазонам, но очевидно, что .. - это неправильное обозначение для этого, так что: хороший улов. - person ; 24.12.2013
comment
delnan, насчет эффективности извините, я не уточнил, мне просто интересно, что поскольку в этой конкретной головоломке достижимо только 16!/2 состояний, то таким образом мы бы потеряли пару байтов, но я еще подумал об этом и я думаю, что на самом деле не нужно быть таким педантичным. - person Alfonso Pérez; 24.12.2013
comment
извините, а не будет ли это больше похоже на: idx |= val << (i*4) ? - person Alfonso Pérez; 26.12.2013
comment
@AlfonsoPérez Теперь ты посеял у меня сомнения. Я не уверен (больше), правильно ли это. Однако я знаю, что ваша альтернатива не может быть правильной: сдвиг на i означает, что он не может касаться большинства битов idx, а различные 4-битные переменные мешают друг другу. Вы должны попробовать мою версию (и очевидную альтернативу, idx |= val << (i * 4)) на некоторых перестановках и проверить, соответствует ли результат указанным мною спецификациям. - person ; 26.12.2013
comment
Я думаю, что idx |= val << (i * 4) тоже правильно. Для головоломки 8 idx |= val << (i * 3) не будет правильным, потому что самое большое число равно 8, поэтому требуется 4 бита (двоичное 1000) - для работы его нужно сдвинуть на 3 * 8. Но для головоломки 15 это не имеет значения, потому что самое большое число 15 и занимает 4 бита. - person alcohol is evil; 18.10.2015
comment
Но мой вопрос: все ли значения должны быть уникальными? Мой логический массив для найденных состояний в 9 головоломках содержит более 150 000 000 элементов. Это не так уж и много, но для 16 пазла потребуется гигабайт памяти. Я прав? Как тогда хранить? - person alcohol is evil; 18.10.2015
comment
@alcoholisevil Поздравляю, вы только что столкнулись с комбинаторным взрывом. Слишком много возможных игровых состояний (16!/2 ~= 10^13, как указал OP в комментарии выше), чтобы перечислить их все или сохранить некоторые данные для каждого из них. Я уже говорил об этом в ответе. Есть еще полезные операции, которые вы можете выполнять с идентификатором состояния (например, использовать его в качестве ключа к хэш-карте или другому разреженному массиву), но у вас не может быть полного массива с одним элементом для каждого возможного состояния. - person ; 18.10.2015

arrow_upward
3
arrow_downward

Есть 16! = 2,09 * 10 ^ 13 возможных состояний, для кодирования которых требуется около 44,25 бит.

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

Почему бы не закодировать это так:
Назовем значения a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p.

Значение может быть

b`:= b - (b>a)?1:0;
c`:= c - (c>a)?1:0 - (c>b)?1:0
d`:= d - (d>a)?1:0 - (d>b)?1:0 - (d>c)?1:0
....

hashNumber= a+b*15+c*15*14+d`*15*14*15+....

Это даст вам биективное сопоставление каждого возможного состояния с числом, умещающимся в 6 байтов.

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

Неоптимально, но быстро:
Используйте 4 бита для каждого числа (пропустите последнее, потому что его можно вычислить из предыдущих 15 чисел), для чего требуется 15 * 4 бита = 60 бит. может храниться в 7,5 байтах или, если вы готовы тратить больше, просто используйте 8 байтов.

person MrSmith42    schedule 24.12.2013