3

ハッシュライフでは、フィールドは通常、理論的に無限のグリッドとして扱われ、問題のパターンは原点の近くに集中します。四分木はフィールドを表すために使用されます。ツリーのk番目のレベルで2^（2k）セルの正方形、一辺が2kの場合、ハッシュテーブルは中央に2 ^（k-1）x 2 ^（k-1）のセルの正方形を格納します。 、将来的には2 ^（k-2）世代。たとえば、4x4の正方形の場合、2x2の中心、1世代先に格納されます。8x8の正方形の場合、2世代先の4x4の中心を格納します。

したがって、8x8の初期構成では、8x8の正方形を中心に4x4の正方形を1世代前方に配置し、8x8の正方形を中心に2世代前方（4x4の正方形を1世代前方に）2x2の正方形を配置します。新しい世代ごとに、グリッドのビューが減少し、次にオートマトンの次の状態が得られます。最も内側の2x2平方2^（k-2）世代を先に進めた後は、これ以上先に進むことはできません。

では、ゴリーのハッシュライフはどのように永遠に続くのでしょうか？また、フィールドのビューは決して減少しないようです。2 ^（k-2）世代後のオートマトン全体の状態を示しているようです。時間とともに拡張する開始構成を考えると、アルゴリズムのビューはさらに増えるようです。グリッドのビューがズームアウトして、拡大するオートマトンを表示しますか？

4

3 に答える 3

6

Dr. Dobbに関する優れた記事があり、HashLifeの仕組みについて詳しく説明しています。基本的な答えは、既存のノードでアルゴリズムを実行するだけでなく、新しいシフトされたノードを使用して次世代を取得することです。

于 2009-12-21T23:01:47.457 に答える
5

明確にするために（^記号が欠落しているため）、次のように求めています。

ツリーのk番目のレベルで2^（2k）セルの正方形、1辺が2 ^ kの場合、ハッシュテーブルには2 ^（k-1）x 2 ^（k-1）の正方形が格納されます。中央のセル、将来は2 ^（k-2）世代。[...]

したがって、8x8の初期構成が与えられると、[...]新しい世代ごとに、グリッドのビューが減少し、次に、オートマトンの次の状態が得られます。最も内側の2x2の正方形の2^k-2世代を先に進めた後は、これ以上先に進むことはできません。

では、ゴリーのハッシュライフはどのように永遠に続くのでしょうか？また、フィールドのビューは決して減少しないようです。

8x8パターンから始めるのではなく、8x8パターンが含まれているより大きなパターンから始めることを想像してみてください。たとえば、中央に8x8パターンがあり、端の周りに空白セルの4行の余白がある16x16パターンから始めることができます。このようなパターンは、空白の4x4ノードを8x8開始パターンの4x4サブノードと組み合わせると簡単に作成できます。

このような16x16のパターンを考えると、HashLifeアルゴリズムは、4世代先の8x8の答えを出すことができます。

あなたはもっと欲しい？さて、中央に8x8パターンがあり、ほとんど空白のスペースを含む32x32パターンから始めます。これにより、8世代先の16x16の回答を得ることができます。

パターンに、8世代後に16x16の領域の外に出るほど速く移動する移動オブジェクトが含まれている場合はどうなりますか？シンプル-64x64の開始パターンで開始しますが、16世代全体で実行するのではなく、8世代だけ実行します。

一般に、任意に大きく、場合によっては拡大するパターンのすべてのケースは、パターンの外側に必要なだけ空白を追加することで処理できます（実際にはGollyで処理されます）。

于 2011-10-21T04:54:43.383 に答える
1

中央の正方形は、事前に計算されたものにすぎません。このアルゴリズムは実際、宇宙全体を常に保持し、中心だけでなく、宇宙のすべての部分を更新します。

于 2010-07-13T14:06:43.383 に答える