从字符串序列自动推断植物生长模型，效率提升显著
A Graph-Based Classical and Quantum Approach to Deterministic L-System Inference
- 构建特征图将推断问题转化为可高效求解的独立集与逻辑满足问题
- 提出经典精确算法和近似量子算法，均在多项式时间内完成推断
- 适合对生物形态建模、自动化推理感兴趣的科研人员
L-system 可用于模拟和生成许多生物过程，如植物发育。通常需专家手工推导特定 L-system，过程耗时且繁琐。若能从数据（如图像序列）中自动推断出对应模型，则意义重大。本文聚焦于从字符串序列中推断确定性上下文无关 L-system（D0L-system）。我们提出字符串序列的特征图，并将其转化为最大独立集（MIS）和 SAT 问题，在多项式时间内完成推断。随后，我们设计了经典精确算法和近似量子算法，实现高效求解。
原文摘要 · Abstract (English)
L-systems can be made to model and create simulations of many biological processes, such as plant development. Finding an L-system for a given process is typically solved by hand, by experts, in a massively time-consuming process. It would be significant if this could be done automatically from data, such as from sequences of images. In this paper, we are interested in inferring a particular type of L-system, deterministic context-free L-system (D0L-system) from a sequence of strings. We introduce the characteristic graph of a sequence of strings, which we then utilize to translate our problem (inferring D0L-systems) in polynomial time into the maximum independent set problem (MIS) and the SAT problem. After that, we offer a classical exact algorithm and an approximate quantum algorithm for the problem.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。