6

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

我已经设法使用数据库作为我的“图形存储”来工作。例如，我有：

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

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

retract然后，我对匹配的子集使用一些规则，并使用assert. 我真的很喜欢这种方法……它易于阅读和处理，我让 Prolog 完成了很多繁重的模式匹配工作。

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

执行时间对我来说很重要，对我来说易于开发也很重要。

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

4

3 回答 3

5

像往常一样：使用动态数据库可以为您提供索引，这可能会加快速度（在查找时）并减慢您的速度（在断言时）。通常，当您断言的次数多于查找的次数时，动态数据库就不那么好了。但主要缺点是它也使测试和调试变得非常复杂，因为您无法单独测试谓词，并且需要牢记数据库的当前隐式状态。在许多情况下，节点列表和邻接连接是一个很好的表示。我非常喜欢的另一种表示形式，特别是如果您需要为节点和边存储更多属性，是为每个节点使用一个变量，并使用变量属性（SWI-Prolog 中的 get_attr/3 和 put_attr/3）来存储边在他们身上，例如 [edge_to(E1,N_1),edge_to(E2,N_2),...

于 2011-07-29T14:36:05.113 回答
1

您是否考虑过使用 SWI-Prolog 的 RDF 数据库？http://www.swi-prolog.org/pldoc/package/semweb.html

于 2011-07-29T17:22:54.070 回答
0

正如 mat 所说，动态谓词有额外的成本。
但是，如果您可以构建图形并且不需要更改它，则可以编译谓词，它将与普通谓词一样快。

通常在 sw-prolog 中，谓词查找是在第一个参数上使用哈希表完成的。（如果是动态谓词，它们会调整大小）

另一种解决方案是关联列表，其中查找等的成本为 o(log(n))
在您了解它们的工作原理后，您可以在需要时轻松编写接口。

最后，您始终可以使用 SQL 数据库并使用ODBC 接口提交查询（尽管对于您提到的应用程序来说，这听起来有点矫枉过正）

于 2011-07-29T18:21:34.300 回答