L系統
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/a/af/Fractal_weeds.jpg/300px-Fractal_weeds.jpg)
Lindenmayer系統,簡稱L系統,是由荷蘭烏特勒支大學的生物學和植物學家,匈牙利裔的阿里斯蒂德·林登麥伊爾(Aristid Lindenmayer)於1968年提出的有關生長發展中的細胞交互作用的數學模型,尤其被廣泛應用於植物生長過程的研究。
L-system是一系列不同形式的正規語法規則,多被用於植物生長過程建模,但是也被用於模擬各種生物體的形態。L-system也能用於生成自相似的分形,例如迭代函數系統。
起源
作為一位生物學家,Lindenmayer工作的內容是酵母菌和絲狀真菌,並研究多種類型的海藻的生長模式,例如藍綠細菌項圈藻(Anabaena catenula,淡水藻類的一種)。最初,L系統被設計成用於提供一種關於簡單多細胞生物體生長的正規描述,並且試圖證明植物細胞之間的緊密關係。不久以後,這個系統被擴展成描述高等植物及其複雜枝杈結構。
L-system 結構
L-system的自然遞歸規則導致自相似性,也因此使得分形一類形式可以很容易的使用L-system描述。植物模型和自然界的有機結構生成,非常相似並很容易被定義,因此通過增加遞歸的層數,可以緩慢生長並逐漸變得更複雜。L-system同樣在製造人造生命領域。 L-system 語法與Chomsky語法非常相似,說到L-system通常指的是帶參數的L-system,定義如下:
G={V,S,ω,P},
V:變量符號集合
S:常量符號集合
ω:初始狀態串
P:產生式規則
自初始狀態開始迭代套入L-system的文法規則,和正規文法所產生的語言不同處在於,L-system在一次迭代中可同時套用許多不同的文法規則。如果在一次迭代中只能夠套用一個文法規則,產生出來的結果被稱為語言而不是L-system。由此可知,L-system為正規文法所產生出的語言的子集合。
L系統的例子
例1:海藻的生長
Lindenmayer研究海藻生長模式時提出的最早的L-系統:
- 變量 : A B
- 常量 : 無
- 公理 : A
- 規則 : (A → AB), (B → A)
迭代過程:
- n = 0 : A
- n = 1 : AB
- n = 2 : ABA
- n = 3 : ABAAB
- n = 4 : ABAABABA
- n = 5 : ABAABABAABAAB
- n = 6 : ABAABABAABAABABAABABA
- n = 7 : ABAABABAABAABABAABABAABAABABAABAAB
例1的解釋
n=0: A 开始 (公理/起始点) / \ n=1: A B 根据规则(A → AB)起始点A拓展成AB,由于起始点没有B,规则(B → A)没有被用到 /| \ n=2: A B A AB中的A拓展成AB,B变成A,于是得到了ABA /| | |\ n=3: A B A A B 可以看到每个A都是一个新的子树的根,由此引发出和整体结构同构的子结构。 /| | |\ |\ \ n=4: A B A A B A B A
如果我們觀察這個序列的長度就會發現這是一個斐波那契數列—— 1 2 3 5 8 13 21 34 55 89 ... (因為我們選擇從A開始,故第一個1少掉了) 如果我們把A看成一隻成年兔子,B看成未成年兔子,那麼這個構造和那個著名的兔生兔的構造是一致的。 即每個月B會成長成A,而A每個月又會生出一個B。
開放問題
許多涉及L-systems研究的問題有待解決,比如:
- 描述所有那些確定的局部連鎖的上下文無關L-systems(目前已知完成解決的只有包含兩個變量的這一種情況)。
- 給定一個結構,找出生成此結構的L-systems文法。
參考文獻
外部連結
- David J. Wright's article on L-systems
- Algorithmic Botany at the University of Calgary (頁面存檔備份,存於互聯網檔案館)
- Branching: L-system Tree (頁面存檔備份,存於互聯網檔案館) A Java applet of the botanical tree growth simulation using the L-system.
- Fractint L-System True Fractals
- "An introduction to Lindenmayer systems", by Gabriela Ochoa。Brief description of L-systems and how the strings they generate can be interpreted by computer.
- "powerPlant" an open-source landscape modelling software (頁面存檔備份,存於互聯網檔案館)
- Fractint home page
- L-Systems in Architecture (頁面存檔備份,存於互聯網檔案館)
- A simple L-systems generator (Windows)
- Lyndyhop: another simple L-systems generator (Windows & Mac)
- An evolutionary L-systems generator (anyos*) (頁面存檔備份,存於互聯網檔案館)
- "LsystemComposition". Page at Pawfal ("poor artists working for a living") about using L-systems and genetic algorithms to generate music.
- eXtended L-Systems (XL), Relational Growth Grammars, and open-source software platform GroIMP. (頁面存檔備份,存於互聯網檔案館)
- A JAVA applet with many fractal figures generated by L-systems. (頁面存檔備份,存於互聯網檔案館)
- Another L-system applet, supporting programming, with explanation and examples.
- L-systems in Architecture; genetic housing.
- L-systems in Plant Growth,Simulation and Visualization (PlantVR). (頁面存檔備份,存於互聯網檔案館)
- Musical L-systems: Theory and applications about using L-systems to generate musical structures, from waveforms to macro-forms. (頁面存檔備份,存於互聯網檔案館)
- L-system digital sound synthesis: 'Do Digital Monkeys Inhabit Virtual Trees?' Electronic music piece composed with L-systems.
- LSys/JS - Interactive L-System interpreter using the Canvas HTML element。
- Lindenmayer System for plant visualisation (Java Applet)。
- Fractal Grower: Free Java paper folding L-System intended for elementary and middle school students. (頁面存檔備份,存於互聯網檔案館)
- Programmatic animations in actionscript showing various L-systems. (頁面存檔備份,存於互聯網檔案館)
- Java applet showing random L-Systems while driving down Lindenmayer Boulevard (頁面存檔備份,存於互聯網檔案館)
- Magic Garden - Artificial Plants Laboratory (頁面存檔備份,存於互聯網檔案館) - free plants generator using L-Systems
- Inkscape (頁面存檔備份,存於互聯網檔案館) a free software vector graphics program which implements, among its plugins, an L-system generator
- Garabatos,an interactive evolutionary image generator based in L-Systems
- Online experiments with L-Systems using JSXGraph (JavaScript) (頁面存檔備份,存於互聯網檔案館)
參見
|