3

在 hashlife 中，该字段通常被视为理论上无限的网格，所讨论的模式集中在原点附近。四叉树用于表示字段。给定一个由 2^(2k) 个单元格组成的正方形，边上有 2k 个，在树的第 k 层，哈希表在中心存储 2^(k-1) x 2^(k-1) 个正方形单元格, 2^(k-2) 代以后。例如，对于一个 4x4 的正方形，它存储 2x2 中心，向前 1 代；对于 8x8 正方形，它存储 4x4 中心，向前 2 代。

所以给定一个 8x8 的初始配置，我们得到一个以 8x8 正方形为中心的 4x4 正方形 1 代前向中心和一个 2x2 正方形 2 代前向（1 代前向 4x4 正方形）以 8x8 正方形为中心。随着每一代我们对网格的看法减少，反过来我们得到自动机的下一个状态。在将最里面的 2x2 平方 2^(k-2) 代向前推进之后，我们就不能再进一步了。

那么 Golly 中的 hashlife 是如何永远持续下去的呢？此外，它对该领域的看法似乎从未减少。它似乎显示了 2^(k-2) 代后整个自动机的状态。更重要的是，给定一个随时间扩展的起始配置，算法的视图似乎增加了。网格视图缩小以显示扩展自动机？

4

3 回答 3

6

有一篇关于 Dobb 博士的好文章，详细介绍了 HashLife 的工作原理。基本答案是您不仅在现有节点上运行算法，还使用新的移动节点来获得下一代。

于 2009-12-21T23:01:47.457 回答
5

为了清楚起见（因为您的 ^ 符号丢失了），您要问：

给定一个由 2^(2k) 个单元组成的正方形，边上有 2^k，在树的第 k 层，哈希表存储 2^(k-1)×2^(k-1) 个正方形中心的细胞，未来 2^(k-2) 代。[...]

因此，给定一个 8x8 的初始配置 [...] 随着每一代的更新，我们对网格的看法会减少，反过来，我们会得到自动机的下一个状态。在将最里面的 2x2 平方 2^k-2 代向前推进之后，我们不能再进一步了。

那么 Golly 中的 hashlife 是如何永远持续下去的呢？此外，它对该领域的看法似乎从未减少。

与其从您的 8x8 模式开始，不如想象您从一个更大的模式开始，其中恰好包含您的 8x8 模式。例如，您可以从 16x16 图案开始，其中 8x8 图案位于中心，边缘有 4 行空白单元格。通过将空白的 4x4 节点与 8x8 起始模式的 4x4 子节点组合起来，这样的模式很容易构建。

给定这样一个 16x16 的模式，HashLife 算法可以给你一个 8x8 的答案，未来 4 代。

你想要更多？好的，从包含大部分空白空间的 32x32 图案开始，中间是 8x8 图案。有了这个，你可以获得一个 16x16 的答案，它是未来 8 代人的答案。

如果您的图案包含移动的物体，这些物体移动得足够快，以至于它们在 8 代后超出了 16x16 区域怎么办？很简单——从 64x64 启动模式开始，但不要尝试运行 16 代，而是运行 8 代。

一般来说，在任意长的时间段内任意大的、可能扩展的模式的所有情况都可以通过在模式外部添加所需的空白区域来处理（实际上是在 Golly 中处理的）。

于 2011-10-21T04:54:43.383 回答
1

居中的方块只是预先计算的东西。该算法确实始终保持整个宇宙并更新它的所有部分，而不仅仅是中心。

于 2010-07-13T14:06:43.383 回答