performance - Prolog中有效的可变图表示？

Question

我想以有效的方式在 Prolog 中表示可变图。我将在图中搜索子集并用其他子集替换它们。

我已经设法使用 使某些东西工作起来了数据库作为我的“图形存储”。例如，我有:

:- dynamic step/2.
% step(Type, Name).

:- dynamic sequence/2.
% sequence(Step, NextStep).

然后我用几条规则来 retract我匹配的子集并使用 assert 用新步骤替换它们.我真的很喜欢这种方法……它易于阅读和处理，而且我让 Prolog 做了很多繁重的模式匹配工作。

我知道的另一种表示图形的方法是使用 列表 节点和邻接连接。我看到很多网站都在使用这种方法，但我有点犹豫，因为它的开销更大。

执行时间对我很重要，对我自己来说易于开发也是如此。

两种方法的优缺点是什么？

Answer 1

像往常一样:使用动态数据库为您提供索引，这可能会加快速度(在查找时)并减慢速度(在断言时)。一般来说，当断言次数多于查找次数时，动态数据库并不是那么好。但主要的缺点是它也使测试和调试显着复杂化，因为您不能单独测试您的谓词，并且需要牢记数据库的当前隐式状态。在许多情况下，节点列表和邻接连接是一个很好的表示。我非常喜欢的另一种表示，特别是如果您需要为节点和边存储更多属性时，是为每个节点使用一个变量，并使用变量属性(SWI-Prolog 中的 get_attr/3 和 put_attr/3)来存储边在它们上面，例如 [edge_to(E1,N_1),edge_to(E2,N_2),...] 其中 N_i 是代表其他节点(具有它们自己的属性)的变量，而 E_j 也是您可以进一步附加的变量如果需要，可以存储关于每条边的附加信息(重量、容量等)的属性。