algorithm - 从具有连接要求的预定义元素生成有向无环图

Question

我正在研究一个系统，当给定一组不同类型的元素时，将创建一个连接部分或所有元素的有向无环图。每个元素都有一些输入 A 和输出 B。在构建图时，系统需要确保前一个节点的输出与当前节点的输入相匹配。

节点的输入和输出是为了确保只连接某些类型的元素

元素看起来像这样

ElementName : Input -> Output

可能有多个输入/输出，或者没有输出(见下文)。

One : X -> Y
Two : Y -> Z,F
Three : Y, Z -> W
Four : Z -> F
Five : F -> NULL

注意:

我们正在谈论很多不同的元素，现在大约有 30 个，但计划随着时间的推移添加更多。

这是进行程序生成叙事的项目的一部分。节点是个人任务。输入是您开始任务所需要的。输出是如何影响故事状态的。

问题:

我见过几种生成随机 DAG 的不同方法，而不是根据一些预设连接要求(具有连接它们的规则)制作 DAG 的方法。我还想要一些限制图形复杂性的方法。即限制他们可以拥有的分支数量。

我想要什么的想法:

你的垃圾箱里有一堆不同类型的乐高积木，比如 30 个。你有连接乐高积木的规则。

Blue -> Red
Blue -> White
Red -> Yellow
Yellow -> Green/Brown
Brown -> Blue

众所周知，除了颜色之外，每个乐高积木都有形状。所以 2 个蓝色乐高积木可能不是同一类型的乐高积木。所以我们的目标是建立一个符合我们规则的大型结构。即使有我们的规则，我们仍然可以将乐高积木连接成一堆不同的结构。

P.S. 我希望这不是一个笼统的问题。如果是，请记下，我会尽量使其更具体。

Answer 1

听起来像 L-system (又名 Lindenmayer 系统)方法可行:

• 您的乐高积木收藏类似于符号字母表
• 您的连接规则对应于一组产生式规则，这些产生式规则将每个符号扩展为更大的符号串
• 您的起始乐高代表开始构造的初始“公理”字符串
• 生成的几何结构就是您的 DAG

最简单的方法类似于:给定一个乐高积木，随机选择一个有效的连接规则并将一个新的乐高积木添加到 DAG。从那里您可以根据需要添加更多的复杂性。如果您需要倾斜随机选择以支持某些规则，那么您实际上是在构建一个 stochastic grammar .如果规则的选择取决于先前生成的 DAG 部分，则它是 context sensitive grammar 的类型.

Graph rewriting ，通过算法从基础图创建一个新图，可能是一个更直接的解决方案，但我个人发现 L 系统更容易内化并且研究它们产生的结果在本质上并不过分学术/理论。

L 系统本身属于 formal grammars 的类别.可能值得检查其中一些相关的想法，但很容易(至少对我而言)以牺牲核心开发为代价而被理论内容所牵制。