2009-12-21 32 views
2

「在hashlife中,該字段通常被視爲一個理論上無限的網格,所討論的模式集中在原點附近。使用四叉樹來表示場。給定一個22k單元的正方形,一邊2k,第k哈希表在未來將2k-1乘2k-1的方格存儲在中心,2k-2代。例如,對於4x4方格,它存儲2x2中心,第1代前向;而對於一個8x8的方塊,它將存儲4x4中心,向前2代。「在Golly中哈希生命如何繼續下去?

因此,如果給定8x8的初始配置,我們會得到一個4x4的正方形1代前向中心w.r.t. 8x8正方形和2x2正方形2代正方形(1代正方形4x4正方形)以8x8正方形爲中心。隨着每一代新一代我們對網格的看法減少,反過來我們得到自動機的下一個狀態。在最內層的2x2平方2k-2代前進之後,我們再往前走。

那麼Golly的hashlife如何永遠持續下去呢?其對該領域的看法似乎也從未減少。它似乎顯示了2k-2代後整個自動機的狀態。更重要的是,隨着時間的推移,隨着時間的推移,這種算法的觀點似乎會增加。網格視圖縮小以顯示擴展的自動機?

+1

這是正式的Languagues和自動機理論? – 2009-12-21 19:00:40

+0

自助項目,以協助學習f#。 – Naximus 2009-12-21 19:05:33

+0

嘿,如果你想出了不錯的F#生活實現,我想看看他們:) – Mau 2010-07-13 14:09:48

回答

6

有一個good article on Dr. Dobb's詳細介紹了HashLife的工作原理。基本的答案是,您不僅僅在現有節點上運行算法,還會使用新的移位節點來獲取下一代。

+0

這是一個很酷的文章。我將不得不在假期嘗試實施。 – gradbot 2009-12-22 02:03:55

+0

我可以得到下一代(使用移位節點並按照你說的合併它們),但不是永遠。正如每個新一代通過視野降低一樣。所以一旦我回到基本情況 - 4x4我不能再走了。 因此,如果給定一個方形的K×K平方,程序將輸出作爲中心的2k-1×2k-1平方,未來2k-2代。 但是如果我想要更多的世代呢?不知何故,哈利生活中的hashlife實現似乎永遠持續下去? – Naximus 2009-12-22 06:53:23

1

集中正方形只是預先計算的東西。該算法確實始終保持整個宇宙,並更新它的所有部分,而不僅僅是中心。

5

要清楚(因爲你的^符號失蹤),你都在問:

鑑於側2 ^(2K)電池,2^k的方形,在的第k個水平 樹,哈希表存儲未來中心2 ^(k-2)代的2 ^(k-1)-by-2 ^(k-1)平方的單元。 [...]

所以賦予了8x8的初始配置[...]隨着每一代新 我們電網的看法降低,在轉,我們得到了 自動機的下一個狀態。在得到最內層的2^k-2代前進之後,我們不得不進一步發展。

那麼Golly的hashlife如何永遠持續下去呢?其對 領域的看法似乎從未減少。

代替使用8×8模式開始的,而是想象你開始與恰好包含在它裏面的8×8模式的更大模式。例如,您可以從16x16圖案開始,該圖案的中心爲8x8圖案,邊緣周圍爲4行空白單元格。通過將空白的4x4節點與8x8開始模式的4x4子節點進行組裝,這種模式很容易構建。

給定這樣的16x16模式,HashLife算法可以給你一個8x8的答案,在未來4代。

你想要更多嗎?好吧,從32x32模式開始,這個模式主要包含空白區域,中間是8x8模式。有了這個,你可以得到一個16x16的答案,在未來8代。

如果您的圖案包含移動的物體,移動的物體移動速度足夠快,以至於經過8代之後纔會出現在16x16區域之外,該怎麼辦?簡單 - 從64x64開始模式開始,但不是試圖運行它整整16代,只是運行它8代。

一般而言,所有的情況下任意大的,可能擴大圖案,隨時間任意長的時間,可以根據需要通過圍繞添加儘可能多的空白空間處理(事實上在天哪處理)模式之外。