8

更新：这被称为 de Brujin 圆环，但我仍然需要在 C# 中找出一个简单的算法。

http://en.wikipedia.org/wiki/De_Bruijn_torus

http://datagenetics.com/blog/october22013/index.html

我需要尽可能密集地组合 3x3 位网格的所有值。通过 3x3 位网格，我的意思是 3x3 网格，其中每个位置有点类似于这个问题中的打孔概念：

查找 3x3 打孔的所有组合

3x3 位网格示例：

XXX .X. ...
XXX .X. .X.
XXX .X. ...

目标

我想打包所有 512（实际上是 256，因为中心位始终打开）可能的值，以便它们在单个 NxM 网格中重叠。

不完整的例子：

此示例将大约 25 个可能值打包到 7x7 网格中。

.......
.X.XXX.
.......
.X.XXX.
.X.XXX.
.X.XXX.
.......

已经知道的事情：

  • 有 2^9 (512) 个唯一值。
  • 我只关心 2^8 (256) 个值，因为我需要始终打开中心位。

尝试

我手动尝试了许多不同的技术，但无法提出一个简单的算法。

所以，我想编写一个 C# 程序来创建它，但我也没有看到一个简单的方法。

在我看来，甚至没有明显的蛮力方法。似乎任何蛮力尝试都会接近 512！在最坏的情况下组合。

观察

每条边只有 8 个可能的值。

X...X.XXX. //(8+2 bits) Exhausts all values in the same problem with 1-Dimension.

.X.XXX.    //(5+2 bits) The above simplifies when the center bit must be on.

目的

这实际上将用于基于 2d 瓦片的游戏。

游戏有 N 个可能的地块。鉴于地面可以在任何情况下出现，设计师需要一种方式来表达在任何给定情况下应该选择哪个瓷砖。

包含所有可能情况的紧凑网格是指定在每种情况下使用哪个图块并消除所有冗余的最有效方法。

更新

例子

....
.XX.
.XX.
....

以上是允许表达 4 种情况的基本模式，我将对其进行修改以使用其他 ascii 值来表示应在每种情况下使用的结果：

....
.AG.
.HH.
....

其中 A、G、H 各自代表应用于每种情况的特定模式。

因此，如果找到以下模式：

...
.XX
.XX

这与上面导致“A”的模式匹配，因此在这种情况下将使用“A”。

???
?A?
???

目的是详尽地表达每种可能的情况会导致什么。

在实践中

我能够尝试这个，发现结果太随机了，无法很好地实现目标。作为人类，很难在每种情况下选择正确的价值观，因为或者混乱。类似模式的手动分组仍然效果更好。

4

3 回答 3

3

使用 De Bruijn 序列将所有 3x3 模式打包到 3xN 网格中

让我们将每个 height-3 列视为 0 到 7 之间的单个数字，我们可以这样做，因为有 8 个可能的 height-3 列。现在，将所有 512 个可能的 3x3 模式打包到最小可能的 3xN 大小的网格中，相当于找到一个带有参数 B(8, 3) 的 de Bruijn 序列。这个网格的大小是3x514：在第一个 3x3 之后，每个额外的 3x3 只花费我们 1 个额外的列，这对于高度为 3 的网格显然是最好的。

根据该 Wikipedia 页面，似乎最有效的方法是通过在前一个序列的 de Bruijn 图（因为另一个建议的算法涉及寻找哈密顿路径，这是一个 NP 完全问题，其难度相当于旅行商问题）。

还有de Bruijn tori，de Bruijn 序列的 2D 类似物，可以更直接地接近您打包到 NxN 网格中的目标。但是，从该页面上不清楚如何甚至是否可以为 3x3 图案构建 de Bruijn 圆环（他们只说已知可以为均匀大小的方形图案构建它们，并且方形的圆环奇数大小的模式本身不能是正方形的——所以大概 NxN 已经出局了），此外，它们满足的强唯一性约束可能对您的应用程序来说是不必要的。

于 2015-06-11T11:20:10.050 回答
2

下面的 520 位字符串包含所有 3x3 位模式作为连续子序列：

XXXXXXXXX.XXXXXXX..XXXXXX.X.XXXXXX...XXXXX.XX.XXXXX.X..XXXXX..X.XXXXX....XXXX.XXX.XXXX.XX..XXXX.X.X.XXXX.X...XXXX..XX.XXXX..X..XXXX...X.XXXX.....XXX.XXX..XXX.XX.X.XXX.XX...XXX.X.XX.XXX.X.X..XXX.X..X.XXX.X....XXX..XX..XXX..X.X.XXX..X...XXX...XX.XXX...X..XXX....X.XXX......XX.XX.XX.X..XX.XX..X.XX.XX....XX.X.XX..XX.X.X.X.XX.X.X...XX.X..X..XX.X...X.XX.X.....XX..XX...XX..X.X..XX..X..X.XX..X....XX...X.X.XX...X...XX....X..XX.....X.XX.......X.X.X.X..X.X.X....X.X..X...X.X...X..X.X......X..X..X.....X...X....X.........XXXXXXXX

或者，如果您愿意，可以使用 j_random_hacker 的版本：

............X..X..X..X...........X..X..X..X...........X..X..X..X...........X..X..X..X.X..X..X..XX.XX.XX.XX.X..X..X..XX.XX.XX.XX.X..X..X..XX.XX.XX.XX.X..X..X..XX.XX.XX.XX.........X..X..X..X........X..X..X..X........X..X..X..X.X..X..XX.XX.XX.XX.X..X..XX.XX.XX.XX.X..X..XX.XX.XX.XX.X..X..XX.XX.XX.XX......X..X..X..X.....X..X..X..X.X..XX.XX.XX.XX.X..XX.XX.XX.XX.X..XX.XX.XX.XX.X..XX.XX.XX.XX...X..X..X..X.XX.XX.XX.XX.XX.XX.XX.XX.XX.XX.XX.XX.XX.XX.XX.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..
......X..X........X..X.....X..X........X..X.X..XX.XX.X..X..XX.XX.X..XX.XX.X..X..XX.XX.....X..X........X..X.....X..X........X..X.X..XX.XX.X..X..XX.XX.X..XX.XX.X..X..XX.XX...X..X........X..X.XX.XX.X..X..XX.XX.XX.XX.X..X..XX.XX..X..X........X..X..X..X........X..X.XX.XX.X..X..XX.XX.XX.XX.X..X..XX.XXXXXXXX.XX.XXXXXXXXXXX.XX.XXXXXXX.XX..X..X.XX.XX.XX..X..X.XX.XXXXXX.XX.XXXXXXXXXXX.XX.XXXXXXXXX.XX.XXXXXXX..X..X.XX.XX..X..X.XX.XXX.XX.XXXXXXXX.XX.XXXXXX......X..X.....X..X.X..XX.XX.X..XX.XX...X..X.XX.XX.XX.XXXXXXXXXX..
...X.....X.....X.....X.XX.X..XX.X..XX.X..XX..X.....X.....X.....X.XX.X..XX.X..XX.X..XX..X.....X.....X.....X.XX.X..XX.X..XX.X..XX..X.....X.....X.....X.XX.X..XX.X..XX.X..XXXXX.XXXXX.XXXXX.XXXX..X.XX..X.XX..X.XXX.XXXXX.XXXXX.XXXX..X.XX..X.XX..X.XXX.XXXXX.XXXXX.XXXX..X.XX..X.XX..X.XXX.XXXXX.XXXXX.XXX...X.....X.....X.XX.X..XX.X..XX..X.....X.....X.XX.X..XX.X..XX..X.....X.....X.XX.X..XX.X..XXXXX.XXXXX.XXXX..X.XX..X.XXX.XXXXX.XXXX..X.XX..X.XXX.XXXXX.XXX...X.....X.XX.X..XX..X.....X.XX.X..XXXXX.XXXX..X.XXX.XXX...X.XXX..

或者您可以节省空间并简单地使用从 0 到 511 的数字，对于大多数计算机来说，这些数字都是 9 位模式。

于 2015-06-11T17:42:14.947 回答
0

“包含所有可能情况的紧凑网格是指定在每种情况下使用哪个图块并消除所有冗余的最有效方法。”

我倾向于不同意。

无论折叠练习的结果如何，索引它以检索给定的 3x3 模式都需要 8 位索引，因为正好有 256 个瓦片邻接情况。如果您的紧凑表示包含超过 256 个模式 - 也就是说，如果混入了不需要或冗余的模式 - 那么您将需要超过 8 位进行索引。

但是，如果将 8 位字节视为位掩码并以某种方式将 8 位映射到 3x3 网格的八个外部图块，则 8 位字节已经可以表示所有可能的邻接情况。这意味着折叠的主网格 - de Bruijn 风格或其他风格 - 是多余的，可以省去。

于 2015-06-12T07:02:51.193 回答