c++ - 汉明立方体的数据结构

Question

我有一个普通维数的汉明立方体，但在实践中，维数通常在 3 到 6 之间。

搜索算法是:

Input: any vertex, `v`.
Find all vertices that lie in Hamming distance 1 from `v`.
Find all vertices that lie in Hamming distance 2 from `v`.
...

我事先不知道我需要离开 v 多远。例如，我可能会停在距离 1。

例如，给定这个立方体:

和 v = 100，我需要汉明距离为 1 的顶点，它们是 000、101、110(以任何顺序)。然后，我可能需要获取距离为 2 的顶点，即 111、001、010。如果极少数情况下也需要距离为 3 的顶点，我也会获取 011。

立方体的顶点可能包含 ID(整数)。

哪种数据结构适合存储此多维数据集并有效地搜索它？我对其他操作不太感兴趣。

我考虑过以某种方式对所有位序列进行排序，以便我可以轻松访问它们，但没有任何效果。

---

到目前为止我的方法:

data-structure使用哈希表(特别是 std::unordered_map)，其中键是顶点，值是 ID。

algorithm给定一个顶点 v，生成汉明距离 t 内的所有位序列(即 1、2、...)。

但是，这需要我在每次顶点v到达时调用一个函数(这经常发生)。我有一个函数可以实现这个，基于 this .

Answer 1

我对 C++ 生疏了，所以我会保持抽象。

汉明立方体给定点的邻居很容易计算。给定一个顶点的位序列，分别翻转每个位。

不过，您可以预先计算。您可以缓存 neighbors() 函数的结果，也可以将它们保存到一个数组中。每个顶点都有自己的邻居，因此每个顶点都有一个数组。这基本上为您提供了邻接表。

有了这个邻接表，您就可以使用深度限制搜索来搜索您的汉明立方体，它是 DFS(我猜是 BFS，但空间复杂度更差)的一种变体，深度仅为 k 个单位.

---

您的数据结构是一个不错的选择，但考虑到您的顶点是二进制字符串，因此它们涵盖了从 0 到 2^n - 1 的所有点。您还不如只使用一个数组——查找仍然是 O(1)，而且它会更紧凑，因为周围没有未使用的桶。