亚洲成aⅴ人在线观看_亚洲欧美日韩综合一区在线观看_国产无码电影一区二区三区_国语精品91自产拍在线观看二区

VIP標(biāo)識(shí) 上網(wǎng)做生意,首選VIP會(huì)員| 設(shè)為首頁(yè)| 加入桌面| | 手機(jī)版| RSS訂閱
食品伙伴網(wǎng)服務(wù)號(hào)
 

元胞自動(dòng)機(jī)的分類(lèi)

放大字體  縮小字體 發(fā)布日期:2006-09-19
元胞自動(dòng)機(jī)的構(gòu)建沒(méi)有固定的數(shù)學(xué)公式,構(gòu)成方式繁雜,變種很多,行為復(fù)雜。故其分類(lèi)難度也較大,自元胞自動(dòng)機(jī)產(chǎn)生以來(lái),對(duì)于元胞自動(dòng)機(jī)分類(lèi)的研究就是元胞自動(dòng)機(jī)的一個(gè)重要的研究課題和核心理論,在基于不同的出發(fā)點(diǎn),元胞自動(dòng)機(jī)可有多種分類(lèi),其中,最具影響力的當(dāng)屬S. Wolfram在80年代初做的基于動(dòng)力學(xué)行為的元胞自動(dòng)機(jī)分類(lèi),而基于維數(shù)的元胞自動(dòng)機(jī)分類(lèi)也是最簡(jiǎn)單和最常用的劃分。除此之外,在1990年,Howard A.Gutowitz提出了基于元胞自動(dòng)機(jī)行為的馬爾科夫概率量測(cè)的層次化、參量化的分類(lèi)體系(Gutowitz, H. A. ,1990)。下面就上述的前兩種分類(lèi)作進(jìn)一步的介紹。同時(shí)就幾種特殊類(lèi)型的元胞自動(dòng)機(jī)進(jìn)行介紹和探討S. Wolfrarm在詳細(xì)分忻研究了一維元胞自動(dòng)機(jī)的演化行為,并在大量的計(jì)算機(jī)實(shí)驗(yàn)的基礎(chǔ)上,將所有元胞自動(dòng)機(jī)的動(dòng)力學(xué)行為歸納為四大類(lèi)(Wolfram. S.,1986):
(1)平穩(wěn)型:自任何初始狀態(tài)開(kāi)始,經(jīng)過(guò)一定時(shí)間運(yùn)行后,元胞空間趨于一個(gè)空間平穩(wěn)的構(gòu)形,這里空間平穩(wěn)即指每一個(gè)元胞處于固定狀態(tài)。不隨時(shí)間變化而變化。
(2)周期型:經(jīng)過(guò)一定時(shí)間運(yùn)行后,元胞空間趨于一系列簡(jiǎn)單的固定結(jié)構(gòu)(Stable Paterns)或周期結(jié)構(gòu)(Perlodical Patterns)。由于這些結(jié)構(gòu)可看作是一種濾波器(Filter),故可應(yīng)用到圖像處理的研究中。
(3)混沌型:自任何初始狀態(tài)開(kāi)始,經(jīng)過(guò)一定時(shí)間運(yùn)行后,元胞自動(dòng)機(jī)表現(xiàn)出混沌的非周期行為,所生成的結(jié)構(gòu)的統(tǒng)汁特征不再變止,通常表現(xiàn)為分形分維特征。
(4)復(fù)雜型:出現(xiàn)復(fù)雜的局部結(jié)構(gòu),或者說(shuō)是局部的混沌,其中有些會(huì)不斷地傳播。從另一角度,元胞自動(dòng)機(jī)可視為動(dòng)力系統(tǒng),因而可將初試點(diǎn)、軌道、不動(dòng)點(diǎn)、周期軌和終極軌等一系列概念用到元胞自動(dòng)機(jī)的研究中,上述分類(lèi),又可以分別描述為(譚躍進(jìn),1996;謝惠民,1994;李才偉、1997);
(1)均勻狀態(tài),即點(diǎn)態(tài)吸引子,或稱(chēng)不動(dòng)點(diǎn);
(2)簡(jiǎn)單的周期結(jié)構(gòu),即周期性吸引子,或稱(chēng)周期軌;
(3)混沌的非周期性模式,即混沌吸引子;
(4)這第四類(lèi)行為可以與生命系統(tǒng)等復(fù)雜系統(tǒng)中的自組織現(xiàn)象相比擬,但在連續(xù)系統(tǒng)中沒(méi)有相對(duì)應(yīng)的模式。但從研究元胞自動(dòng)機(jī)的角度講,最具研究?jī)r(jià)值的具有第四類(lèi)行為的元胞自動(dòng)機(jī),因?yàn)檫@類(lèi)元胞自動(dòng)機(jī)被認(rèn)為具有"突現(xiàn)計(jì)算"(Emergent Computation)功能,研究表明,可以用作廣義計(jì)算機(jī)(Universal Computer)以仿真任意復(fù)雜的計(jì)算過(guò)程。另外,此類(lèi)元胞自動(dòng)機(jī)在發(fā)展過(guò)程中還表現(xiàn)出很強(qiáng)的不可逆(lrreversibility)特征,而且,這種元胞自動(dòng)機(jī)在若干有限循環(huán)后,有可能會(huì) "死"掉,即所有元胞的狀態(tài)變?yōu)榱恪?
S·Wolfram還近似地給出了上述四種一維元胞自動(dòng)機(jī)中各類(lèi)吸引子或模式所占地比見(jiàn) (表1-1),可以看出,具有一定局部結(jié)構(gòu)的復(fù)雜模式出現(xiàn)的概率相對(duì)要小一些。而第三種混沌型則出現(xiàn)的概率最大,并且,其概率隨著k和r的增大而呈現(xiàn)增大的趨勢(shì)。


這種分類(lèi)不是嚴(yán)格的數(shù)學(xué)分類(lèi),但S·Wolfram將眾多(也許所有)的元胞自動(dòng)機(jī)的動(dòng)力學(xué)行為歸納為數(shù)量如此之少的四類(lèi),是非常有意義的發(fā)現(xiàn),對(duì)于元胞自動(dòng)機(jī)的研究具有很大的指導(dǎo)意義。它反映出這種分類(lèi)方法可能具有某種普適性,很可能有許多物理系統(tǒng)或生命系統(tǒng)可以按這樣的分類(lèi)方法來(lái)研究,盡管在細(xì)節(jié)上可以不同,但每一類(lèi)中的行為在定性上是相同的 (謝惠民,1994)。
理論上,元胞自動(dòng)機(jī)可以是任意維數(shù)的。那么,按元胞空間的維數(shù)分類(lèi),元胞自動(dòng)機(jī)
通?梢苑譃:
(l)一維元胞自動(dòng)機(jī):元胞按等間隔方式分布在一條向兩側(cè)無(wú)限延伸的直線(xiàn)上,每個(gè)元胞 (Cell)具有有限個(gè)狀態(tài)s,s∈S={s1,s2,...,sk},定義鄰居半徑r,元胞的左右兩側(cè)共有2r個(gè)元胞作為其鄰居集合N,定義在離散時(shí)間維上的轉(zhuǎn)換函數(shù)f:S2r 1→S可以記為:
,Sit為第i個(gè)元胞在t時(shí)刻的狀態(tài)。
稱(chēng)上述A={S,N,f}三元組(維數(shù)d≡1)為一維元胞自動(dòng)機(jī) (Amoroso,S,1972;李才偉,l997)。
對(duì)一維元胞自動(dòng)機(jī)的系統(tǒng)研究最早,相對(duì)來(lái)講,其狀態(tài)、規(guī)則等較為簡(jiǎn)單,往往其所有可能的規(guī)則可以一一列出,易于處理,研究也最為深入。目前,對(duì)于元胞自動(dòng)機(jī)的理論研究多集中在一維元胞自動(dòng)機(jī)上。S,Wolfram對(duì)元胞自動(dòng)機(jī)的動(dòng)力學(xué)分類(lèi)也是基于對(duì)一維初等元胞自動(dòng)機(jī) (Elementary Cellular Automata)的分析研究得出的。它的最大的一個(gè)特征在于容易實(shí)現(xiàn)元胞自動(dòng)機(jī)動(dòng)態(tài)演化的可視化:二維顯示中,一維顯示其空間構(gòu)形,空間維;另外一維顯示其發(fā)展演化過(guò)程,時(shí)間維。
(2)二維元胞自動(dòng)機(jī):元胞分布在二維歐幾里德平面上規(guī)則劃分的網(wǎng)格點(diǎn)上,通常為方格劃分。以J. H. Conway的"生命游戲"為代表,應(yīng)用最為廣泛。由于,世界上很多現(xiàn)象是二維分布的,還有一些現(xiàn)象可以通過(guò)抽象或映射等方法,轉(zhuǎn)換到二維空間上,所以,二維元胞自動(dòng)機(jī)的應(yīng)用最為廣泛,多數(shù)應(yīng)用模型都是二維元胞自動(dòng)機(jī)模型。

(3)三維元胞自動(dòng)機(jī):目前,Bays(Bays,C,1988)等人在這方面做了若干試驗(yàn)性工作,包括在三維空間上實(shí)現(xiàn)了生命游戲,延續(xù)和擴(kuò)展了一維和二維元胞自動(dòng)機(jī)的理論。
(4)高維元胞自動(dòng)機(jī):只是在理論上進(jìn)行少量的探討,實(shí)際的系統(tǒng)模型較少。Lee Meeker在他的碩士論文中,進(jìn)行了對(duì)四維元胞自動(dòng)機(jī)的探索。

 

 

 
推薦圖文
推薦食品專(zhuān)題
點(diǎn)擊排行
 
 
Processed in 0.217 second(s), 484 queries, Memory 1.86 M