在*解决方案中检查已经访问过的状态，以解决8个嘴式问题

Question

我正在使用A*算法进行大学作业来解决8个插头问题的解决方案，目前正在使用一种方法来识别已经访问过的拼图州以减少冗余操作的方法。我可以将这个问题发生爆发，并列出已经访问的州，并搜索正在探索的每个州，但是显然效率低下。我正在寻找某种方法来使任何难题成为唯一的整数标识符，以便我可以在布尔数组中搜索任何状态并检查它是否已访问。

我想在将数字分配给数学符号时，将数字分配给拼图的每个位置时（这样，左上方位置获得数字2，中间位置3，数字3，右上位置数字5，依此类推）。这样给定拼图的状态，

[[a, b, c]; [d, e, f]; [g, h, i]]

它的标识符将由id =（2^a）（3^b）（5^c）给出，但是很快就花了很长时间意识到这些数字变得非常非常大，并且从内存的角度来看，将大小的数组非常不切实际（我什至不认为具有数组的必要大小甚至是可能的）。

另一个选项是一个具有布尔值的8维数组，因此您可以使用拼图的相应置换值访问它，但是，在语法上，一个8维数组在审美上是非常不愉快的，而后方的疼痛只是声明变量。

有没有办法将唯一的整数标识符分配给拼图的任何给定状态，以便我可以认识到它是否已经以瞬时方式访问，而不必在已经访问过的状态的列表中搜索它？

Answer 1

您需要一个 hash table ，提供O（1）搜索复杂性。

至于唯一的标识符，您可以使用某种哈希，例如：

id = state[0][0]
id = id * 37 + state[0][1]
id = id * 37 + state[0][2]
// and so on for every number in state

对于3x3板，足以代表每个州具有独特整数值的状态，这将在哈希表中效果很好。