使用 L-系統 生成的 3D 雜草
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文法。
参考文献
外部連結
参见