植物的算法美/[加拿大] 普鲁辛凯维奇
第1章应用L系统的绘图模型Lindenmayer系统(简称为L系统),被认为是植物生长的数学理论。起初L系统并没有详细地给出有关高级植物的综合模型,而是重点研究植物的拓扑结构,也就是强调植物细胞之间或者大一点的模块之间的相邻关系,而植物的几何形态超出了它的理论研究范围。
后来为了把L系统作为植物模型研究通用的工具,提出了几种有关L系统的几何解释。贯穿整本书,应用了以海龟几何学为基础的几何解释。与L系统理论相关的基本概念和海龟几何学解释如下。
1.1重写系统1.Koch结构L系统的核心概念是重写,也称为迭代重写。一般情况下,重写是通过应用一个重写规则(rewriting rules)或产生式(productions)的集合,对简单的初始目标中的部分(可以是一部分也可以是多个部分)进行连续置换来定义复杂目标的技术。
利用重写规则定义图形的经典例子是1905年由Koch提出的雪花曲线(图1.1),Mandelbrot又重新描述了这个结构。
在Koch结构递归置换开多边形的同时,对其他对象的迭代重写也进行了研究。例如,Wolfram研究了矩形阵列的元素迭代重写生成的类型。流行的Conway生命游戏的基础就是一个与之类似的迭代重写机制。
在该研究领域,各种图形的迭代重写体系是人们重点研究的内容之一。2.语法应用最广泛、最容易理解的迭代重写是对字符串的操作,这种系统最初的正式定义是20世纪初由Thue给出的。
但一个应用广泛的字符串迭代重写系统的例子是在20世纪50年代末期,由Chomsky在研究形式语法的基础上给出的,他应用迭代重写的概念来研究自然语言的语法特征。几年以后,Backus和Naur为了给出程序设计语言ALGOL-60的一个正式定义而引进了迭代重写的基本符号。