Идея сохранить информацию о посещенных штатах

Question

Сейчас я делаю решатель из 15 головоломок (на с ++), но вместо 15 головоломок моя программа должна решать также головоломки 3x4, 8x8 и т. Д. -> X x Y головоломок.Я должен каким-то образом хранить информацию о посещенных состояниях, моей первой идеей было создать дерево, например:
Пазлы:

Состояние 1
1 2
3 0

Состояние 2
1 3
0 2

Я храню в своем дереве:

root-> 1-> 2->3-> 0
\ _
\ -> 3-> 0-> 2

Это также будет работать для головоломки 5x3, 6x6 и т. Д. Для всех головоломок

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

Следующая идея состояла в том, чтобы сохранить посещенные состояния в stl std.:: map <>, но я не знаю, как сделать хорошую хэш-функцию - для создания ярлыка из состояния головоломки (потому что мне не нужно хранить состояние головоломки, мне нужна только информация, которую посетили. У вас есть идеи?, для ключа к std :: map или других идей для сохранения информации о том, был ли посещен штат?

Answer 1

Предположим, что вас интересует только решение головоломок X * Y, где X, Y <= 16. Я бы представлял состояние головоломки с помощью массива байтов X * Y, в котором каждый байт дает значение квадрата.в загадкеИспользование байтов вместо BigInteger в странной базе, вероятно, даст вам более быстрый доступ и время модификации, потому что битовая арифметика имеет тенденцию быть медленной и, вероятно, не будет хорошим подходом в плане компромисса между памятью и скоростью.1003 * А затем просто используйте <code>std::set<PuzzleState<8,8 > с методами insert и find.После тестирования, если производительность все еще не соответствует требованиям, вы можете создать хеш-таблицу вместо std::set с помощью простой хеш-функции, такой как Rolling hash .

Answer 2

Хеширование Zobrist в значительной степени распространено в программах, которые играют в абстрактные игры.

Answer 3

Я бы представлял одно состояние как число BigInteger (доступна реализация на С ++ здесь , или если вы хотите реализовать свой собственный здесь - это поток,тоже).

Предполагая, что у вас есть головоломка с размерами (X, Y), вы создадите число, используя base = X * Y, и цифры этого числа будут представлять кусочки головоломки, сведенные в однуразмерность.

Например:

State 1
1 2
3 0

Это будет сведено в

1 2 3 0

, а затем преобразовано в число 4, например:

state = (1 * (4^3)) + (2 * (4^2)) + (3 * 4) + 0;

Это уникально идентифицирует любое состояние для любой головоломки.