hash - 帮助设计一个散列函数来检测重复记录？

Question

让我解释一下我的程序。它是一个魔方求解器。我得到一个加扰的立方体(这是初始状态)。这成为图的根节点。我正在使用 iterative deepening depth first search 将这个打乱的立方体“暴力破解”到可识别的状态，然后我可以使用模式识别来解决。

您可以想象，这是一个非常大的图，所以我想提出某种散列功能来检测该图中的重复节点(从而加快遍历速度)。

我对散列函数基本不熟悉，但这是我的想法……每个节点本质上都是魔方的不同状态。所以如果我来到一个已经看到的立方体状态(节点)，我想跳过它。所以我需要一个散列函数，将我从状态变量带到校验和，其中状态变量是一个 54 个字符的字符串。唯一允许的字符是 y, r, g, o, b, w(对应于颜色)。

任何帮助设计此哈希函数将不胜感激。

Answer 1

为了最快的重复检测和删除 - 首先避免生成许多重复的位置。这比生成然后查找重复更容易并且更快。因此，例如，如果您有 F 和 B 之类的移动，如果您允许子序列 FB 也不允许 BF，这会给出相同的结果。如果您刚刚完成 3F​​，请不要跟随 F。您可以生成一个小的查找表，用于在给定最后三个 Action 的情况下允许下一步 Action 。

对于剩余的重复项，您需要快速散列，因为位置很多。正如其他人所评论的那样，为了使您的哈希值更快，您希望它的哈希值来自，即位置的表示，要小。有 12 个边角 block 和 8 个角 block 。表示每个立方体的位置和方向只需每个立方体 5 位，即总共 100 位(12.5 字节)。对于边缘，它的四位用于位置，一位用于翻转。对于角，它的三位代表位置，2 位代表自旋。你可以忽略最后一个边缘立方体，因为它的位置和翻转是由其他人固定的。使用这种表示形式，您的位置已经减少到 12 个字节。

你在一个魔方位置有大约 70 个真实位的信息，而 96 位足够接近 70 位，因此实际上对这些位进行进一步的散列运算会适得其反。 IE。将此板的表示视为您的哈希。这听起来可能有点奇怪，但是从您的问题来看，我设想您同时尝试使用更适合您的模式匹配的立方体的不太紧凑的表示。在这种情况下，12 字节的值可以被视为散列，其优点是它是永远不会发生冲突的散列。这使得重复测试代码和新值插入更短、更简单、更快。它会比目前建议的 MD5 解决方案便宜。

您可以使用许多其他技巧来减少搜索重复位置的工作量。看看http://cube20.org/想法。