2

我处理一个问题；我想计算我的代码的递归规则做了多少次递归。

我的程序检查对象是否是计算机硬件的组件（通过组件（X，Y）谓词）。例如组件（计算机，主板）-> true。

它甚至检查对象不是直接组件而是另一个组件的子组件的情况。例如 subcomponent(computer,ram) -> true。（因为 ram 是主板的组件，主板是计算机的组件）

因为我的代码超过 400 行，所以我将只向您展示表单组件（X，Y）和规则子组件（X，Y）的一些谓词。

因此，一些谓词如下：

component(computer,case).
component(computer,power_supply).
component(computer,motherboard).
component(computer,storage_devices).
component(computer,expansion_cards).
component(case,buttons).
component(case,fans).
component(case,ribbon_cables).
component(case,cables).

component(motherboard,cpu).
component(motherboard,chipset).
component(motherboard,ram).
component(motherboard,rom).
component(motherboard,heat_sink).
component(cpu,chip_carrier).
component(cpu,signal_pins).
component(cpu,control_pins).
component(cpu,voltage_pins).
component(cpu,capacitors).
component(cpu,resistors).

等等....

我的规则是：

subcomponent(X,Z):- component(X,Z).
subcomponent(X,Z):- component(X,Y),subcomponent(Y,Z).

好吧，为了计算给定组件 X 到给定组件 Y 所具有的组件数量——也就是递归规则 subcomponents(X,Y) 的递归数量，我做了一些失败的尝试。但是，我在下面介绍它们：

一世）

 number_of_components(X,Y,N,T):- T is N+1, subcomponent(X,Y).
 number_of_components(X,Y,N,T):- M is N+1, subcomponent(X,Z), number_of_components(Z,Y,M,T).

在这种情况下，我收到此错误：“错误：is/2：参数未充分实例化”。

ii)

number_of_components(X,Y):- bagof(Y,subcomponent(X,Y),L),
                        length(L,N),
                        write(N).

在这种情况下，我得到的结果是 1 或 11，并且在这个数字之后是真的，仅此而已。完全没有逻辑！

iii)

count_elems_acc([], Total, Total).
count_elems_acc([Head|Tail], Sum, Total) :-
      Count is Sum + 1, 
      count_elems_acc(Tail, Count, Total).


number_of_components(X,Y):- bagof(Y,subcomponent(X,Y),L),
                        count_elems_acc(L,0,Total),
                        write(Total).

在这种情况下，根据我的知识库，我得到的结果数字不正确。（或者我误译了它们——因为这种方式似乎有一些逻辑）

那么，我做错了什么，我应该写什么？

我期待着阅读你的答案！

4

2 回答 2

3

您可以做的一件事是使用call_with_depth_limit/3. 您调用谓词（在本例中为subcomponent/2）。你增加限制直到你得到一个结果，如果你得到一个结果，这个限制就是使用的最深递归级别。您可以查看相关文档。

但是，您可以做一些更简单的事情。您的数据库可以表示为未加权的有向无环图。所以，把你的整个数据库放在一个有向图中，就像在library(ugraphs)中实现的那样，并找到它的传递闭包。在传递闭包中，一个组件的邻居都是它的子组件。完毕！

要制作图表：

findall(C-S, component(C, S), Es),
vertices_edges_to_ugraph([], Es, Graph)

要找到传递闭包：

transitive_closure(Graph, Closure)

并找到子组件：

neighbours(Component, Closure, Subcomponents)

将Subcomponents是一个列表，您可以使用length/2.

编辑

一些随机的想法：在您的情况下，您的数据库似乎描述了一个根据定义既是有向图又是非循环图（组件-子组件关系严格来说是一种方式，对吗？）。这就是没有必要定义您自己的遍历图表的原因，例如在这个伟大的问题和答案中很好地展示了这一点。因此，您不需要定义自己的递归subcomponent谓词等。

在使用数据库时将数据库表示为一个术语而不是将其保持为平面表的一个好处是，编写操作它的谓词变得微不足道：您可以免费获得 Prolog 的回溯。并且由于 library(ugraph) 使用的图形的 S 表示非常适合 Prolog，因此您很可能最终也会得到一个更高效的程序。

于 2016-01-30T05:25:27.350 回答
1

谓词的调用次数可能是一个困难的概念。我想说，使用您的系统提供的工具。

?- profile(number_of_components(computer,X)).
20===================================================================
Total time: 0.00 seconds
=====================================================================
Predicate                       Box Entries =    Calls+Redos     Time
=====================================================================
$new_findall_bag/0                        1 =        1+0         0.0%
$add_findall_bag/1                       20 =       20+0         0.0%
$free_variable_set/3                      1 =        1+0         0.0%
...
so:count_elems_acc/3                      1 =        1+0         0.0%
so:subcomponent/2                        22 =        1+21        0.0%
so:component/2                           74 =       42+32        0.0%
so:number_of_components/2                 2 =        1+1         0.0%

另一方面，最重要的是从句变量之间的关系。这就是 Prolog 的精髓。所以，试着阅读——比如说，用简单的英语——你的规则。

i) number_of_components(X,Y,N,T)N,T 与 X 有什么关系？我不能说。所以

?- leash(-all),trace.
?- number_of_components(computer,Y,N,T).
   Call: (7) so:number_of_components(computer, _G1931, _G1932, _G1933)
   Call: (8) _G1933 is _G1932+1
ERROR: is/2: Arguments are not sufficiently instantiated
   Exception: (8) _G1933 is _G1932+1 ?

ii)number_of_components(X,Y)如果 Y 是 X 的 number_of_components，那么这里将很有意义。然后，

number_of_components(X,Y):- bagof(S,subcomponent(X,S),L), length(L,Y).

产生

?- number_of_components(computer,X).
X = 20.

或更好

?- aggregate(count, S^subcomponent(computer,S), N).
N = 20.

注意 的用法S。它在它出现的目标中是“存在量化的” 。即，允许在证明目标的同时进行更改。

iii）count_elements_acc/3 - 或多或少 - 等于长度/2，所以结果（打印）似乎是正确的，但同样，这是您的最后一个子句未能建立的 X 和 Y 之间的关系。仅当目的是执行副作用时才应使用从子句打印……例如，调试……

于 2016-01-30T04:20:20.520 回答