3

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

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

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

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

4

5 回答 5

2

您可以随时尝试加密哈希函数。由于您的问题不是安全问题（没有攻击者故意试图找到哈希到相同值的不同状态），您可以使用损坏的哈希函数。我建议尝试MD4，它非常快。您的 54 个字符的字符串非常适合 MD4 输入（MD4 可以将最多 55 个字节的输入作为单个块处理）。

一台基本的 2.4 GHz PC 每秒可以散列大约 1200 万个这样的字符串，使用单个内核，使用简单的展开的 C 实现（例如，看起来像MD4Transform()RFC 1320 中包含的示例代码中的函数）。这可能足以满足您的需求。

于 2010-12-02T18:45:46.307 回答
2

1) 不要使用哈希9*6 = 54魔方上 有不同的面。即使浪费地使用每个面 1 个字节，这也是 432 位，因此散列不会为您节省太多空间。每个面 3 位的更好打包为 162 位（21 字节）。在我看来，您需要一种紧凑的方式来表示魔方。

OTOH，如果您要存储一组许多以前访问过的状态，那么我发现使用布隆过滤器而不是真正的集合可以获得不错的结果（但通常不是最佳的），而且空间利用率要低得多。

2）如果你接受哈希的想法： 只需使用 MD5，它比建议的 rubik 状态稍微紧凑，相当快，并且具有良好的碰撞特性 - 这不像你有一个恶意对手试图引起 rubik cube hash碰撞;-)。

编辑：一旦您拥有实现算法的库或函数（例如：OpenSSL、GNU TLS 和许多独立的实现），使用加密哈希函数（如 MD4/MD5）通常很简单。通常该函数类似于void md5(unsigned char *buf, size_t len, unsigned char *digest)wheredigest指向预分配的 16 字节缓冲区并且buf是要散列的数据（您的魔方结构）。这是一些未经测试的C代码：

#include <openssl/md5.h>
void main()
{
    unsigned char digest[16];
    unsigned char buf[BUFLEN];
    initializeBuffer(buf);
    MD5(buf,BUFLEN,digest);    // This is the openssl function
    printDigest(digest);
}

并确保编译/链接-lssl.

于 2010-12-02T18:52:43.240 回答
2

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

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

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

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

于 2010-12-02T20:48:52.710 回答
1

只是为了建立理论上的最小表示 -有效魔方的状态空间约为4.3*10^19. 然后，日志2 (4.3*10^19) 将确定您需要多少位来表示该完整空间，其上限为 66。所以理论上，如果你可以对每个有效状态进行编号，任何给定的状态都可以用 66 位唯一地表示。

虽然您可能希望遵循其他人的建议并找到一种更紧凑的方式来表示立方体，但请考虑用边、角和面片来表示状态。由于合法立方体移动的交换法则，您应该能够连接 12 个 4 位边缘位置、8 个 3 位角位置和 6 个 3 位面位置的序列。这应该导致使用 90 位的唯一表示。

这种表示可能不利于您创建树的方式，但它是独一无二的，易于比较，并且应该可以在您现有的表示中找到给定的状态。

于 2010-12-02T21:12:21.647 回答
1

8个角立方体：

  • 您可以将这些角中的每一个分配给 8 个位置，每个位置需要 3 位来确定哪个角立方体在哪个位置，总共 24 位。
  • 您可以进一步将其减少为仅记录 8 个位置中的 7 个，因为您可以轻松地使用消除过程来确定第 8 个角是什么（对于 21 位）。
  • 但是，这可以进一步减少，因为 8 个角只能以排列8! = 40320排列并且40320可以用 16 位表示。

每个角立方可以正确定位或顺时针或逆时针旋转 120° 以处于三个不同的位置（分别表示为 0、1 和 2）。

  • 这需要每个角 2 位来表示。
  • 但是，方向之和（模 3）始终为 0；因此，如果您知道 8 个方向中的 7 个（假设您有一个可解的立方体），您可以计算第 8 个角的方向（总共 14 位）。
  • 或者为了进一步简化，七个三进制（以 3 为基数）数字可以表示角的方向，这可以用 12 个二进制数字（位）表示。

所以角立方体可以用 28 位表示，如果你想解码排列，或者用 33 位表示，如果你想直接记录 7-of-8 个角的位置。

12个边缘立方体：

  • 每个都可以用 4 位表示（总共 48 位），可以通过仅记录 12 个边缘的 11 个位置（总共 44 位）将其减少到 44 位。
  • 但是，12! = 479001600边缘的排列可以存储在 29 位中。

每条边都可以正确定向或翻转：

  • 这需要 1 位来表示。
  • 但是，边缘总是成对翻转，因此翻转边缘的奇偶校验将始终为零（再次，这意味着您只需要记录边缘的 12 个方向中的 11 个），总共需要 11 位。

所以边立方体可以用 40 位表示，如果你想解码排列，或者如果你想记录所有位置和 12-of-12 边缘的翻转，可以用 55 位表示。

6个中心立方体

你不需要记录任何关于中心立方体的信息——它们相对于魔方中心的球是固定的（所以假设你不担心立方体上任何标志的方向）是不动的。

总计：

  • 使用排列：68 位
  • 使用位置：88 位
于 2016-01-18T01:18:42.040 回答